数据结构——二叉树的先序遍历、中序遍历、后序遍历（C++代码实现）

你的名字 2022-12-21 06:27 92阅读 0赞

# 什么是先序、中序、后序？ #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ3OTY1NTM3_size_16_color_FFFFFF_t_70_pic_center]  
如上图所示，是一个简单的二叉树，这三个名词中的序代表的当然是顺序的意思，并且是父亲结点与子节点之间输出的顺序。

1.  先序遍历，指的是父亲结点第一步输出，第二步输出左子结点，第三步输出右子结点。图中二叉树的先序遍历输出就会是这样：1->2->4->5->3->6->7
2.  中序遍历，指的是父亲结点在第二步输出，第一步输出左子结点，第三步输出右子结点。图中二叉树的中序遍历输出就会是这样：4->2->5->1->6->3->7
3.  后序遍历，指的是父亲结点在第三步输出，第一步输出左子结点，第二步输出右子结点。图中二叉树的后序遍历输出就会是这样：4->5->2->6->7->3->1

#include<iostream>
    using std::cout;
    using std::endl;
    class Node {
        //定义二叉树的结点类
    public:
        int data;//存储结点上的数据
        Node *lchild, *rchild;//指向左右子结点的指针变量
        Node(int _data) {
        
            data = _data;
            lchild = NULL;
            rchild = NULL;
        }
        ~Node() {
        
            if (lchild != NULL) delete lchild;
            if (rchild != NULL) delete rchild;
            //delete data;
        }
        void preorder() {
        
            cout << data << " ";//第一步输出父亲结点的值
            if (lchild != NULL) lchild->preorder();//第二步输出左子结点的值
            if (rchild != NULL) rchild->preorder();//第三步输出右子结点的值
        }
        void inorder() {
        
            if (lchild != NULL) lchild->inorder();//第一步输出左子结点的值
            cout << data << " ";//第二步输出父亲结点的值
            if (rchild != NULL) rchild->inorder();//第三步输出右子结点的值
        }
        void postorder() {
        
            if (lchild != NULL) lchild->postorder();//第一步输出左子结点的值
            if (rchild != NULL) rchild->postorder();//第二步输出右子结点的值
            cout << data << " ";//第三步输出父亲结点的值
        }
    };
    class BinaryTree {
        //定义二叉树类
    private:
        Node *root;//定义指向根结点的指针
    public:
        BinaryTree() {
        
            root = NULL;
        }
        ~BinaryTree() {
        
            delete root;
        }
        void build_demo() {
        //构建图中二叉树的样例
           	root = new Node(1);
            root->lchild = new Node(2);
            root->rchild = new Node(3);
            root->lchild->lchild = new Node(4);
            root->lchild->rchild = new Node(5);
            root->rchild->lchild = new Node(6);
            root->rchild->rchild = new Node(7);
        }
        void preorder() {
        
            root->preorder();
        }
        void inorder() {
        
            root->inorder();
        }
        void postorder() {
        
            root->postorder();
        }
    };
    int main() {
        
        BinaryTree binarytree;
        binarytree.build_demo();//构建图中二叉树的样例
        binarytree.preorder();//先序遍历
        cout << endl;
        binarytree.inorder();//中序遍历
        cout << endl;
        binarytree.postorder();//后序遍历
        cout << endl;
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ3OTY1NTM3_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/ad26123378b14076853626f91a6f5e78.png