二叉树的递归遍历

二叉树的结构定义

typedef struct TNode *Position;
typedef Position BinTree;

 // 二叉树树节点的定义
struct TNode {
    ElementType Data;  // 节点数据
    BinTree Left;  // 左子树
    BinTree Right;  // 右子树
};

二叉树的遍历

对二叉树的遍历是指访问树的每个结点，且每个结点仅被访问一次。访问是一个抽象的概念，实际上可以对结点数据的各种处理，比如输出结点信息。下面的遍历都是先遍历左子树再遍历右子树，根据访问其结点的先后进行区分

中序遍历

中序遍历是指对树中任一结点的访问是在遍历完其左子树后进行的，访问此结点后再对其右子树遍历。从根结点开始，遇到每个结点是，做以下处理：

1. 中序遍历其左子树
2. 访问根结点
3. 中序遍历其右子树

void InOrderTraversal( BinTree BT )
{
    if ( BT ) {
        InOrderTraversal( BT->Left );  //1
        printf( "%d", BT->Data );  //2
        InOrderTraversal( BT->Right  );  //3
    }
}

先序遍历

先序遍历是指对结点的访问是再其左、右子树遍历之前进行的。从根结点开始，遇到每个结点是，做以下处理：

1. 访问根结点
2. 先序遍历其左子树
3. 先序遍历其右子树

void InOrderTraversal( BinTree BT )
{
    if ( BT ) {
        printf( "%d", BT->Data );  //1
        InOrderTraversal( BT->Left );  //2
        InOrderTraversal( BT->Right  );  //3
    }
}

后续遍历

后续遍历是指结点左、右子树的遍历先进行，然后才是对此节点的访问。从根结点开始，遇到每个结点是，做以下处理：

1. 后续遍历其左子树
2. 后续遍历其右子树
3. 访问根结点

void InOrderTraversal( BinTree BT )
{
    if ( BT ) {
        InOrderTraversal( BT->Left );  //1
        InOrderTraversal( BT->Right  );  //2
        printf( "%d", BT->Data );  //3
    }
}

下图为对该二叉树进行各种遍历的结果：

遍历结果.jpg