前言

二叉樹的原理

代碼實現(xiàn)

/*
二叉樹的學習
參考：https://blog.csdn.net/guokeyan22/article/details/50758922
*/

#include<iostream>
#include<queue>

using namespace std;

/*
二叉樹的結(jié)點
*/

class BinTreeNode
{
private:
    int data;               //數(shù)據(jù)域
    BinTreeNode* left;      //左子樹
    BinTreeNode* right;     //右子樹

public:
    //使用列表初始化結(jié)點
    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;      //根結(jié)點


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.創(chuàng)建二叉樹
    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.獲取葉子結(jié)點個數(shù)
    int get_leaf_num(BinTreeNode* r)const;
    //7.獲取二叉樹高度
    int get_tree_height(BinTreeNode* r)const;
    ////8.交換二叉樹的左右子樹/兒子
    //void swap_left_right(BinTreeNode* r);
    ////

};

/*
創(chuàng)建二叉樹
創(chuàng)建一顆二叉樹忱反，可以用前序/中序/后序的方法。 用"#"表示空結(jié)點

@return 二叉樹的根結(jié)點
*/
BinTreeNode * BinTree::creat_tree() {

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

    cin >> item;

    if (item!='#') {
        BinTreeNode* pTmpNode = new BinTreeNode(item - 48);
        //根結(jié)點
        t = pTmpNode;
        //創(chuàng)建左子樹
        t_l = creat_tree();
        t->set_left(t_l);
        //創(chuàng)建右子樹
        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) {

        //先遍歷根結(jié)點
        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());
        //然后遍歷根結(jié)點
        cout << r->get_data() << " ";
        //最后中序遍歷右子樹
        in_order(r->get_right());
    }
}

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

    if (r!=nullptr) {
        //先后序遍歷左子樹
        post_order(r->get_left());
        //再后續(xù)遍歷優(yōu)子樹
        post_order(r->get_right());
        //最后遍歷根結(jié)點
        cout << r->get_data() << " ";
    }
    

}

/*
二叉樹的遍歷——層序遍歷
二叉樹的層序遍歷類似于廣度優(yōu)先搜索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());
        }
    }

}


/*
獲取二叉樹葉子結(jié)點的個數(shù)
二叉樹葉子結(jié)點個數(shù)=左子樹葉子結(jié)點個數(shù)+右子樹葉子結(jié)點個數(shù)
利用遞歸
@return 葉子結(jié)點個數(shù)
*/
int BinTree::get_leaf_num(BinTreeNode * r) const {
    
    //遞歸終止條件1：該結(jié)點為空
    if (r == nullptr) {
        return 0;
    }

    //遞歸終止條件2：(這是判斷是否為葉子結(jié)點)
    //若該結(jié)點的左子樹，右子樹為空间影，則為葉子結(jié)點
    if (r->get_right()==nullptr&&r->get_left()==nullptr) {
        return 1;
    }

    //遞歸整個書的葉子結(jié)點個數(shù)=左子樹葉子結(jié)點個數(shù)+右子樹葉子結(jié)點個數(shù)
    return get_leaf_num(r->get_left()) + get_leaf_num(r->get_right());

}


/*
計算二叉樹的高度
二叉樹的高度 = max(左子樹高度注竿，右子樹高度)+1
*/
int BinTree::get_tree_height(BinTreeNode * r) const {
    //空結(jié)點
    if (r==nullptr) {
        return 0;
    }

    //葉子結(jié)點
    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;
    //-------------------創(chuàng)建二叉樹---------------------------
    cout << "創(chuàng)建一顆二叉樹，請輸入二叉樹的前序序列，'#'代表空結(jié)點" << endl;
    tree.set_root(tree.creat_tree());
    cout << endl;

    //-------------------前序遍歷二叉樹-----------------------
    cout << "前序遍歷二叉樹的結(jié)果:";
    tree.pre_order(tree.get_root());
    cout << endl;

    //--------------------中序遍歷二叉樹----------------------
    cout << "中序列遍歷二叉樹的結(jié)果:";
    tree.in_order(tree.get_root());
    cout << endl;

    //--------------------后序列遍歷二叉樹--------------------
    cout << "后序遍歷二叉樹的結(jié)果:";
    tree.post_order(tree.get_root());
    cout << endl;

    //--------------------層序遍歷----------------------------
    cout << "層序遍歷二叉樹的結(jié)果:";
    tree.level_order(tree.get_root());
    cout << endl;

    //--------------------計算二叉樹葉子結(jié)點的個數(shù)------------
    cout << "二叉樹葉子結(jié)點的個數(shù):";
    cout << tree.get_leaf_num(tree.get_root());
    cout << endl;

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


    system("pause");

}

• 運行結(jié)果

  
  
  image.png