二叉树相关性质及其遍历
目录
一.二叉树的性质
性质1.二叉树第i层结点数
性质2.深度为k二叉树结点数
性质3.度为0和2的结点数量关系
性质4.完全二叉树的深度
性质5.双亲结点与孩子结点的下标关系
二.二叉树的遍历及其建立
1.二叉树结点的建立
2.前序遍历
编辑
3.中序遍历
编辑
4.后序遍历
5.层序遍历
6.求二叉树结点的个数
7.求二叉树的高度
8.求二叉树第k层结点个数
9.求二叉树叶子结点的个数
10.遍历二叉树寻找数据
一.二叉树的性质
性质1.二叉树第i层结点数
结论：在二叉树的第 i 层上至多有 2^(i - 1) 个结点（i≥1)
证明如下：二叉树的第一层（i = 1）时，最多有 2^(1 - 1) = 1 个结点，也就是根结点。当第二层（i = 2）时，最多就有 2^(2 - 1) = 2 个结点。第三层（i = 3）时，最多能有 2^(3 - 1) = 4 个结点，以此类推。每一层可容纳的结点数是按照以 2 为底数的指数形式增长，层数越高，理论上能容纳的最多结点数就越多，这是因为二叉树每个结点最多有两个子结点，每往下一层就可以在之前的基础上翻倍扩展结点数量。
性质2.深度为k二叉树结点数
结论：深度为 k 的二叉树至多有 2^k - 1 个结点（k≥1）
证明如下：这里说的深度就是从根结点到叶结点最长路径上的结点数。比如深度为 1 的二叉树，最多就是 1 个结点（也就是根结点本身，计算可得 2^1 - 1 = 1）；深度为 2 的二叉树，最多有 2^2 - 1 = 3 个结点（即根结点加上它的两个子结点）；深度为 3 的二叉树，最多会有 2^3 - 1 = 7 个结点，是把各层最多的结点数累加起来（1 + 2 + 4 = 7，等同于公式计算结果）。可以理解为把每层按照性质 1 中每层最多结点数进行求和，利用等比数列求和公式能推导出这样的结果。
性质3.度为0和2的结点数量关系
结论：对任何一棵二叉树 T，如果其终端结点数为 n₀，度为 2 的结点数为 n₂，则 n₀ = n₂ + 1
证明如下：终端结点就是叶结点，也就是没有子结点的那些结点。度为 2 的结点是指有左右两个子结点的结点。我们可以通过分析二叉树中结点之间的分支关系来推导这个性质。在二叉树里，除了根结点外，每个结点都有且仅有一个分支指向它，设二叉树的总分支数为 B。那么从结点角度来看，总分支数 B 等于所有结点的度数之和（因为每个度为 1 的结点贡献 1 个分支，度为 2 的结点贡献 2 个分支等），同时总分支数 B 又等于总结点数减 1 （因为除根结点外每个结点都对应一个分支进入它）。设度为 1 的结点数为 n₁，总结点数 N = n₀ + n₁ + n₂，总分支数 B = n₁ + 2×n₂ ，又因为 B = N - 1 = n₀ + n₁ + n₂ - 1，将 B = n₁ + 2×n₂ 代入可得：n₁ + 2×n₂ = n₀ + n₁ + n₂ - 1，经过化简就能得到 n₀ = n₂ + 1 。
性质4.完全二叉树的深度
结论：具有 n 个结点的完全二叉树的深度为⌊log₂n⌋ + 1
证明如下：完全二叉树是一种特殊形态的二叉树，它除了最后一层外，每一层的结点数都达到了最大值，最后一层的结点从左到右依次排列。根据前面性质 2 知道深度为 k 的二叉树最多有 2^k - 1 个结点，对于完全二叉树来说，结点数 n 是介于深度为 k - 1 的二叉树最多结点数和深度为 k 的二叉树最多结点数之间，即 2^(k - 1) - 1 < n ≤ 2^k - 1 ，对这个不等式进行变形和推导，两边同时加 1 可得 2^(k - 1) < n + 1 ≤ 2^k ，然后取以 2 为底的对数可得 k - 1 < log₂(n + 1) ≤ k ，由于 k 是整数，所以 k = ⌊log₂n⌋ + 1（这里⌊ ⌋表示向下取整），也就是其深度的计算方式。
性质5.双亲结点与孩子结点的下标关系
如果对一棵有 n 个结点的完全二叉树（其深度为⌊log₂n⌋ + 1）的结点按层序编号（从第 1 层到第⌊log₂n⌋ + 1 层，每层从左到右），则对任一结点 i（1≤i≤n），有以下关系：
如果 i = 1，则结点 i 是二叉树的根，无双亲；如果 i > 1，则其双亲结点是⌊i / 2⌋
证明如下：在完全二叉树按层序编号规则下，根结点编号为 1 ，自然无双亲。对于其他结点，因为是按顺序一层一层从左到右编号的，通过观察和分析可以发现，任意一个非根结点的双亲结点编号正好是它自身编号除以 2 向下取整得到的结果。比如编号为 3 的结点，它的双亲就是编号为⌊3 / 2⌋ = 1（也就是根结点）的结点；编号为 6 的结点，双亲就是编号为⌊6 / 2⌋ = 3 的结点。
如果 2i > n，则结点 i 无左孩子（结点 i 为叶结点）；否则其左孩子是结点 2i
证明如下：按照编号和结点对应关系，左孩子的编号在顺序上正好是双亲编号的 2 倍，但是要考虑到可能出现的情况，当 2i 大于总结点数 n 时，意味着这个位置超出了实际存在的结点范围，那就说明该结点 i 没有左孩子，本身就是叶结点了；如果 2i 不超过 n ，那编号为 2i 的结点就是结点 i 的左孩子，例如在有 7 个结点的完全二叉树中，结点 3 的左孩子就是结点 2×3 = 6 。
如果 2i + 1 > n，则结点 i 无右孩子；否则其右孩子是结点 2i + 1
证明如下：
同理，右孩子的编号在顺序上是双亲编号的 2 倍再加 1，当 2i + 1 大于总结点数 n 时，说明不存在对应的右孩子结点了，该结点 i 就只有左孩子或者本身就是叶结点；如果 2i + 1 不超过 n ，那么编号为 2i + 1 的结点就是结点 i 的右孩子，比如在上述 7 个结点的完全二叉树中，结点 3 的右孩子就是结点 2×3 + 1 = 7 。
二.二叉树的遍历及其建立
1.二叉树结点的建立
这里我们使用链式结构来构建二叉树，链式的缺点是不支持随机访问，但是相比较于顺序的二叉树而言，在不知道具体的结点个数的情况下，链式二叉树可以随时扩容，下面我们给出链式二叉树的BTNode结点结构体定义：
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;对于创建一个二叉树结点来说，我们只需要malloc开辟一块新空间作为新的二叉树结点，将左孩子和右孩子指针置为空，将数据放入结点中去，再返回新结点的地址：
BTNode* BuyBTNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc failed");return NULL;}newnode->data = x;newnode->left = NULL;newnode->right = NULL;return newnode;
}这里我们手动创建一个链式二叉树，并将其各个结点连接起来，如下：
int main()
{BTNode* n1 = BuyBTNode(1);BTNode* n2 = BuyBTNode(2);BTNode* n3 = BuyBTNode(3);BTNode* n4 = BuyBTNode(4);BTNode* n5 = BuyBTNode(5);BTNode* n6 = BuyBTNode(6);n1->left = n2;n2->left = n3;n1->right = n4;n4->left = n5;n4->right = n6;return 0;
}2.前序遍历
这里我们选择将NULL打印出来，并且要使用递归的操作，
1.先将当前结点作为根节点，判断根节点是否为空，如果为空就打印出来；
2.打印当前结点的数据；
3.将当前结点左孩子当成下一节点的根节点，使用递归函数；
4.将当前结点右孩子当成下一节点的根节点，使用递归函数；
原理图：
//前序遍历
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%-4d ", root->data);PreOrder(root->left);PreOrder(root->right);
}
3.中序遍历
这里原理与前面一样，重复相同的操作，我们只需调换一下打印当前结点数据和第一次递归调用函数即可：
1.先将当前结点作为根节点，判断根节点是否为空，如果为空就打印出来；
2.将当前结点左孩子当成下一节点的根节点，使用递归函数；
3.打印当前结点的数据；
4.将当前结点右孩子当成下一节点的根节点，使用递归函数；
//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%-4d ", root->data);InOrder(root->right);
}
4.后序遍历
同理：
1.先将当前结点作为根节点，判断根节点是否为空，如果为空就打印出来；
2.将当前结点左孩子当成下一节点的根节点，使用递归函数；
3.将当前结点右孩子当成下一节点的根节点，使用递归函数；
4.打印当前结点的数据；
//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%4d ", root->data);
}
5.层序遍历
我们通常需要借助队列来实现层序遍历。队列是一种先进先出（FIFO）的数据结构。首先将根节点入队，然后每次从队头取出一个节点，访问该节点，接着将它的左子节点和右子节点（如果存在）依次入队。如此循环，直到队列为空，如果对队列的实现还不了解，可以看这一专栏前面的内容，里面有对链式队列实现的具体讲解，这里我们就不做过多赘述，直接使用：
使用队列，如果根节点存在的话，我们就将根节点入队列，如果队列不为空的话，我们每次出队列后打印出队列这一元素的数据，然后将左右孩子分别入队列（哪个孩子结点存在就入哪个，都存在就依次入队列），这样循环一直到队列为空，就实现了层序遍历：
//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if (front->left){QueuePush(&q,front->left);}if (front->right){QueuePush(&q,front->right);}}QueueDestroy(&q);
}
6.求二叉树结点的个数
这里我们还是使用递归，如果根结点为NULL，我们就返回0，否则就返回左子树的结点加上右子树的结点加上自身1，为了简洁明了我们使用三目操作符，如下：
//结点个数
int TreeSize(BTNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}7.求二叉树的高度
双重递归，如果根结点为空，我们返回0，接着比较左子树和右子树的高度，选择较大的一方进行返回，并加上根结点所在的一层高度1，如下：
//二叉树的高度
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;
}8.求二叉树第k层结点个数
双重递归，如果k此时为1，我们设置一个递归出口，这时就说明已经递归到二叉树最上层，也就是根节点所在的那一层，我们返回1，其他我们返回左子树第k-1层的结点个数+右子树第k-1层的结点个数：
//第k层节点个数
int TreekNode(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return TreekNode(root->left, k - 1) + TreekNode(root->right, k - 1);
}9.求二叉树叶子结点的个数
同样书双重递归，我们对根节点的度进行一个判断，如果这个结点不存在左孩子和右孩子，那么度为0，是我们要找的叶子结点，返回1，其他情况我们返回左子树寻找到的叶子结点个数+右子树寻找到的叶子结点个数即可：
//求二叉树叶子结点的个数
int TreeLeafNum(BTNode* root)
{if (root==NULL){return 0;}else{if (root->left == NULL && root->right == NULL){return 1;}else{return TreeLeafNum(root->left) + TreeLeafNum(root->right);}}
}10.遍历二叉树寻找数据
双重递归，我们先对根节点进行判断，如果为空，那么就返回空指针，这也是递归出口，如果根节点的数据刚好是要寻找的数据，我们就返回根节点的地址，其他情况，我们返回到左子树寻找的结果| |右子树寻找的结果，这里只要一方找到就算寻找到，注意不要写成&&！
//寻找数据
BTNode* TreeFind(BTNode* root, int x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}return TreeFind(root->left, x) == NULL ? TreeFind(root->right, x) : TreeFind(root->left, x);
}
二叉树的内容展示更新到这里，如果觉得对你有帮助，别忘了支持~
