一、遍历二叉树
1.定义 二叉树的遍历(travering binary tree)是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。
2.前序遍历
(1)规则：若二叉树为空，则空操作返回。否则，先访问根结点，然后前序遍历左子树，再前序遍历右子树。
(2)实例
前序遍历结果为：A BDGH CEIF 分析：当最先访问根结点后，然后前序遍历左子树。当访问根的左子树时，这里"前序遍历"即我们将B假设为左子树的根来遍历。
(3)算法 从二叉树定义可知，其是用递归的方式，所以，实现遍历算法也可以采用递归。
/*二叉树的前序遍历递归算法*/
void PreOrderTraverse(BiTree T)
{
if(T==NULL) //若树为空，返回为空
return;
printf("%c",T->data); //显示结点数据，可以更改为其他对结点操作
PreOrderTraverse(T->lchild); //再先遍历左子树
PreOrderTraverse(T->rchild); //最后遍历右子树
}
实例分析： 如上图所示，当调用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)算法
/*二叉树的中序遍历递归算法*/
void InOrderTraverse(BiTree T)
{
if(T == NULL)
return;
InOrderTraverse(T->lchild); //中序遍历左子树
printf("%c",T->data); //显示结点数据，可以更改为其他对结点操作
InOrderTraverse(T->rchild); //最后中序遍历右子树
}
4.后序遍历
(1)规则：若树为空，则空操作返回。否则，从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。
(2)实例
后序遍历结果为：GHDB IEFC A
(3)算法
/*二叉树的后序遍历递归算法*/
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild);//先后序遍历左子树
PostOrderTraverse(T->rchild);//再后序遍历右子树
printf("%c",T->data); //显示结点数据，可以更改为其他对结点操作
}
5.层序遍历
(1)规则：若树为空，则空操作返回。否则，从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
(2)实例
层序遍历结果为：A BC DEF GHI
二、推导遍历结果 二叉树遍历性质： (1)已经前序遍历序列和中序遍历序列，可以唯一确定一颗二叉树; (2)已经后序遍历序列和中序遍历序列，可以唯一确定一颗二叉树; 1.假设已经一颗二叉树的前序遍历序列为ABCDEF,中序遍历序列为CBAEDF，请问这颗二叉树的 后序遍历结果是多少？ 分析： 2.假设一颗二叉树的中西序列是ABCDEFG,后序序列是BDCAFGE，求前序序列？ 分析：
三、二叉树的建立 对于一颗普通的二叉树，我们需将二叉树中每个借点的空指针引出一个虚结点，其值为一特定值，比如"#"。我们称这种处理后的二叉树为原二叉树的扩展二叉树，扩展二叉树可以通过一个"前序"或"中序"或"后序"遍历序列确定一颗二叉树。 (1)扩展二叉树的前序遍序列为：AB#D##C## (2)实现算法
/*按前序输入而二叉树中借点的值(一个字符)
* 其中，#表示空树，构造二叉链表表示二叉树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); //构造右子树
}
}
总结：实际上，建立二叉树也是利用了递归的远离，只不过在原来应该是打印结点的地方改成了生成结点、给结点赋值操作而已。另外，我们也可以通过中序或后序遍历的方式实现二叉树的建立，只不过代码里生成的结点和构造左右字子树的代码顺序交换一下即可。
四、线索二叉树 对于一个有n个结点的二叉链表，每个结点有指向左右孩子的两个指针域，所以一共是2n个指针域。而n个结点的二叉树一共有n-1条分支线(根结点无前驱)，也就是说，其实存在2n-(n-1)=n+1个空指针域。由于这些空间不存储任何事物，这样会导致内存资源的浪费。另外，在二叉链表上，我们只能知道每个结点指向其左右孩子结点的地址，而不知道某个结点的前驱是谁，后继是谁。想要知道，就必须遍历一次链表，以后每次需要知道时，都必须先遍历一次。为了提供内存空间的利用率和节省操作时间，我们可以考虑在创建就明确结点的前驱和后继。
1.线索二叉树 如果将指向前驱和后驱的指针称为线索，那么加上线索的二叉链表则称为线索链表；加上线索的二叉树就称之为线索二叉树(Threaded Binary Tree)，对二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化。通过线索二叉树，我们对它进行遍历就等于操作一个双向链表结构，从而大大提高了访问速度。 如上图二叉树按中序遍历后：HDIBJE A FCG，空指针指(结点rchild指针或lchild指针)向的后继或前驱。
2.线索二叉树结点结构与实现
(1)结点结构 由于无法知道某一结点的lchild是指向它的左孩子还是指向前驱，rchild是指向右孩子还是指向后继