这就是我们的大致思路，而要实现这个首先，我们得导入我们队列，导入之后，我们需要修改的部分就是这两个，前置声明，因为我们的树是在他的里面定义的，所以在队列的头文件里面是不认识树结点的，所以我们得先声明一下，定义就在后面让他去找去。
所以他最终的代码为
//层序遍历 void LevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root != NULL) { QueuePush(&q, root); } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); printf("%c ", front->date); if (root->left != NULL) { QueuePush(&q, front->left); } if (root->right != NULL) { QueuePush(&q, front->right); } } printf("\n"); QueueDestory(&q); }
运行结果为
5.二叉树的销毁
想要销毁这颗二叉树，那么我们就必须得使用后序的方式来进行销毁，如果根节点是NULL，那么什么也不用做，如果不是空，那么就先销毁他的左子树，然后销毁右子树，最后销毁该结点。如此递归下去即可，代码如下
void DestoryTree(BTNode* root) { if (root == NULL) { return; } DestoryTree(root->left); DestoryTree(root->right); free(root); root = NULL; }
6.二叉树的一些选择题
1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（ ）
A、 ABDHECFG B、 ABCDEFGH C、 HDBEAFCG D、 HDEBFGCA
对于这道题，最关键的部分是完全二叉树这几个字眼。由此我们直接得出该完全二叉树的图
而他的先序遍历我们很容易就得知，A B D H E C F G
所以选A
2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为 （）
A、E B、 F C、 G D、 H
对于这道题其实不用中序遍历我们也能做出来，因为我们知道先序遍历第一个肯定是根节点，所以就直接得出答案为E
但是呢我们也要知道先序遍历和中序遍历其实是可以确定一个二叉树的。我们现在画出他的二叉树，首先先序遍历我们可以确定根，所以我们知道首先有一个根E，有了根以后，我们根据这个根在中序遍历中的位置就能确定出左右区间，所以HFI部分为左子树，JKG部分为右子树。而HFI这一部分我们又回到先序遍历中，我们可以看出F是根，我们由这个F是根又回到中序遍历中确定他的左右子树区间，我们不难得出，H就是F的左子树，I就是F的右子树。同理，我们可以得出JKG部分的结构，G为根节点，J和K都是左子树部分，而JK部分中，J又是根节点，而K 是J 的右子树
最终我们得出这颗二叉树为
3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为____。
A、 adbce B、 decab C、 debac D、 abcde
这道题和上一道题是一样的，我们可以根据中序遍历和后序写出他的二叉树。这里直接给出他的二叉树
所以他的先序遍历为abcde
7.牛客题目之二叉树遍历
在这里也给出一道题
题目链接：二叉树遍历_牛客题霸_牛客网
题目描述：
（1）思路分析
首先我们先将思路给理清楚，二叉树的中序遍历并不难，难的是如何根据输入的字符串去构建二叉树。他的构建过程是这样的，因为他是根据先序遍历来构建的，那么第一个a肯定就是根结点，然后第二个b就是左子树的根节点，如此下来，c也是b的左子树的根结点，这时候我们该看c的左子树了，但是下一个数据是#，也就是说c的左子树是一个空，那么就该插入c的右子树了，而这个右子树恰好也是一个空。所以就返回到b的右子树了，b的右子树是一个d，d的左子树是一个e，e的左子树又是空，e的右子树是g，g的左右子树都是空。所以现在回到了d的右子树了，d的右子树刚好是一个f，而f的左右子树都是空，所以现在回到了a，a的右子树是一个空。
这样一来二叉树就构建完成了，如下图所示
有了二叉树构建完成，那么这道题简直就是易如反掌了
（2）解题代码
#include <stdio.h> #include <stdlib.h> typedef struct TreeNode { struct TreeNode* left; struct TreeNode* right; char val; }TreeNode; TreeNode* CreateTree(char* str,int* i) { if(str[*i]=='#') { (*i)++; return NULL; } TreeNode* root=(TreeNode*)malloc(sizeof(TreeNode)); if(root==NULL) { printf("malloc fail\n"); exit(-1); } root->val=str[*i]; (*i)++; root->left=CreateTree(str,i); root->right=CreateTree(str,i); return root; } void InOrder(TreeNode* root) { if(root==NULL) { return ; } InOrder(root->left); printf("%c ",root->val); InOrder(root->right); } int main() { char str[101]={0}; scanf("%s",str); int i=0; TreeNode* root = CreateTree(str,&i); InOrder(root); return 0; }
四、哈夫曼树的建立以及编码
在这里也简单提及一下哈夫曼树，实际上哈夫曼树应用并不多。一般只应用于文件压缩。在这里简单的提及一下哈夫曼树的建立以及他的编码
假设我们有如下四个结点，a、b、c、d相当于他们的编号，7、5、2、4则是他们的权值，我们利用这四个结点来构造一颗哈夫曼树
我们的构造过程是这样的，先找出最小的和次最小的两个结点，然后让最小的放在左边，次最小的放在右边，然后再他们这两个结点上面构造一个双亲结点。这个双亲结点的权值是他们两个的权值之和
然后接下来将这个6这个结点和剩余的结点放在一块，找出他们的最小的两个结点，同样最小的放在左边，次最小的放在右边
跟上面同样的道理，继续将剩余的找出最小的两个
这样一来，我们就构建出哈夫曼树了，上面的就是哈夫曼树
有了哈夫曼树，我们还会对其进行编码，我们将每一个左子树编码为0，右子树编码为1
有了这些编码，我们就可以知道每一个结点的编码是多少了
比如a的编码为0、b的编码为10、c的编码为110、d的编码为111
而这些编码就是哈夫曼编码
这棵树也叫做加权路径最优二叉树，也就是所有原结点的权值*路径长度和最小
即：权值越大、路径越短、编码越短；权值越小、路径越长、编码越长。
总结
本小节讲解了树的概念，二叉树的性质，二叉树的先序中序后序层序遍历以及计算叶子结点，总结点个数的实现,最后还有哈夫曼树的建立以及编码
如果对你有帮助，不要忘记点赞加收藏哦！！！
想获得更多优质的内容， 一定不要忘记关注我哦！！！
