数据结构-二叉树遍历总结
二叉树结构
二叉树是一种特殊的树，每个父结点最多只能用有两个子结点。
在树中，按照结点的“继承”关系可以分为父结点和子结点； 按照结点的位置关系可以分为根结点，中间结点和叶结点。 其中叶结点没有子结点。 我们用结点中的数字代表结点，那么在上图中：10为根结点；6、14为中间结点；4、8、12、16为叶节点。
二叉树存储结构
二叉树结构可以使用链式和顺序两种方式实现，其中比较常用的链式存储结构：
链式结构
typedef char TElemType;
typedef struct BiTNode /* 结点结构 */
{
TElemType data; /* 结点数据 */
struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;也可以写成这样，更清晰一些：
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode* lchild;
struct BiTNode* rchild;
}BiTNode;
typedef BiTNode* BiTree; 顺序结构
#define LENGTH 100
typedef char datatype;
typedef struct node{
datatype data;
int lchild,rchild;
int parent;
}Node;
Node tree[LENGTH];
int length;
int root; 本质上是一个结构体数组。
二叉树遍历
在二叉树中最重要的操作大概就是遍历，如链表这样的数据结构，遍历的方式是唯一的，因为我们只知道链表的头结点，遍历到一个结点时也只知道下一个结点（单链表），但是在树中却有多种遍历方式，通常有： 前序遍历：根结点—>左子结点—>右子结点，10、6、4、8、14、12、16； 中序遍历：左子结点—>根结点—>右子结点，4、6、8、10、12、14、16； 后序遍历：左子结点—>右子结点—>根结点，4、8、6、12、16、14、10； 层序遍历：第一层—>第二层—>第n层，10、6、14、4、8、12、16；
代码实现
遍历操作可以使用循环和递归的方式实现，其中递归可以使代码变的很简洁易懂，同样树的结构越复杂，递归的层数就会越深，但是总体上递归的方法更常用。
前序遍历：
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}中序遍历：
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return;
InOrderTraverse(T->lchild); /* 中序遍历左子树 */
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}后序遍历：
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild); /* 先后序遍历左子树 */
PostOrderTraverse(T->rchild); /* 再后序遍历右子树 */
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
}以上三种遍历方式很相似，只是递归的输入不同，而这就决定着遍历的顺序，我们拿前序遍历举个例子：
还是上面这个图，此时函数的输入为树的根结点，这是一个BiTree 类型的变量，前面定义了它是一个指针，打印10，此时没有进入递归，深度为0：
执行PreOrderTraverse(T->lchild)递归两次后打印6、4，此时打印6的那次递归深度是1，打印4的递归深度是2：
此时执行PreOrderTraverse(T->lchild)，但是4没有左子结点，进入一下第3层递归又退出回到第2层，执行PreOrderTraverse(T->rchild)但是4没有右子结点，进入一下第3层递归又退出回到第2层，此时结点4已经执行完了，返回第1层（结点6），执行PreOrderTraverse(T->rchild)，打印8：
递归又到了第2层，显然又要退回到第1层，但是到了第1层发现第1层也执行完了，退回到第0层（结点10），执行PreOrderTraverse(T->rchild)，打印14，于是后面就一样了，直到打印了16之后，从第2层开始退出，退到第0层之后发现第0层也执行完了：
最后，树的层序遍历与上面三种遍历方式不同，而且也不仅仅能用在二叉树，这个在本博客中先不涉及，后面补上。
其他操作
二叉树除了遍历外，还有一些其他的基本操作：
构建空二叉树：
typedef int Status;
Status InitBiTree(BiTree *T)
{
*T=NULL;
return OK;
}销毁二叉树：
void DestroyBiTree(BiTree *T)
{
if(*T)
{
if((*T)->lchild) /* 有左孩子 */
DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
if((*T)->rchild) /* 有右孩子 */
DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
free(*T); /* 释放根结点 */
*T=NULL; /* 空指针赋0 */
}
}创建二叉树：
void CreateBiTree(BiTree *T)
{
TElemType ch;
ch=str[index++];
if(ch=='#')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
if(!*T)
exit(OVERFLOW);
(*T)->data=ch; /* 生成根结点 */
CreateBiTree(&(*T)->lchild); /* 构造左子树 */
CreateBiTree(&(*T)->rchild); /* 构造右子树 */
}
}判断二叉树是否存在：
Status BiTreeEmpty(BiTree T)
{
if(T)
return FALSE;
else
return TRUE;
}返回二叉树深度：
int BiTreeDepth(BiTree T)
{
int i,j;
if(!T)
return 0;
if(T->lchild)
i=BiTreeDepth(T->lchild);
else
i=0;
if(T->rchild)
j=BiTreeDepth(T->rchild);
else
j=0;
return i>j?i+1:j+1;
} 腾讯云开发者
