数据结构与算法-二叉树中序遍历

野性酷女 2022-05-29 11:00 223阅读 0赞

二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。因为树的定义本身就 是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历 中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。

包含的头文件：

#include <iostream>
    #include <stack>
    
    using namespace std;

定义二叉树节点：

struct BinaryTreeNode {
        int val;
        BinaryTreeNode *left;
        BinaryTreeNode *right;
        BinaryTreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

基于循环的二叉树中序遍历：

void InOrderTraversal_Recurrence(BinaryTreeNode *root){
        stack< BinaryTreeNode* > s;
        BinaryTreeNode *p=root;
        while(p!=NULL||!s.empty()){
            while(p!=NULL){
                s.push(p);
                p=p->left;
            }
            if(!s.empty()){
                p=s.top();
                cout<< p->val <<" ";
                s.pop();
                p=p->right;
            }
        }
    }

基于递归的二叉树中序遍历：

void InorderTraversal_Recursive(BinaryTreeNode* BT){
        if(BT){
            InorderTraversal_Recursive(BT->left);
            printf("%d ", BT->val);
            InorderTraversal_Recursive(BT->right);
        }
    }

创建的二叉树的形状：  
![这里写图片描述][Image 1]  
完整程序：

#include <iostream>
    #include <stack>
    
    using namespace std;
    
    struct BinaryTreeNode {
        int val;
        BinaryTreeNode *left;
        BinaryTreeNode *right;
        BinaryTreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    void InorderTraversal_Recursive(BinaryTreeNode* BT){
        if(BT){
            InorderTraversal_Recursive(BT->left);
            printf("%d ", BT->val);
            InorderTraversal_Recursive(BT->right);
        }
    }
    
    void InOrderTraversal_Recurrence(BinaryTreeNode *root){
        stack< BinaryTreeNode* > s;
        BinaryTreeNode *p=root;
        while(p!=NULL||!s.empty()){
            while(p!=NULL){
                s.push(p);
                p=p->left;
            }
            if(!s.empty()){
                p=s.top();
                cout<< p->val <<" ";
                s.pop();
                p=p->right;
            }
        }
    }
    
    int main(){
        BinaryTreeNode a(1);
        BinaryTreeNode b(2);
        BinaryTreeNode c(5);
        BinaryTreeNode d(3);
        BinaryTreeNode e(4);
        BinaryTreeNode f(6);
        a.left = &b;
        a.right = &c;
        b.left = &d;
        b.right = &e;
        c.right = &f;
        InorderTraversal_Recursive(&a);
        printf("\n");
        InOrderTraversal_Recurrence(&a);
        printf("\n");
        return 0;
    }

中序遍历的结果（递归和非递归）：

3 2 4 1 5 6 
    3 2 4 1 5 6

[Image 1]: