二叉树的建立和遍历

r囧r小猫 2022-05-26 04:40 180阅读 0赞

# 一、基本概念 #

![BinaryTree.png][]

二叉树：每个结点的子结点个数不大于2的树，叫做二叉树。  
根结点：最顶部的那个结点叫做根结点，根结点是所有子结点的共同祖先。比如上图中的“7”结点就是根结点。  
子结点：除了根结点外的结点，都叫子结点。  
叶子结点：没有子结点的结点，叫做叶子结点。比如上图中的“1”结点、“5”结点和“11”结点。

二叉树的遍历，有三种：  
（1）前序遍历：先遍历根结点，再遍历左子树，最后遍历右子树。上图的前序遍历顺序为：7->4->1->5->12->8->11->13  
（2）中序遍历：先遍历左子树，再遍历根结点，最后遍历右子树。上图的中序遍历顺序为：1->4->5->7->8->11->12->13  
（3）后序遍历：先遍历左子树，再遍历右子树，最后遍历根结点。上图的后序遍历顺序为：1->5->4->11->8->13->12->7

二叉排序树：左子结点 <= 根结点 <= 右子结点的二叉树，叫做二叉排序树（或排序二叉树）。上图就是一个二叉排序树。

# 二、二叉树的建立和遍历 #

#include<iostream>
    using namespace std;
    
    struct BTreeNode                //定义二叉树结点的数据结构
    {
        int data;
        BTreeNode *leftChild;       //左子结点指针
        BTreeNode *rightChild;      //右子结点指针
    };
    
    class Btree
    {
        BTreeNode *root;            //根结点的指针，没写访问权限则为默认的private
    
    public:
        Btree()                     //构造函数
        {
            root = NULL;
        }
    
        void createBtree(int);
    
        void preOrder()                     //前序遍历方法，对外接口
        {
            preOrderTraverse(root);
            cout << endl;
        }
    
        void preOrderTraverse(BTreeNode *); //中序遍历具体过程
    
        void inOrder()                      //中序遍历方法，对外接口
        {
            inOrderTraverse(root);
            cout << endl;
        }
    
        void inOrderTraverse(BTreeNode *);  //中序遍历具体过程
    
        void postOrder()                    //后序遍历方法，对外接口
        {
            postOrderTraverse(root);
            cout << endl;
        }
    
        void postOrderTraverse(BTreeNode *);//后序遍历具体过程
    };
    
    void Btree::createBtree(int x)
    {
        BTreeNode *newnode = new BTreeNode;
        newnode->data = x;
        newnode->leftChild = NULL;
        newnode->rightChild = NULL;
    
        if(NULL == root)    //如果没有根结点，则第一个结点就是根结点
        {
            root = newnode;
        }
        else                //根据数值大小判断是左子结点还是右子结点
        {
            BTreeNode *father;
            BTreeNode *current = root;
    
            while(current != NULL)   //找到要插入newnode的节点指针
            {
                father = current;
                if(current->data > x)
                {
                    current = current->leftChild;
                }
                else
                {
                    current = current->rightChild;
                }
            }
    
            //newnode插入到father结点的左（或右）子结点位置
            if(father->data > x)
            {
                father->leftChild = newnode;
            }
            else
            {
                father->rightChild = newnode;
            }
        }
    }
    
    void Btree::preOrderTraverse(BTreeNode *root)
    {
        if(root)
        {
            cout << root->data << " ";
            preOrderTraverse(root->leftChild);
            preOrderTraverse(root->rightChild);
        }
    }
    
    void Btree::inOrderTraverse(BTreeNode *root)
    {
        if(root)
        {
            inOrderTraverse(root->leftChild);
            cout << root->data << " ";
            inOrderTraverse(root->rightChild);
        }
    }
    
    void Btree::postOrderTraverse(BTreeNode *root)
    {
        if(root)
        {
            postOrderTraverse(root->leftChild);
            postOrderTraverse(root->rightChild);
            cout << root->data << " ";
        }
    }
    
    int main()
    {
        Btree A;
        int arr[]={
       7, 4, 1, 5, 12, 8, 13, 11};
    
        //排序二叉树：左子结点<根节点<右子节点
        cout << "建立排序二叉树: ";
        int cnt = sizeof(arr) / sizeof(int);
        for(int i = 0; i < cnt; i++)
        {
            cout << arr[i] << " ";
            A.createBtree(arr[i]);
        }
        cout << endl;
    
        cout << "前序遍历: ";
        A.preOrder();
    
        cout << "中序遍历: ";
        A.inOrder();
    
        cout << "后序遍历: ";
        A.postOrder();
    
        return 0;
    }

运行结果：

建立排序二叉树： 7 4 1 5 12 8 13 11
    前序遍历：7 4 1 5 12 8 11 13
    中序遍历：1 4 5 7 8 11 12 13
    后序遍历：1 5 4 11 8 13 12 7

> TopCoder & Codeforces & AtCoder交流QQ群：648202993  
> 更多内容请关注微信公众号  
> ![wechat\_public.jpg][wechat_public.jpg]

[BinaryTree.png]: /images/20220526/ac37df1e6af046eeb0b4c320c547d8fa.png
[wechat_public.jpg]: /images/20220526/e04f424a99894f1e8cb08c161da52c10.png