前言

二叉树的原理

代码实现

/*
二叉树的学习
参考：https://blog.csdn.net/guokeyan22/article/details/50758922
*/

#include<iostream>
#include<queue>

using namespace std;

/*
二叉树的结点
*/

class BinTreeNode
{
private:
    int data;               //数据域
    BinTreeNode* left;      //左子树
    BinTreeNode* right;     //右子树

public:
    //使用列表初始化结点
    BinTreeNode(const int& item, BinTreeNode* lPtr = nullptr, BinTreeNode* rPtr = nullptr) :data(item), left(lPtr), right(rPtr) {};
    BinTreeNode() {};
    ~BinTreeNode() {};

public:
    void set_data(int data) {
        this->data = data;
    }

    int get_data() const {
        return this->data;
    }

    void set_left(BinTreeNode* left) {
        this->left = left;
    }

    BinTreeNode* get_left() const {
        return this->left;
    }

    void set_right(BinTreeNode* right) {
        this->right = right;
    }

    BinTreeNode* get_right() {
        return this->right;
    }



private:

};



/*
二叉树
*/

class  BinTree
{

private:
    BinTreeNode* root;      //根结点


public:
    BinTree(BinTreeNode* t = nullptr) :root(t) {};
    ~BinTree() { delete root; };

public:
    inline void set_root(BinTreeNode* root) {
        this->root = root;
    }
    
    inline BinTreeNode* get_root() const{
        return this->root;
    }

    //1.创建二叉树
    BinTreeNode* creat_tree();
    //2.前序遍历
    void pre_order(BinTreeNode* r)const;
    //3.中序遍历
    void in_order(BinTreeNode* r)const;
    //4.后序遍历
    void post_order(BinTreeNode* r)const;
    //5.层序遍历
    void level_order(BinTreeNode* r)const;
    //6.获取叶子结点个数
    int get_leaf_num(BinTreeNode* r)const;
    //7.获取二叉树高度
    int get_tree_height(BinTreeNode* r)const;
    ////8.交换二叉树的左右子树/儿子
    //void swap_left_right(BinTreeNode* r);
    ////

};

/*
创建二叉树
创建一颗二叉树，可以用前序/中序/后序的方法。 用"#"表示空结点

@return 二叉树的根结点
*/
BinTreeNode * BinTree::creat_tree() {

    char item;
    BinTreeNode* t;
    BinTreeNode* t_r;
    BinTreeNode* t_l;

    cin >> item;

    if (item!='#') {
        BinTreeNode* pTmpNode = new BinTreeNode(item - 48);
        //根结点
        t = pTmpNode;
        //创建左子树
        t_l = creat_tree();
        t->set_left(t_l);
        //创建右子树
        t_r = creat_tree();
        t->set_right(t_r);
        
        return t;
    } else {
        t = nullptr;
        return t;
    }

}

/*
二叉树的遍历——前序遍历
采用递归的方式

*/
void BinTree::pre_order(BinTreeNode * r) const {

    if (r!=nullptr) {

        //先遍历根结点
        cout << r->get_data() << " ";
        //然后前序遍历左子树
        pre_order(r->get_left());
        //最后前序遍历右子树
        pre_order(r->get_right());
        
    }
}

/*
二叉树的遍历——中序遍历
采用递归的方式
*/
void BinTree::in_order(BinTreeNode * r) const {
    if (r!=nullptr) {
        //先中序遍历左子树
        in_order(r->get_left());
        //然后遍历根结点
        cout << r->get_data() << " ";
        //最后中序遍历右子树
        in_order(r->get_right());
    }
}

/*
二叉树的遍历——后序遍历
*/
void BinTree::post_order(BinTreeNode * r) const {

    if (r!=nullptr) {
        //先后序遍历左子树
        post_order(r->get_left());
        //再后续遍历优子树
        post_order(r->get_right());
        //最后遍历根结点
        cout << r->get_data() << " ";
    }
    

}

/*
二叉树的遍历——层序遍历
二叉树的层序遍历类似于广度优先搜索BFS。 二叉树的层序遍历可以使用队列queue
*/
void BinTree::level_order(BinTreeNode * r) const {

    if (r==nullptr) {
        return;
    }

    queue<BinTreeNode*> q;
    //r进入队尾(队列在尾部插入，队头/首删除)
    q.push(r);

    while (!q.empty()) {
        //获取队首的元素
        BinTreeNode* pTmpNode = q.front();  
        cout << pTmpNode->get_data() << " ";

        //队头元素出队列/删除
        q.pop();

        if (pTmpNode->get_left()!=nullptr) {
            q.push(pTmpNode->get_left());

        }
        if (pTmpNode->get_right()!=nullptr) {
            q.push(pTmpNode->get_right());
        }
    }

}


/*
获取二叉树叶子结点的个数
二叉树叶子结点个数=左子树叶子结点个数+右子树叶子结点个数
利用递归
@return 叶子结点个数
*/
int BinTree::get_leaf_num(BinTreeNode * r) const {
    
    //递归终止条件1：该结点为空
    if (r == nullptr) {
        return 0;
    }

    //递归终止条件2：(这是判断是否为叶子结点)
    //若该结点的左子树，右子树为空，则为叶子结点
    if (r->get_right()==nullptr&&r->get_left()==nullptr) {
        return 1;
    }

    //递归整个书的叶子结点个数=左子树叶子结点个数+右子树叶子结点个数
    return get_leaf_num(r->get_left()) + get_leaf_num(r->get_right());

}


/*
计算二叉树的高度
二叉树的高度 = max(左子树高度，右子树高度)+1
*/
int BinTree::get_tree_height(BinTreeNode * r) const {
    //空结点
    if (r==nullptr) {
        return 0;
    }

    //叶子结点
    if (r->get_left()==nullptr&&r->get_right()==nullptr) {
        return 1;
    }

    int l_height = get_tree_height(r->get_left());
    int r_height = get_tree_height(r->get_right());

    return l_height >= r_height ? l_height + 1 : r_height + 1;
}



int main() {

    //实例化一个二叉树
    BinTree tree;
    //-------------------创建二叉树---------------------------
    cout << "创建一颗二叉树，请输入二叉树的前序序列，'#'代表空结点" << endl;
    tree.set_root(tree.creat_tree());
    cout << endl;

    //-------------------前序遍历二叉树-----------------------
    cout << "前序遍历二叉树的结果:";
    tree.pre_order(tree.get_root());
    cout << endl;

    //--------------------中序遍历二叉树----------------------
    cout << "中序列遍历二叉树的结果:";
    tree.in_order(tree.get_root());
    cout << endl;

    //--------------------后序列遍历二叉树--------------------
    cout << "后序遍历二叉树的结果:";
    tree.post_order(tree.get_root());
    cout << endl;

    //--------------------层序遍历----------------------------
    cout << "层序遍历二叉树的结果:";
    tree.level_order(tree.get_root());
    cout << endl;

    //--------------------计算二叉树叶子结点的个数------------
    cout << "二叉树叶子结点的个数:";
    cout << tree.get_leaf_num(tree.get_root());
    cout << endl;

    //--------------------计算二叉树的高度--------------------
    cout << "二叉树的高度:";
    cout << tree.get_tree_height(tree.get_root());
    cout << endl;


    system("pause");

}

• 运行结果

  
  image.png