C++数据结构：二叉树（一）——先序建立二叉树

小鱼儿 2022-06-06 04:25 361阅读 0赞

## 一、二叉树 （Binary Tree） ##

定义： 二叉树是n个节点的有限集合，该集合或者为空集（ 称为空二叉树 ），或者由一个根节点和两棵互不相交的的二叉树组成，这两棵二叉树分别称为根节点的左子树和右子树。

--------------------

本次二叉树知识体系的总结秉承的思想是：我们希望 二叉树类BiTree，它的私有成员能体现二叉树本身的性质，它的公有成员能提供给用户一系列对二叉树的操作方法。

--------------------

## 二、先序创建二叉树 ##

BiTree.h 头文件定义如下：

typedef char Item;          //树中数据类型
    typedef struct node         //每个节点包含一个数据，一个左指针，一个右指针
    {
        Item data;              //节点中数据
        struct node *lchild;    //指向当前节点的左孩子
        struct node *rchild;    //指向当前节点的右孩子
    }BiTNode;
    
    class BiTree
    {
    private:
        BiTNode *root;                      //二叉树的根节点
        int size;                           //二叉树的大小
        int depth;                          //二叉树的深度
    public:
        BiTree();                           //初始化二叉树构造函数
        void GetBiTRoot();                  //获取根节点
        void GetBiTNum();                   //获取二叉树节点数目
        void GetBiTDepth();                 //获取二叉树的深度
    
        BiTNode* CreateBiTree();            //先序创建二叉树
    };

BiTree.cpp 文件定义如下：

#include "BiTree.h"
    #include <iostream>
    #include <queue>
    using namespace std;
    static int leftdepth = 0;                   //左深度计数器
    static int rightdepth = 0;                  //右深度计数器
    //函数原型
    
    //构造函数
    //初始化二叉树，根节点指向空，树大小为0，深度为0
    BiTree::BiTree()
    {
        root = nullptr;
        size = 0;
        depth = 0;
    }
    
    //操作：  获取二叉树根节点数据
    void BiTree::GetBiTRoot()
    {
        cout << "二叉树的根节点为：";
        cout << this->root->data << endl;
    }
    
    //操作：  获取二叉树节点数目
    void BiTree::GetBiTNum()
    {
        cout << "二叉树的节点数目为：";
        cout << this->size << endl;
    }
    
    //操作：  获取二叉树的深度
    void BiTree::GetBiTDepth()
    {
        cout << "二叉树的深度为：";
        cout << this->depth << endl;
    }
    //操作：  先序建立二叉树
    //操作前：无参数，输入#表示为空
    //操作后：创建完整的树并返回树的根节点
    BiTNode* BiTree::CreateBiTree()
    {
        BiTNode *ptree;         //指向当前树节点的指针        
        if (this->root == nullptr)
            cout << "请输入根节点（#代表空树）:";
        else
            cout << "请输入节点（#代表空树）:";
        Item TreeData;          //树中的数据
        cin >> TreeData;        //输入数据
        if (TreeData == '#')    //如果输入的是“#”则表示空
            ptree = nullptr;
        else                    //否则不为空，申请一个空
        {
            if (!(ptree = new BiTNode))
                exit(1);
            ptree->data = TreeData;
            if(this->root == nullptr)
                this->root = ptree;
            this->size++;       //节点个数+1
            cout << ptree->data << "的左孩子";
            if(ptree->lchild = CreateBiTree())
                leftdepth++;    //左深度+1
            cout << ptree->data << "的右孩子";
            if(ptree->rchild = CreateBiTree())
                rightdepth++;   //右深度+1
        }
        this->depth = (leftdepth > rightdepth ? leftdepth : rightdepth) + 1;
        return ptree;           //最终返回树的根节点
    }

UseBiTree.cpp 文件定义如下：

#include "BiTree.h"
    #include <iostream>
    using namespace std;
    int main()
    {
        BiTree tree;
        tree.CreateBiTree();    //先序建立二叉树
        tree.GetBiTRoot();      //获取二叉树的根节点数据
        tree.GetBiTNum();       //获取二叉树的总节点个数
        tree.GetBiTDepth();     //获取二叉树的深度
    
        system("pause");
        return EXIT_SUCCESS;
    }

## 三、运行结果 ##

输入二叉树如下图所示  
  
![二叉树][SouthEast]  
 运行结果  
  
![运行结果][SouthEast 1]

--------------------

下一篇文章将为大家介绍[《二叉树的遍历》][Link 1]  
  
 如有不对的地方欢迎大家指正交流

[SouthEast]: /images/20220606/2b23811b77e141e19313e14a275fe2a7.png
[SouthEast 1]: /images/20220606/7f5312c14ae546ec8273f93b01c191bb.png
[Link 1]: http://blog.csdn.net/S_a_b_e_r_/article/details/78394556