二叉树的结构定义
typedef struct TNode *Position;
typedef Position BinTree;
// 二叉树树节点的定义
struct TNode {
ElementType Data; // 节点数据
BinTree Left; // 左子树
BinTree Right; // 右子树
};
二叉树的遍历
对二叉树的遍历是指访问树的每个结点，且每个结点仅被访问一次。访问是一个抽象的概念，实际上可以对结点数据的各种处理，比如输出结点信息。下面的遍历都是先遍历左子树再遍历右子树，根据访问其结点的先后进行区分
中序遍历
中序遍历是指对树中任一结点的访问是在遍历完其左子树后进行的，访问此结点后再对其右子树遍历。从根结点开始，遇到每个结点是，做以下处理：
- 中序遍历其左子树
- 访问根结点
- 中序遍历其右子树
void InOrderTraversal( BinTree BT )
{
if ( BT ) {
InOrderTraversal( BT->Left ); //1
printf( "%d", BT->Data ); //2
InOrderTraversal( BT->Right ); //3
}
}
先序遍历
先序遍历是指对结点的访问是再其左、右子树遍历之前进行的。从根结点开始，遇到每个结点是，做以下处理：
- 访问根结点
- 先序遍历其左子树
- 先序遍历其右子树
void InOrderTraversal( BinTree BT )
{
if ( BT ) {
printf( "%d", BT->Data ); //1
InOrderTraversal( BT->Left ); //2
InOrderTraversal( BT->Right ); //3
}
}
后续遍历
后续遍历是指结点左、右子树的遍历先进行，然后才是对此节点的访问。从根结点开始，遇到每个结点是，做以下处理：
- 后续遍历其左子树
- 后续遍历其右子树
- 访问根结点
void InOrderTraversal( BinTree BT )
{
if ( BT ) {
InOrderTraversal( BT->Left ); //1
InOrderTraversal( BT->Right ); //2
printf( "%d", BT->Data ); //3
}
}
下图为对该二叉树进行各种遍历的结果：
遍历结果.jpg
