【数据结构】二叉树的中序遍历

冷不防 2022-09-30 13:49 95阅读 0赞

树的遍历是指访问树的每一个结点，且每一个结点只被访问一次。访问是一个抽象的概念，实际上可以是对结点数据的各种处理，比如输出结点信息或更改结点信息。根据二叉树的构成以及结点的访问顺序，遍历可分为4种方式：先序遍历，中序遍历，后序遍历和层序遍历。  
中序遍历是指对树中任意结点的访问总是在遍历完其左子树之后进行的，访问此结点后再遍历其右子树。遍历从根结点开始，遇到每个节点遍历过程如下：

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

![这里写图片描述][SouthEast]

如上图所示二叉树，其遍历结果为： 4 8 2 5 1 9 6 10 3 7  
（此处访问节点定义为输出结点数据）

如上过程用递归可以很方便地实现，代码如下：  
`二叉树的结构定义`

typedef struct TreeNode * BinTree;
    struct TreeNode{
        int Date;
        struct TreeNode *Left;
        struct TreeNode *Right;
    };

`中序遍历函数`

void InOderTraversal(BinTree BT)
    {
        if(BT){
            InOderTraversal(BT->Left);
            printf("%d ", BT->Date);
            InOderTraversal(BT->Right);
        }
    }

递归程序虽然简洁，但是执行效率不高，所以下面给出非递归算法。由图可知，三种遍历的路线是一样的：都是从根结点开始沿左子树深入下去，当深入到最左端，无法继续深入下去时，则沿原路返回，每遇到一个结点便进入其右子树，如此地深入和返回，直到最后从根结点的右子树返回根节点为止。先序遍历是在深入时遇到结点就访问，中序遍历是在从左子树返回时遇到结点就访问，后序遍历是从右子树返回时遇到结点就访问。  
在这一过程中，返回结点的顺序与进入节点的顺序相反，即后进入先返回，正好符合堆栈结构后进先出的特点。由此，可以利用堆栈实现这一遍历路线。  
在中序遍历二叉树时，遇到一个结点，就把它入栈，并去遍历它的左子树；当左子树便利结束后，从栈顶弹出并访问这个结点，然后按其右指针中序遍历该结点的右子树。  
代码如下：  
（代码中栈的实现参见之前关于链栈的博文）

void InOrderTraversal(BinTree BT)
    {
        BinTree T;
        Stack S;
        S = CreateStack();
        T = BT;
        while(T || !IsEmpty(S)){
            while(T){
                Push(S,T);
                T = T->Left;
            }
            if(! IsEmpty(S)){
                T = Pop(S);
                printf("%d ", T->Date);
                T = T->Right;
            }
        }
    }

[SouthEast]: /images/20220705/e3ccff26ef1b4cb2a98570e7fbae56f4.png