数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码（上）：https://developer.aliyun.com/article/1513431
4.3求二叉树第k层结点个数
求当前树的第k层结点个数=其左子树第k-1层结点个数+其右子树第k-1层结点个数，k=1时返回1
比如上图K=3,求A的第3层结点个数就是求B的第2层的节点+C的第2层的结点。
int TreeKLevelSize(BTNode* root, int k) { assert(k > 0); if (root == NULL) //空结点返回0 { return 0; } if (k == 1) { return 1; } return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1); }
4.4查找树里面值为x的那个结点
思路：空就返回空，找到了就返回这个结点，没找到就到左子树和右子树去找，都没找到就返回空
BTNode* TreeFind(BTNode* root, BTDataType x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } BTNode* lret = TreeFind(root->left, x); if (lret) { return lret; } BTNode* rret = TreeFind(root->right, x); if (rret) { return rret; } return NULL; }
比如要找E的位置：（找不到前都返回空）
4.5 二叉树销毁
这里采用后序遍历的销毁方式，因为用前序和中序要保存结点。
// 一般，如果选择一级指针，存在野指针问题，调用BinaryTreeDestory的人，把指针置空 // 这样保持接口的一致性 void BinaryTreeDestory(BTNode* root) { if (root == NULL) { return; } BinaryTreeDestory(root->left); BinaryTreeDestory(root->right); //printf("%p %c\n", root, root->data); free(root); root = NULL; }
前面函数的代码和测试：
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef char BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; // 记录左节点 struct BinaryTreeNode* right; // 记录右节点 BTDataType data; // 存储数据 } BTNode; //创建新节点 BTNode* CreateNode(BTDataType x) { BTNode* new_node = (BTNode*)malloc(sizeof(BTNode)); if (new_node == NULL) { printf("malloc failed!\n"); exit(-1); } new_node->data = x; new_node->left = new_node->right = NULL; return new_node; } //手动创建二叉树 BTNode* CreateBinaryTree() { BTNode* nodeA = CreateNode('A'); BTNode* nodeB = CreateNode('B'); BTNode* nodeC = CreateNode('C'); BTNode* nodeD = CreateNode('D'); BTNode* nodeE = CreateNode('E'); BTNode* nodeF = CreateNode('F'); nodeA->left = nodeB; // A nodeA->right = nodeC; // B C nodeB->left = nodeD; // D E F nodeC->left = nodeE; nodeC->right = nodeF; return nodeA; } //二叉树前序遍历 void PreOrder(BTNode* root) { //首先判断根是否为空，为空就返回 if (root == NULL) { printf("NULL "); // 暂时打印出来，便于观察 return; } //走到这里说明不为空，根据前序遍历，先访问根节点 printf("%c ", root->data); //然后遍历左子树（利用递归） PreOrder(root->left); //最后遍历右子树（利用递归） PreOrder(root->right); // A // B C // D E F 前序： 根 左 右 //执行输出： A B D NULL NULL NULL C E NULL NULL F NULL NULL } //二叉树中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%c ", root->data); InOrder(root->right); // A // B C // D E F 中序：左 根 右 //执行输出：NULL D NULL B NULL A NULL E NULL C NULL F NULL } //二叉树后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%c ", root->data); // A // B C // D E F 后序：左 右 根 //执行输出：NULL NULL D NULL B NULL NULL E NULL NULL F C A } 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 TreeKLevelSize(BTNode* root, int k) { assert(k > 0); if (root == NULL) { return 0; } if (k == 1) { return 1; } return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1); } // 查找树里面值为x的那个节点 BTNode* TreeFind(BTNode* root, BTDataType x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } BTNode* lret = TreeFind(root->left, x); if (lret) { return lret; } BTNode* rret = TreeFind(root->right, x); if (rret) { return rret; } return NULL; } // 一般，如果选择一级指针，存在野指针问题，调用BinaryTreeDestory的人，把指针置空 // 这样保持接口的一致性 void BinaryTreeDestory(BTNode* root) { if (root == NULL) { return; } BinaryTreeDestory(root->left); BinaryTreeDestory(root->right); //printf("%p %c\n", root, root->data); free(root); root = NULL; } int main() { BTNode* root = CreateBinaryTree(); PreOrder(root); printf("\n"); InOrder(root); printf("\n"); PostOrder(root); printf("\n"); printf("TreeSize:%d\n", TreeSize(root)); printf("TreeLeafSize:%d\n", TreeLeafSize(root)); printf("TreeKLevelSize:%d\n", TreeKLevelSize(root, 3)); printf("TreeFind:%p\n", TreeFind(root, 'E')); printf("TreeFind:%p\n", TreeFind(root, 'F')); printf("TreeFind:%p\n", TreeFind(root, 'X'));//打印0 ：找不到 BinaryTreeDestory(root); root = NULL; return 0; }
5.二叉树广度优先遍历
5.1层序遍历
层序遍历（Level Traversal）：设二叉树的根节点所在的层数为1的情况下，
从二叉树的根节点出发，首先访问第1层的树根节点，然后再从左到右访问第2层上的节点。
接着是第3层的节点……以此类推，自上而下、从左向右地逐层访问树的节点。
该如何实现层序遍历呢？ 可以利用队列的性质来实现。
之前再讲过队列，这里你可以选择自己实现一个队列。
如果不想实现就直接复制即可，因为这里重点要学的是层序遍历。
这里就先不实现了，下一篇写写二叉树OJ，下下篇再实现（最下面已附链接）
6.笔试选择题
练习1：
2-3树是一种特殊的树，它满足两个条件：
(1) 每个内部结点有两个或三个子结点
(2) 所有的叶结点到根的距离相同
如果一颗2-3树有10个结点，那么它有( )个叶结点。
A.7
B.8
C.7 或 8
D.6
练习2：
设某种二叉树有如下特点：每个结点要么是叶子结点，要么有2棵子树。假如一棵这样的二叉树中有m（m>0）个叶子结点，那么该二叉树上的结点总数为（ ）
A.2m+1
B.2(m-1)
C.2m-1
D.2m
练习3：
设根结点的深度为1，则一个拥有n个结点的二叉树的深度一定在（ ）区间内
A.[log(n + 1)，n]
B.[logn，n]
C.[log(n + 1)，n - 1]
D.[log(n + 1)，n + 1]
练习4：
对任意一颗二叉树，设N0、N1、N2分别是度为0、1、2的结点数，则下列式子中一定正确的是（ ）
A.N0 = N2 + 1
B.N1 = N0 + 1
C.N2 = N0 + 1
D.N2 = N1 + 1
练习5：
二叉树的( )遍历相当于广度优先遍历，( )遍历相当于深度优先遍历
A.前序 中序
B.中序 前序
C.层序 后序
D.层序 前序
练习6：
如果一颗二叉树的前序遍历的结果是ABCD，则满足条件的不同的二叉树有（ ）种
A.13
B.14
C.15
D.16
答案：
1.答案：D
根据题目意思，每一个非叶子节点至少有两个孩子节点，并且叶子节点都在同一层，所以，假设树的高度为h， 则二三树种最小的节点个数为满二叉树的个数：2^h - 1, 最大个数： (3^h - 1) / 2。所以 2^h - 1 < 10 < (3^h - 1) / 2, h为3，结构是1(3(2,2,2))。所以叶节点个数为6
2.答案：C
根据二叉树的性质，在任意的二叉树中，度为0的节点比度为2的节点多了1个----见课件
现在叶子节点为m个，即度为0的节点有m个，那度为2的节点个数就为m-1个
而题目说该二叉树中只有度为2和度为0的节点 ，因此总的节点数就为：m+m-1 = 2m-1
3答案：A
最大深度： 即每次只有一个节点，次数二叉树的高度为n，为最高的高度
最小深度： 此树为完全二叉树， 如果是完全二叉树
根据二叉树性质，完全二叉树的高低为 h = log(n+1)向上取整
4答案：A
节点总数N： N = N0 + N1 + N2
度和边的关系： N - 1 = 0 * N0 + 1 * N1 + 2 * N2
上面两个式子可以推出： N0 + N1 + N2 - 1 = N1 + 2 * N2
可得： N0 = N2 + 1
5答案：D（前中后序遍历都可以称为深度优先遍历，但是单选的话就选前序）
广度优先需要把下一步所有可能的位置全部遍历完，才会进行更深层次的遍历，
层序遍历就是一种广度优先遍历。
深度优先是先遍历完一条完整的路径（从根到叶子的完整路径），才会向上层折返，
再去遍历下一个路径，前序遍历就是一种深度优先遍历。
6答案：B
首先这棵二叉树的高度一定在3~4层之间:
三层：
A(B(C,D),()), A((),B(C,D)), A(B(C,()),D), A(B((),C),D),
A(B,C(D,())), A(B,C((),D))
四层：
如果为四层，就是单边树，每一层只有一个节点，除过根节点，其他节点都有两种选择，
在上层节点的左边还是右边，所以2*2*2共8种，总共为14种。
