2.61 二叉树的前中后序遍历
二叉树一般不进行增删查改操作，（堆的话可以，这里就不多说了）一般就进行前中后序，以及求树的高度等。
1. NLR ：前序遍历 (Preorder Traversal 亦称先序遍历 )—— 访问根结点的操作发生在遍历其左右子树之前。
在进行前序遍历之前我们的自己构建一个二叉树：
BTNode* A = (BTNode*)malloc(sizeof(BTNode)); if (A) { A->left = NULL; A->right = NULL; A->val = 'A'; } BTNode* B = (BTNode*)malloc(sizeof(BTNode)); if (B) { B->left = NULL; B->right = NULL; B->val = 'B'; } BTNode* C = (BTNode*)malloc(sizeof(BTNode)); if (C) { C->left = NULL; C->right = NULL; C->val = 'C'; } BTNode* D = (BTNode*)malloc(sizeof(BTNode)); if (D) { D->left = NULL; D->right = NULL; D->val = 'D'; } BTNode* E = (BTNode*)malloc(sizeof(BTNode)); if (E) { E->left = NULL; E->right = NULL; E->val = 'E'; } BTNode* F = (BTNode*)malloc(sizeof(BTNode)); if (F) { F->left = NULL; F->right = NULL; F->val = 'F'; } BTNode* G = (BTNode*)malloc(sizeof(BTNode)); if (G) { G->left = NULL; G->right = NULL; G->val = 'G'; } BTNode* H = (BTNode*)malloc(sizeof(BTNode)); if (H) { H->left = NULL; H->right = NULL; H->val = 'H'; } A->left = B; A->right = C; B->left = D; B->right = E; E->right = H; C->left = F; C->right = G;
前序遍历的代码：
void PrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%c ", root->val); PrevOrder(root->left); PrevOrder(root->right); }
这里我们用了分治的思想来处理问题，先访问根（打印结点上的数据），然后访问左子树，访问右子树，不断递归下去，直到访问到NULL。
来看看结果：
同理，中序遍历和后序遍历也是一样的方法：
2. LNR：中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
具体代码：
void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%c ", root->val); InOrder(root->right); }
结果展示：
3. LRN：后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
具体代码：
void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%c ", root->val); InOrder(root->right); }
结果展示：
求结点的个数：
具体代码：
int NodeSize(BTNode* root) { return root == NULL ? 0 : NodeSize(root->left) + NodeSize(root->right) + 1; }
这种方法求解节点的个数是比较简洁的，你也可以用count计数，但是要传入地址，还有尽量不要用全局变量，这样做可能会有隐患。如果不太理解上面递归是怎样实现的，最好画递归图来帮助理解。
求叶子结点的个数：
具体代码：
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 maxDepth(struct TreeNode* root){ if(root==NULL) { return 0; } int maxLeft=maxDepth(root->left); int maxRight=maxDepth(root->right); return maxLeft>maxRight?maxLeft+1:maxRight+1; }
注意这里求的是最大深度，不是结点个数，只需要统计出最大值就好了。
2.62 二叉树的层序遍历
层序遍历 ：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为 1 ，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然 后从左到右访问第 2 层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问 树的结点的过程就是层序遍历。
二叉树的层序遍历这里我们用队列来实现：
具体思路：
先让根入队列，然后再让根出队列，当左子树不为NULL时让左子树入队列，当右子树不为NULL时让右子树入队列，然后不断迭代下去，直至队列为空。记得出队列前要保存当前值来访问到该元素，pop到队列当中的值是地址，通过该地址来访问其中的val.
具体代码：
void LevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root); } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); printf("%c ", front->val); if (front->left) { QueuePush(&q, front->left); } if (front->right) { QueuePush(&q, front->right); } } printf("\n"); QueueDestroy(&q); }
当然，自己要实现一个队列：具体实现方法可以参照上一篇博客：戳这里
结果展示：
3 二叉树相关题练习
1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（）
A 不存在这样的二叉树
B 200
C 198
D 199
解题思路：
这里我们引用二叉树的一些性质：
1. 若规定根节点的层数为 1 ，则一棵非空二叉树的 第 i 层上最多有 2^(i-1) 个结点。
2. 若规定根节点的层数为 1 ，则 深度为 h 的二叉树的最大结点数是 2^h- 1。
3. 对任何一棵二叉树 , 如果度为 0 其叶结点个数为 n0, 度为 2 的分支结点个数为 n2, 则有 n0＝n2＋1 。
4. 若规定根节点的层数为 1 ，具有 n 个结点的满二叉树的深度 ， h=LogN。
这里用第三个性质可以知道该题选B
2. 在具有 2 n 个结点的完全二叉树中，叶子结点个数为（）
A n
B n + 1
C n - 1
D n / 2
解题思路：
这个题我们不妨假设叶子结点个数为x,则度为2的结点个数为x-1,由于题目给的是完全二叉树，所以度为1的结点个数只能为0或者1，则由已知条件可列：x+x-1+0（1）=x,由于n只能是整数，所以度为1的结点个数只能取1，故x=n,选A.
3.一棵完全二叉树的节点数位为531个，那么这棵树的高度为( )
A 11
B 10
C 8
D 12
解题思路：
我们不妨假设这棵树的高度为x,最后一层缺失的结点个数为y,则y的取值为[0,2^(h-1)-1],
由已知可列：2^h-1-y=531,结合y的取值我们可以代值进去，选项B符合题意。
解题思路：
为了空间的不浪费，我们首先求出该树的结点个数，通过该节点个数来malloc想要的空间大小，由于我们想要把数据存放到数组中，所以为了不重复malloc，我们分装了一个函数来帮助我们完成前序遍历。
具体代码：
int TreeSize(struct TreeNode* root) { return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1; } PrevOrder(struct TreeNode* root,int*a,int*pc) { if(root==NULL) return ; a[*pc]=root->val; (*pc)++; PrevOrder(root->left,a,pc) ; PrevOrder(root->right,a,pc) ; } int* preorderTraversal(struct TreeNode* root, int* returnSize){ int sz=TreeSize(root); int* a=(int*)malloc(sizeof(int)*sz); int count=0; PrevOrder(root,a,&count); * returnSize=count; return a; }
中序与后续遍历也是一样的分析方法，只是遍历的顺序不一样。
解题思路：
平衡二叉树就是一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 ，我们可以求出左子树的最大高度以及右子树的最大高度来比较，然后不断递归下去，直至满足平衡二叉树的条件。
具体代码：
int maxDepth(struct TreeNode* root){ if(root==NULL) { return 0; } int maxLeft=maxDepth(root->left); int maxRight=maxDepth(root->right); return maxLeft>maxRight?maxLeft+1:maxRight+1; } bool isBalanced(struct TreeNode* root){ if(root==NULL) { return true; } int leftDepth=maxDepth(root->left); int rightDepth=maxDepth(root->right); return abs(leftDepth-rightDepth)<2 && isBalanced(root->left) && isBalanced(root->right); }
好了，今天的分享就到这里了，希望大佬们多多支持下，如果哪里有什么不对的地方欢迎佬们评论区中指出哦。
