昨天的数据结构讲座，学长讲了二叉树这方面的知识，今天又复习了一下，赶紧记下来。
二叉树的定义
二叉树是n个结点的集合，可以为空，也可以由一个根结点和两棵互不相交的左，右子树组成。
二叉树的特点
1. 每个结点最多有两颗子树（是最多有）。
2. 左右子树有顺序，不能随意颠倒（哪怕其中那个结点只有一颗子树，也要区分是左子树还是右子树）。
现在让我们正式开始讲一下各种操作
先来看一张整体的效果图
数据结构
typedef struct node
{
char data;
struct node *lchild,*rchild;
}Tree;
1. 首先，我们需要一颗二叉树，所以最开始我们先来建立一个二叉树。
我们要先得到原二叉树的扩展二叉树（将原二叉树中每个结点的空指针引出一个虚结点，给其一确定值（如"#"）），然后我们就能做到一个遍历序列确定一颗二叉树了。
我们以前序建树为例，所以我们应该输入 ABD#F##E##C##。
void CreatBiTree(Tree **root)
{
char ch;
scanf("%c",&ch);
if(ch == '#')
*root = NULL;
else
{
*root = (Tree *)malloc(sizeof(Tree));
(*root)->data = ch;
CreatBiTree(&(*root)->lchild);
CreatBiTree(&(*root)->rchild);
}
}
注：1. 建立二叉树也是利用递归，和递归遍历差距不大，只不过在原来打印结点的地方改成了生成结点，给结点赋值。
2. 中序，后序建树也可以，代码其实差不多，要提前知道其遍历树顺序就好。
2. 建好一颗树后，我们就来看一下遍历（递归 and 非递归）
先来说一下前序，中序，后序遍历。它们3个的递归遍历基本一样，核心就是3行代码，只不过调整一下顺序，递归比较简洁明了，但是效率却比较低（而且别人要是让你写一个二叉树的遍历，你上去直接递归感觉有点不够高级…），所以非递归的就来了，前，中，后序的非递归实现要借助栈（递归遍历也是系统调用栈来实现），可以自己来用c语言来实现一个栈，但c++有封装好的 stack，所以我就直接用了。
前序遍历
递归：
根 -> 左 -> 右
非递归：
从根结点开始，先判断是否为空，不为空就先访问（打印）该结点，然后入栈，接着遍历左子树；为空时让栈顶元素出栈，并以其为父结点访问其右子树，直到当前节点为空且栈为空时结束。
void PreOrderTra(Tree *root)
{
Tree *p = root;
if(p == NULL)
return;
printf("%c ",p->data);
PreOrderTra(p->lchild);
PreOrderTra(p->rchild);
}
//非递归
void PreOrderTra_fdg(Tree *root)
{
stack<Tree *> s;
Tree *p = root;
while(p || !s.empty())
{
if(p)
{
printf("%c ",p->data);
s.push(p); //入栈
p = p->lchild; //沿左子树
}
else
{
p = s.top(); //取出
s.pop(); //出栈
p = p->rchild; //向右
}
}
}
中序遍历
递归：
左 -> 根 -> 右
非递归：
和前序遍历差不多，只不过访问节点的顺序不一样，访问节点的时机是从栈中弹出元素时访问，如果从栈中弹出元素，就意味着当前节点的父结点的左子树已经遍历完成，这时候再进行访问。
void InOrderTra(Tree *root)
{
Tree *p = root;
if(p == NULL)
return;
InOrderTra(p->lchild);
printf("%c ",p->data);
InOrderTra(p->rchild);
}
//非递归
void InOrderTra_fdg(Tree *root)
{
stack<Tree *> s;
Tree *p = root;
while(p || !s.empty())
{
if(p)
{
s.push(p); //入栈
p = p->lchild;
}
else
{
p = s.top(); //取出
printf("%c ",p->data);
s.pop(); //出栈
p = p->rchild;
}
}
}
后序遍历
递归：
左 -> 右 -> 根
非递归：
对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，或者都已被访问过了，就可以直接访问该结点。如果有孩子未访问，将P的右孩子和左孩子依次入栈（一定要是先右后左，因为访问的时候是从左孩子开始的）。定义两个指针，分别指向当前结点和之前访问过的结点，先将根结点入栈开始。
void PostOrderTra(Tree *root)
{
Tree *p = root;
if(p == NULL)
return;
PostOrderTra(p->lchild);
PostOrderTra(p->rchild);
printf("%c ",p->data);
}
//非递归
void PostOrderTra_fdg(Tree *root)
{
stack<Tree *> s;
Tree *p,*q;
p = q = NULL;
s.push(root);
while(!s.empty())
{
p = s.top();
if((p->lchild == NULL && p->rchild == NULL) || (q != NULL && (q == p->lchild || q == p->rchild)))
{
printf("%c ",p->data); //如果当前结点没有孩子或者孩子结点都已被访问过
s.pop(); //出栈
q = p; //记录上一次访问的结点
}
else //分别放入右左孩子
{
if(p->rchild != NULL)
s.push(p->rchild);
if(p->lchild != NULL)
s.push(p->lchild);
}
}
}
ok，了解了前序，中序，后序的遍历之后，再让我们来看一下层序遍历。我写了两种，一种用的数组，一种是 queue（都一样，只不过是借用数组来实现一个队列的功能）。借助队列来实现，还是比较好理解的，先将其父结点入队，然后将其左右孩子依次入队，队列未空就一直按顺序访问即可。
//层序遍历-（数组）
void LevelTra(Tree *root)
{
Tree *t[20]; //指针数组，存放二叉树结构体指针
int in,out;
in = out = 0;
t[in++] = root; //先保存根结点
while(in > out)
{
if(t[out])
{
printf("%c ",t[out]->data);
t[in++] = t[out]->lchild;
t[in++] = t[out]->rchild;
}
out++;
}
}
//层序遍历-（队列）
void LevelTra_dl(Tree *root)
{
queue<Tree *> s;
Tree *p = NULL;
if(root)
s.push(root); //根结点入队
while(!s.empty())
{
p = s.front();
printf("%c ",p->data);
if(p->lchild != NULL)
s.push(p->lchild);
if(p->rchild != NULL)
s.push(p->rchild);
s.pop();
}
}
3. 求一棵树的结点个数
注：3，4，5，6点都是递归实现的，有些相通的，理解了一个之后，看其它的会比较好理解。
用递归来实现，比较好理解，但是不是很好能想通（我开始是 printf 来的，感受每次递归时的变化）。结点如果为空返回 0，否则返回的是左右子树的结点和再 +1（要加上自己本身）。
int GetNodeNum(Tree *root)
{
if(root == NULL)
return 0;
int lNum = GetNodeNum(root->lchild);
int rNum = GetNodeNum(root->rchild);
//printf("%d %d\n",lNum,rNum);
return lNum + rNum + 1;
}
4. 求一棵树的深度
因为自己本身也占一层，所以返回时 +1。
int GetTreeDepth(Tree *root)
{
if(root == NULL)
return 0;
int lDepth = GetTreeDepth(root->lchild);
int rDepth = GetTreeDepth(root->rchild);
//printf("%d %d\n",lDepth,rDepth);
return lDepth > rDepth ? (lDepth + 1) : (rDepth + 1);
}
5. 求一棵树的叶子结点数
叶子结点：没有孩子的结点。
int GetLeafNodeNum(Tree *root)
{
if(root == NULL)
return 0;
if(root->lchild == NULL && root->rchild == NULL)
return 1;
int lNum = GetLeafNodeNum(root->lchild);
int rNum = GetLeafNodeNum(root->rchild);
return (lNum + rNum);
}
6. 求一棵树某一层的结点数
k 为要访问的那一层。
int GetNodeNumLevel(Tree *root, int k)
{
if(root == NULL || k < 1)
return 0;
if(k == 1)
return 1;
int lNum = GetNodeNumLevel(root->lchild,k - 1);
int rNum = GetNodeNumLevel(root->rchild,k - 1);
return (lNum + rNum);
}
7. 再完成了各种操作之后，一定不能忘记的就是要销毁二叉树了
void DeleteTree(Tree *root)
{
if(root == NULL)
return;
DeleteTree(root->lchild);
DeleteTree(root->rchild);
free(root);
}
以上便是我今天所总结的一些有关二叉树的操作，因为自己也比较菜，所以若是有什么地方有错误，请大家指正！
最后贴上我的主函数
需要注意的就是最后要让指针指向 NULL。
int main()
{
Tree *m_root = NULL;
int k;
int NodeNum,TreeDepth,LeafNodeNum,NodeNumLevel;
printf("创建二叉树: ");
CreatBiTree(&m_root);
printf("前序遍历（递归）: ");
PreOrderTra(m_root);
printf("\n");
printf("前序遍历（非递归）: ");
PreOrderTra_fdg(m_root);
printf("\n");
printf("中序遍历（递归）: ");
InOrderTra(m_root);
printf("\n");
printf("中序遍历（非递归）: ");
InOrderTra_fdg(m_root);
printf("\n");
printf("后序遍历（递归）: ");
PostOrderTra(m_root);
printf("\n");
printf("后序遍历（非递归）: ");
PostOrderTra_fdg(m_root);
printf("\n");
printf("层序遍历（数组）: ");
LevelTra(m_root);
printf("\n");
printf("层序遍历（队列）: ");
LevelTra_dl(m_root);
printf("\n");
printf("树的结点数: ");
NodeNum = GetNodeNum(m_root);
printf("%d\n",NodeNum);
printf("树的深度: ");
TreeDepth = GetTreeDepth(m_root);
printf("%d\n",TreeDepth);
printf("树的叶子结点数: ");
LeafNodeNum = GetLeafNodeNum(m_root);
printf("%d\n",LeafNodeNum);
printf("获取第几层的结点数: ");
scanf("%d",&k);
NodeNumLevel = GetNodeNumLevel(m_root,k);
printf("第%d层结点数为: %d\n",k,NodeNumLevel);
DeleteTree(m_root);
m_root = NULL; //防止野指针
return 0;
}
!@#$%^&*~