wordpress会员互动/苏州优化网站公司
题目
二叉树结点的平衡因子（bf）定义为该结点的左子树高度与
右子树高度之差。设二叉树结点结构为：(lchild,data,bf,rchild),
lchild,rchild 是左右儿子指针；data 是数据元素；bf 是平衡因子，编写递归算法计算二叉树中各个结点的平衡因子。
广告
若有同学需要桂林电子科技大学数据结构考研真题和答案解析（个人制作）或指定参考书《算法与数据结构》第三版张乃孝PDF等资料的欢迎交流（QQ（(肆＋壹)幺幺）&微信（月球不太圆）15577498906）
算法思路
通过后序遍历来遍历二叉树的每一个结点，然后计算每一个结点平衡因子。平衡因子等于左子树高度与右子树高度之差。故需要求出左子树和右子树的高度，也是算法的核心难点。
求出左子树和右子树的高度的算法是high（TreeNode * t），t有三种情况，1为空，2是指向叶子结点，3是指向非叶子的结点。第一种情况，返回0，第二种情况，返回1，第三种情况复杂，需要再次调用high（TreeNode * t），返回1+自己的最大子树高度。
代码
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
typedef struct TreeNode TreeNode;
struct TreeNode {int val;TreeNode *left;TreeNode *right;int bf=0;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* CreateBTree();
TreeNode* CreateBTree()
{TreeNode *bt = NULL;int ch;scanf("%d", &ch);if (ch != -1){bt = new TreeNode(ch);bt->val = ch;bt->left = CreateBTree();bt->right = CreateBTree();}return bt;
}
void PutTree(TreeNode* bt)
{if(bt==NULL)return;else{printf("%d 平衡因子%d ",bt->val,bt->bf);PutTree(bt->left);PutTree(bt->right);}
}
int max(int a,int b)
{if(a>b)return a;elsereturn b;
}
int high(TreeNode * t)
{if(t!=NULL){if(t->left==NULL&&t->right==NULL)return 1;elsereturn 1+max(high(t->left),high(t->right));}elsereturn 0;
}
void visit(TreeNode * t)
{t->bf=high(t->left)-high(t->right);
}
void func(TreeNode * t)
{if(t!=NULL){func(t->left);func(t->right);visit(t);}
}
int main(int argc, char** argv) {TreeNode *bt=CreateBTree();func(bt);PutTree(bt);return 0;
}
运行结果
输入1 2 3 -1 4 -1 -1 -1 5 6 7 -1 -1 -1 8 -1 9 -1 -1
按照先序遍历的顺序建立二叉树(其中字符’-1’代表空节点)
