一、遍历二叉树
1.定义
二叉树的遍历(travering binary tree)是指从根结点出发。依照某种次序依次訪问二叉树中的全部结点，使得每一个结点被訪问一次且仅被訪问一次。
2.前序遍历
(1)规则：若二叉树为空。则空操作返回。
否则，先訪问根结点，然后前序遍历左子树，再前序遍历右子树。
(2)实例
前序遍历结果为：A
BDGH CEIF
分析：当最先訪问根结点后。然后前序遍历左子树。当訪问根的左子树时。这里"前序遍历"即我们将B如果为左子树的根来遍历。
(3)算法
从二叉树定义可知，其是用递归的方式。所以，实现遍历算法也能够採用递归。
<span style="font-size:18px;">/*二叉树的前序遍历递归算法*/
void PreOrderTraverse(BiTree T)
{
if(T==NULL) //若树为空，返回为空
return;
printf("%c",T->data); //显示结点数据，能够更改为其它对结点操作
PreOrderTraverse(T->lchild); //再先遍历左子树
PreOrderTraverse(T->rchild); //最后遍历右子树
}</span>实例分析：
如上图所看到的，当调用PreOrderTraverse(T)函数时，程序执行步骤例如以下：
a)调用PreOrderTraverse(T),T根结点不为null,所以运行printf。打印字母A;
b)然后，调用PreOrderTraverse(T->lchild)。訪问A结点的左孩子，B结点不为null，运行printf打印出B;
c)此时再次递归调用PreOrderTraverse(T->lchild)，訪问了B结点的左孩子，运行printf打印字母D;
d)再次运行PreOrderTraverse(T->lchild)，訪问D结点的左孩子。运行printf打印字母G;
e)再次运行PreOrderTraverse(T->lchild)。訪问G结点的左孩子，因为G结点没有左孩子，则返回为空，所以T==null,返回此函数。此时调用PreOrderTraverse(T->rchild),訪问D结点的右孩子，运行printf打印字母H;
f).......依次继续打印后面字母就可以。
3.中序遍历
(1)规则：若树为空，则空操作返回。否则，从根结点開始(注意并非先訪问根结点)，中序遍历根结点的左子树，然后是訪问根结点。最后中序遍历右子树。
(2)实例
中序遍历结果为：GDHB
A EICF
(3)算法
<span style="font-size:18px;">/*二叉树的中序遍历递归算法*/
void InOrderTraverse(BiTree T)
{
if(T == NULL)
return;
InOrderTraverse(T->lchild); //中序遍历左子树
printf("%c",T->data); //显示结点数据，能够更改为其它对结点操作
InOrderTraverse(T->rchild); //最后中序遍历右子树
}</span>4.后序遍历
(1)规则：若树为空，则空操作返回。否则。从左到右先叶子后结点的方式遍历訪问左右子树，最后是訪问根结点。
(2)实例
后序遍历结果为：GHDB
IEFC A
(3)算法
<span style="font-size:18px;">/*二叉树的后序遍历递归算法*/
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild);//先后序遍历左子树
PostOrderTraverse(T->rchild);//再后序遍历右子树
printf("%c",T->data); //显示结点数据。能够更改为其它对结点操作
}</span>5.层序遍历
(1)规则：若树为空，则空操作返回。
否则，从树的第一层，也就是根结点開始訪问。从上而下逐层遍历，在同一层中。按从左到右的顺序对结点逐个訪问。
(2)实例
层序遍历结果为：A
BC DEF GHI
二、推导遍历结果
二叉树遍历性质：
(1)已经前序遍历序列和中序遍历序列，能够唯一确定一颗二叉树;
(2)已经后序遍历序列和中序遍历序列。能够唯一确定一颗二叉树;
1.假设已经一颗二叉树的前序遍历序列为ABCDEF,中序遍历序列为CBAEDF，请问这颗二叉树的
后序遍历结果是多少？
分析：
2.如果一颗二叉树的中西序列是ABCDEFG,后序序列是BDCAFGE，求前序序列？
分析：
三、二叉树的建立
对于一颗普通的二叉树，我们需将二叉树中每一个借点的空指针引出一个虚结点，其值为一特定值，比方"#"。
我们称这样的处理后的二叉树为原二叉树的扩展二叉树，扩展二叉树能够通过一个"前序"或"中序"或"后序"遍历序列确定一颗二叉树。
(1)扩展二叉树的前序遍序列为：AB#D##C##
(2)实现算法
<span style="font-size:18px;">/*按前序输入而二叉树中借点的值(一个字符)
* 当中，#表示空树，构造二叉链表表示二叉树T
*/
void CreateBitree(Bitree *T)
{
TElemType ch;
scanf("%c",&ch); //输入结点数据字符
if(ch=='#')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode)); //为数据为字符的结点在内存中分配空间
if(!*T) //假设分配未成功则异常结束(内存溢出)
exit(OVERFLOW);
(*T)->data = ch; //生成根结点
CreateBiTree(&(*T)->lchild); //构造左子树
CreateBiiTree(&(*T)->rchild); //构造右子树
}
}</span>总结：实际上。建立二叉树也是利用了递归的远离，仅仅只是在原来应该是打印结点的地方改成了生成结点、给结点赋值操作而已。
另外。我们也能够通过中序或后序遍历的方式实现二叉树的建立，仅仅只是代码里生成的结点和构造左右字子树的代码顺序交换一下就可以。
四、线索二叉树
对于一个有n个结点的二叉链表。每一个结点有指向左右孩子的两个指针域，所以一共是2n个指针域。而n个结点的二叉树一共同拥有n-1条分支线(根结点无前驱)，也就是说。事实上存在2n-(n-1)=n+1个空指针域。因为这些空间不存储不论什么事物。这样会导致内存资源的浪费。
另外。在二叉链表上，我们仅仅能知道每一个结点指向其左右孩子结点的地址。而不知道某个结点的前驱是谁。后继是谁。
想要知道，就必须遍历一次链表。以后每次须要知道时，都必须先遍历一次。为了提供内存空间的利用率和节省操作时间，我们能够考虑在创建就明白结点的前驱和后继。
1.线索二叉树
假设将指向前驱和后驱的指针称为线索，那么加上线索的二叉链表则称为线索链表；加上线索的二叉树就称之为线索二叉树(Threaded
Binary Tree)，对二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化。通过线索二叉树，我们对它进行遍历就等于操作一个双向链表结构，从而大大提高了訪问速度。
如上图二叉树按中序遍历后：HDIBJE
A FCG，空指针指(结点rchild指针或lchild指针)向的后继或前驱。
2.线索二叉树结点结构与实现
(1)结点结构
因为无法知道某一结点的lchild是指向它的左孩子还是指向前驱。rchild是指向右孩子还是指向后继。
因此。我们在每一个结点再增设两个标志域ltag和rtag，须要注意的是ltag和rtag仅仅是存放0或1数字的布尔型变量，其占用的内存空间要小于像lchild和rchild的指针变量。
结点结构例如以下：
(2)线索二叉树结构实现
<span style="font-size:18px;">/*二叉树的二叉线索存储结构定义
* Link==0表示左右孩子指针
* Thread==1表示指向前驱或后驱的线索
*/
typedef eum {Link,Thread} PointerTag;
typedef struct BiThrNode /*二叉线索存储结点结构*/
{
TElemType data; //数据域：结点数据
struct BiThrNode *lchild,*rchild; //指针域：左右孩子指针
PointerTag LTag;
PointerTag RTag; //左右标志
}BiThrNode,*BiThrTree;</span>3.中序遍历线索化的递归函数(难点)
线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。
因为前驱和后继的信息仅仅有在遍历该二叉树时才干得到，所以线索化的过程就是在遍历的过程中改动空指针的过程。
中序遍历线索化的递归函数代码例如以下：
BiThrTree pre; //全局变量。始终指向刚刚訪问过的结点
/*中序遍历进行中序线索化*/
void InThreading(BitThrTree p)
{
if(p)
{
InThreading(p->lchild); //递归左子树线索化
if(!p->lchild) //结点无左孩子
{
p->LTag=Thread; //前驱线索：将结点左指针标志置1，说明左指针指向该结点的前驱
p->lchild=pre; //左孩子指针指向前驱
}
if(!pre->rchild) //前驱没有右孩子
{
pre->RTag=Thread; //后继线索
pre-rchild=p; //前驱右孩子指针指向后继(当前结点p)
}
pre=p; //保持pre指向p的前驱
InThreading(p->rchild); //递归右子树线索化
}
}
源代码分析：
(1)结点前驱线索化
if(!p->lchild)表示假设某结点的左指针域为空，由于其前驱节点刚刚訪问过，赋值给了pre，所以能够将pre赋值给p->lchild。并改动p->LTag=Thread(也就是定义为1)以完毕前驱结点的线索化。
(2)结点后驱线索化
因为该节点还没有訪问到，因此仅仅能对它的前驱结点pre的右指针rchild做推断，if(!pre->rchild)表示假设为空。则p就是pre的后继，于是pre->rchild=p，而且设置pre->RTag=Thread。完毕后继结点的线索化。
(3) pre=p语句的作用是完毕前驱和后继的推断后，将当前的结点p赋值给pre。以便下一次使用。
4.中序遍历线索二叉树T的非递归算法
二叉树的二叉线索存储表示（以中序为例）：在线索链表上加入一个头结点，并令其lchild域的指针指向二叉树的根结点。其rchild域的指针指向中序遍历时訪问的最后一个结点。令二叉树中序串行中的第一个结点的lchild域指针和最后一个结点的rchild域的指针均指向头结点。这样就创建了一个双向线索链表。这样定义的优点是既能够从第一个结点起顺后继进行遍历。也能够从最后一个结点起顺前驱进行遍历。
/*T指向头结点，头结点左键lchild指向根结点，头结点右链rchild指向中序遍历的最后一个结点
* 中序遍历二叉线索链表表示的二叉树T，时间复杂度为O(n)*/
Status InOrderTraverse_Thr(BiThTree T)
{
BiThrTree p;
p=T->lchild; //p指向根结点
while(p != T) //空树或遍历结束时。p==T
{
while(p->LTag==Link) //当LTag==0时循环到中序序列第一个结点
p=p->lchild;
printf("%c",p->data); //显示结点数据，能够更改为其它对结点操作
while(p->RTag == Thread && p->rchild !=T)
{
p=p->rchild;
printf("%c",p->data);
}
p=p->rchild; //p进至其右子树根
}
}
源代码分析：
(1) p=T->lchild。让p指向根结点開始遍历，如上图编号①所看到的;
(2)while(p!=T)：即循环直到图中的④的出现，此时意味着p指向了头结点，于是与T相等(T是指向头结点的指针)。结束循环。否则一直循环下去去进行遍历操作;
(3)while(p->LTag==Link) 循环，就是由A->B->D->H，此时H结点的LTag不是Link(就是不等于0)，所以结束此循环并打印H;
(4)while(p->RTag == Thread && p->rchild !=T)，由于结点H的RTag==Thread(就是等于1)，且不是指向头结点。
因此打印H的后继D,之后由于D的RTag是Link，因此退出循环;
(5)p=p->rchild，即p指向了结点D的右孩子。
.....................不断循环，直到打印出HDIBJEAFCG结束遍历操作。
总结：二叉树的线索化有利于节省空间和时间，在实际问题中，假设所用的二叉树需常常遍历或查找结点时须要某种遍历序列中的前驱和后继，那么採用线索二叉链表的存储结构是一个很不错的选择。