二叉树相关知识

一. 二叉树的遍历
前序、中序以及后序遍历
学习二叉树结构，最简单的方式就是遍历。二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

以下图的二叉树为例:

从上到下依次是前序、中序以及后序,N为空指针NULL每个红方格对应一个流程.

void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}

printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}

以上前序遍历的代码

void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}

InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}

以上是中序遍历的代码,后序的代码类似不再展示.

二. 计算二叉树中节点的数目

int TreeSize(BTNode* root)
{
return root == NULL ? 0 :
TreeSize(root->left) + TreeSize(root->right) + 1;
}

注意用静态的处理方法是不行的,如果多次运行就会出问题.

如果多次运行会出现以下情况:

由于递归的使用,会出现叠加的状况

三. 二叉树中叶子节点的数目

int TreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;

if (root->left == NULL && root->right == NULL)
return 1;

return TreeLeafSize(root->left)
+ TreeLeafSize(root->right);
}

四.二叉树高度的计算

int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;

int leftHeight = TreeHeight(root->left);
int rightHeight = TreeHeight(root->right);

return leftHeight > rightHeight ?
leftHeight + 1 : rightHeight + 1;
}

// 有效率问题
int TreeHeight(BTNode* root)
{
if (root == NULL)
return 0;

return TreeHeight(root->left) > TreeHeight(root->right) ?
TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
}

这里我直接展示了两段代码,其中第一段代码是更优的,时间复杂度为O(N)
第二段是O(2^N).

其中都有
return TreeHeight(root->left) > TreeHeight(root->right) ?
TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;

问题：在判断 > 时，已经调用了一次 TreeHeight(root->left) 和 TreeHeight(root->right)。然后在返回值里，又再次调用了这两个函数。

这意味着：同一棵子树被递归计算了两次，时间复杂度从 O (n) 变成了 O (2ⁿ)，在树比较深时效率会急剧下降。而第一段的优点就是先把左右子树的高度计算出来，存到变量 leftHeight 和 rightHeight 里。之后只需要比较和返回，每个子树只计算一次，时间复杂度是标准的 O (n)，效率更高。

总结:二叉树中大量使用了递归的方法,而递归的关键就是:
明确函数意义：先定义清楚这个递归函数到底要解决什么问题，返回值代表什么。
找到终止条件：确定问题规模缩小到什么程度时，可以直接给出答案，不再递归。
建立递推关系：思考如何用子问题的结果，组合出当前问题的答案。
😊😊😊