Make Progress

0%

二叉树的应用

发表于 分类于

1. 判断两棵二叉树是否相同

情况1：左右子结点不可旋转
情况2：左右子结点可旋转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool is_equal(BiTree* node1,BiTree* node2){
	if(node1==NULL && node2==NULL)
		return 1;
	if( !node1 || !node2)
		return 0;
	if(node1->data == node2->data)
		return is_equal(node1->lchild,node2->rchild)&&is_equal(node1->rchild,node2->rchild);
	else 
		return 0;
	/*
	若可旋转，return 语句改为
	return (is_equal(node1->lchild,node2->lchild)&&is_equal(node1->rchild,node2->rchild)) || (is_equal(node1->lchild,node2->rchild)&&is_equal(node1->rchild,node2->lchild))
	*/
}

2. 求二叉树的深度

从根结点到叶结点经过的最长路径即为深度
本质上为二叉树后序遍历

1
2
3
4
5
6
7
8
9
10
int tree_height(BiTree* root){
	int left,right;
	if(root == NULL)
		return -1;
	else{
		left = tree_height(root->lchild) + 1;
		right = tree_height(root->rchild) + 1;
		return (left > right) ? left : right;	
	}
}

3. 求二叉树中结点的最大距离

情况A：路径经过左子树的最深结点，通过根结点，再到右子树的最深结点
情况b：路径不穿过根结点，而是左子树或右子树的最大距离路径，取其大者

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//A需要子树的最大深度，B需要子树的最大距离
//使函数能在一个结点同时计算及传回这两个信息
struct RESULT{//定义返回结果
	int nMaxDistance;//最大距离
	int nMaxDepth;//最大深度
};
RESULT GetMaxDistance(BiTree* root){
	if(!root){
		RESULT empty = {0,-1};//最大深度初始化为-1，是因为调用者要对其加1，然后变为0；
		return empty;
	}
	RESULT lhs = GetMaxDistance(root -> lchild);
	RESULT rhs = GetMaxDistance(root -> rchild);
	RESULT result;
	result.nMaxDepth = max(lhs.nMaxDepth + 1,rhs.nMaxDepth +1);
	result.nMaxDistance = max(max(lhs.nMaxDistance,lhs.nMaxDistance),lhs.nMaxDepth+lhs.nMaxDepth+2);
	return result;
}

4. 判断一棵树是不是二叉排序树

//二叉排序树的中序遍历结点值是从小到大有序的，根据此原理写出如下算法，时间复杂度O(n);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int prev1 = INT_MIN;//定义为最小的整数
int JudgeBST(BiTree* bt){
	int b1,b2;
	if(bt == NULL)
		return 1;
	else{
		b1 = JudgeBST(bt -> lchild);
		if(b1 == 0||prev1 >= bt->data);
			return 0;
		prev1 = bt -> data;
		b2 = JudgeBST(bt -> rchild);
		return b2;
	}	
}

4. 判断一颗二叉树是不是平衡二叉树

求出根节点的最大深度与最小深度，则最大深度与最小深度之差dis就是树中任一子树深度差最大值；只要dis小于等于1，就是平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxDepth(BiTree* root){
	if(root == NULL)
		return 0;
	return 1 + max(maxDepth(root->lchild),maxDepth(root->rchild));
}
int minDepth(BiTree* root){
	if(root == NULL)
		return 0;
	return 1 + min(minDepth(root->lchild),minDepth(root->rchild));
}
bool isBalanced(BiTree* root){
	return (maxDepth(root) - minDepth(root) <= 1);
}