6.3树的存储结构( 五 ) _结点

6.6.2 二叉链表
既然顺序存储适用性不强，我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表
结构如图所示：
代码实现如下：
/*二叉树的二叉链表结点结构定义*/typedef struct BiTNode /* 结点结构*/{TElemType data;/*结点数据*/struct BiTNode *1child, *rchild; /*左右孩子指针*/} BiTNode, *BiTree;
结构下图：
如果有需要，还可以增加一个指向其双亲的指针域，那样就称之为三叉链表，很灵活要学会自己变通~~~~
6.7遍历二叉树 6.7.1 二叉树遍历原理
二叉树的遍历(tree )是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
访问和次序是关键！
6.7.2二叉树的遍历方法 1.前序遍历
规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树,再前序遍历右子树。如下图所示，遍历的顺序为:。
2.中序遍历
规则是若树为空，则空操作返回，否则**从根结点开始(注意并不是先访问根结点)，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。**如图所示、谝历的顺序为:。
3.后序遍历
规则是若树为空，则空操作返回，否则**从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。**如图所示，遍历的顺序为: .
4.层序遍历
规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。如图所示，遍历的顺序为:。
6.7.3前序遍历算法
二叉树的定义是递归的方式，所以实现算法也可以递归
/*二叉树的前序遍历递归算法*/void PreOrderTraverse ( BiTree T ){if( T==NULL)return;printf ( "&c",T->data) ;/*显示结点数据，可以更改为其他对结点操作*/PreOrderTraverse (T->lchild) ; /*先序遍历左子树*/PreOrderTraverse (T->rchild) ; /*最后先序遍历右子树*/}
可以简单的看个例子
一颗这样的二叉树T，如果要遍历它的话
1.调用 (T), T根结点不为null, 所以执行, 打印字母A
2.调用 (T->) ;访问了A结点的左孩子，不为null,执行
显示字母B
3.不断的递归调用 (T->)到H，此时为H结点无左孩子，所以T==null, 返回此函数，此时递归调用 (T->) ;访问了H结点的右孩子，显示字母K,
后面的话会不断的向前向左向右遍历
6.7.4中序遍历算法
/*二叉树的前序遍历递归算法*/void PreOrderTraverse ( BiTree T ){if( T==NULL)return;InOrderTraverse (T->lchild) ; /*中遍历左子树*/printf ( "&c",T->data) ;/*显示结点数据，可以更改为其他对结点操作*/InOrderTraverse (T->rchild) ; /*最后中序遍历右子树*/}
流传和上类似，都是不断的递归
6.7.5后序遍历算法
/*二叉树的前序遍历递归算法*/void PreOrderTraverse ( BiTree T ){if( T==NULL)return;InOrderTraverse (T->lchild) ; /*中遍历左子树*/InOrderTraverse (T->rchild) ; /*最后中序遍历右子树*/printf ( "&c",T->data) ;/*显示结点数据，可以更改为其他对结点操作*/}
6.7.6推导遍历结果
已知一棵二叉树的前序遍历序列为,中序遍历序列为，请问这棵二叉树的后序遍历结果是多少?（已知前中求后）
前序遍历是先打印在递归左跟右，所以前序遍历序列为，A就位根结点的数据。再由中序遍历序列可以CB是A的左子树，EDF是A的右子树