本節(jié)主要講述二叉樹(shù)中常見(jiàn)操作的 C++ 實(shí)現(xiàn)，重點(diǎn)是代碼的實(shí)現(xiàn)净响，不拘泥于一種方法少欺。
后續(xù)會(huì)根據(jù)做的一些題增加樹(shù)的其他操作，并在個(gè)人的 github 持續(xù)更新中馋贤。

本部分基本涵蓋了二叉樹(shù)的基本操作赞别，后續(xù)新增內(nèi)容會(huì)在個(gè)人的 github 上持續(xù)更新。
此處對(duì)于二叉樹(shù)的基本概念就不做贅述了配乓，聚焦于代碼上的實(shí)現(xiàn)仿滔。

二叉樹(shù)的創(chuàng)建

首先，c++ 文件的基本結(jié)構(gòu)走起來(lái)犹芹。

#include <bits/stdc++.h>

using namespace std;

int main(){
    
    return 0;
}

之后崎页，考慮二叉樹(shù)的節(jié)點(diǎn)，為了泛用性腰埂，可以使用 typedef飒焦。

typedef string ElemType;

這里我們使用 string 類(lèi)型作為節(jié)點(diǎn)類(lèi)型，當(dāng)然你也可以自定義其他類(lèi)型。

然后定義樹(shù)的節(jié)點(diǎn)牺荠，顯然翁巍，根據(jù)樹(shù)的定義，我們需要一個(gè)數(shù)據(jù)域 data 和兩個(gè)節(jié)點(diǎn)類(lèi)型的指針域 left 和 right休雌，分別指向其左子樹(shù)和右子樹(shù)灶壶，使用 struct 類(lèi)型即可。
完成這些后杈曲，我們?cè)诮Y(jié)構(gòu)體里創(chuàng)建一個(gè)給節(jié)點(diǎn)數(shù)據(jù)域賦值的構(gòu)造函數(shù)驰凛，其指針域都默認(rèn)為空。
結(jié)構(gòu)如下：

typedef string ElemType;

//定義樹(shù)的節(jié)點(diǎn)
typedef struct BinaryNode{
    //節(jié)點(diǎn)
    ElemType data;
    //左子樹(shù)
    BinaryNode* left;
    //右子樹(shù)
    BinaryNode* right;
    BinaryNode(ElemType value){
        data = value;
        left = NULL;
        right = NULL;
    }
}BinaryNode,*BiTree;

接下來(lái)担扑，我們定義一個(gè)二叉樹(shù)類(lèi)恰响，其私有成員部分有樹(shù)根節(jié)點(diǎn) mRoot ，節(jié)點(diǎn)總數(shù)(可有可無(wú)) size 魁亦，相關(guān)成員函數(shù)渔隶，共有成員部分也有相關(guān)成員函數(shù)羔挡。
二叉樹(shù)的類(lèi)如下：

//二叉樹(shù)
class BinaryTree{
private:
    //根節(jié)點(diǎn)
    BiTree mRoot;
    //節(jié)點(diǎn)總數(shù)
    int size;
    //按前序遍歷方式遞歸創(chuàng)建二叉樹(shù)
    BiTree create();
    //遞歸實(shí)現(xiàn)前序遍歷
    void preOrder(BiTree root);
    //非遞歸實(shí)現(xiàn)前序遍歷
    void nonRec_preOrder(BiTree root);
    //遞歸實(shí)現(xiàn)中序遍歷
    void inOrder(BiTree root);
    //非遞歸實(shí)現(xiàn)中序遍歷
    void nonRec_inOrder(BiTree root);
    //遞歸實(shí)現(xiàn)后序遍歷
    void postOrder(BiTree root);
    //非遞歸實(shí)現(xiàn)后序遍歷
    void nonRec_postOrder(BiTree root);
    //非遞歸實(shí)現(xiàn)層次遍歷
    void nonRec_levelOrder(BiTree root);
    //遞歸實(shí)現(xiàn)摧毀樹(shù)(前序遍歷)
    void destroy(BiTree root);
    //遞歸得到樹(shù)的節(jié)點(diǎn)數(shù)
    int getSize(BiTree root);
    //遞歸得到樹(shù)的高度
    int getHeight(BiTree root);
    //得到葉子節(jié)點(diǎn)的個(gè)數(shù)
    int getLeafs(BiTree root);
    //得到度為1的節(jié)點(diǎn)個(gè)數(shù)
    int getOneLeafs(BiTree root);
    //得到滿節(jié)點(diǎn)個(gè)數(shù)
    int getFullLeafs(BiTree root);
    //獲取第 k 層的節(jié)點(diǎn)數(shù)
    int getLevelSize(BiTree root,int level);
    //查找指定值的節(jié)點(diǎn)
    BiTree findNode(BiTree root,ElemType value);

public:
    //按前序遍歷方式遞歸創(chuàng)建二叉樹(shù)
    void createTree();
    //遞歸實(shí)現(xiàn)前序遍歷
    void preOrder();
    //非遞歸實(shí)現(xiàn)前序遍歷
    void nonRec_preOrder();
    //遞歸實(shí)現(xiàn)中序遍歷
    void inOrder();
    //非遞歸實(shí)現(xiàn)中序遍歷
    void nonRec_inOrder();
    //遞歸實(shí)現(xiàn)后序遍歷
    void postOrder();
    //非遞歸實(shí)現(xiàn)后序遍歷
    void nonRec_postOrder();
    //遞歸實(shí)現(xiàn)層次遍歷
    void nonRec_levelOrder();
    //遞歸實(shí)現(xiàn)摧毀樹(shù)(前序遍歷)
    void destroy();
    //遞歸得到樹(shù)的節(jié)點(diǎn)數(shù)
    int getSize();
    //遞歸得到樹(shù)的高度
    int getHeight();
    //得到葉子節(jié)點(diǎn)的個(gè)數(shù)
    int getLeafs();
    //得到度為1的節(jié)點(diǎn)個(gè)數(shù)
    int getOneLeafs();
    //得到滿節(jié)點(diǎn)個(gè)數(shù)
    int getFullLeafs();
    //獲取第 k 層的節(jié)點(diǎn)數(shù)
    int getLevelSize(int level);
    //判斷是否為完全二叉樹(shù)
    bool isCompleteTree();
    //查找指定值的節(jié)點(diǎn)
    BiTree findNode(ElemType value);

};

后續(xù)繼續(xù)增加一些功能洁奈，本系列的任務(wù)先實(shí)現(xiàn)上面給出所有的操作。

我們先來(lái)看按前序遍歷方式遞歸創(chuàng)建二叉樹(shù)绞灼，
私有函數(shù)部分：

void preOrder(BiTree root);

共有函數(shù)部分：

//按前序遍歷方式遞歸創(chuàng)建二叉樹(shù)
void createTree();

之后的操作基本上都分為相應(yīng)的私有函數(shù)部分和共有函數(shù)部分利术，
同時(shí)一個(gè)功能的實(shí)現(xiàn)先給出私有函數(shù)部分，再給出其共有函數(shù)部分低矮。

來(lái)看創(chuàng)建印叁，我們使用的是前序遍歷的方式，空節(jié)點(diǎn)使用 "#" (因?yàn)檩斎氲氖亲址?lèi)型)军掂。
首先呢轮蜕，我們創(chuàng)建型節(jié)點(diǎn) newNode ，若輸入的值為 "#" 蝗锥，則返回為空跃洛，因?yàn)槭强展?jié)點(diǎn)。
然后將輸入的值 value 賦予新節(jié)點(diǎn)的數(shù)據(jù)域终议，最后遞歸創(chuàng)建該節(jié)點(diǎn) newNode 的左子樹(shù)和右子樹(shù)汇竭。
代碼如下：

//按前序遍歷方式遞歸創(chuàng)建二叉樹(shù)
BiTree BinaryTree::create(){
    BiTree newNode = NULL;
    ElemType value;
    //此處 ElemType 應(yīng)該是基本類(lèi)型數(shù)據(jù),若為自定義類(lèi)型,請(qǐng)重載輸入流
    cin>>value;
    //# 表示當(dāng)前子樹(shù)為空
    if(value == "#"){
        return NULL;
    }else{
        //遞歸創(chuàng)建左右子樹(shù),使用 size 記錄下樹(shù)的節(jié)點(diǎn)樹(shù)
        size++;
        newNode = new BinaryNode(value);
        newNode->left = create();
        newNode->right = create();
        return newNode;
    }
}
void BinaryTree::createTree(){
    size = 0;
    mRoot = create();
}

這樣一棵樹(shù)就已經(jīng)創(chuàng)建好了，當(dāng)然樹(shù)的創(chuàng)建方式有很多穴张，這里只列舉了一種细燎，之后還會(huì)增加其他方式。
來(lái)測(cè)試下吧：

int main(){
    BinaryTree tree;
    cout<<"Please enter the tree in the previous order traversal mode.If the node is empty,use # instead:"<<endl;
    //"A B D G # # H # # # C E # I # # F # #";
    tree.createTree();
    cout<<&tree<<endl;
    return 0;
}

打印的結(jié)果為：

Please enter the tree in the previous order traversal mode.If the node is empty,use # instead:
A B D G # # H # # # C E # I # # F # #
0x62fe10

&tree 的內(nèi)容可能有所不同皂甘，有結(jié)果玻驻，說(shuō)明這棵樹(shù)已經(jīng)創(chuàng)建成功了！

樹(shù)的遍歷(遞歸 + 非遞歸)

在創(chuàng)建一棵樹(shù)后偿枕，我們總想看看樹(shù)里面有什么內(nèi)容璧瞬，那就遍歷嘛佛析。
樹(shù)的遍歷常見(jiàn)的有四種，前序遍歷彪蓬，中序遍歷寸莫，后序遍歷，層次遍歷档冬。
前三種既可以使用遞歸方法膘茎，也可以使用非遞歸。
層序遍歷就是非遞歸了酷誓。
非遞歸過(guò)程中會(huì)用到 棧與隊(duì)列 披坏，DFS 和 BFS 等概念。

前序遍歷(遞歸 + 非遞歸)

先來(lái)看前序遍歷的盐数，前序遍歷的順序是根節(jié)點(diǎn)棒拂，左子樹(shù)，右子樹(shù)玫氢。
遞歸方法很簡(jiǎn)單帚屉，代碼如下：

//遞歸實(shí)現(xiàn)前序遍歷
void BinaryTree::preOrder(BiTree root){
    if(root != NULL){
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}
void BinaryTree::preOrder(){
    cout<<"The result of the preorder traversal is "<<endl;
    preOrder(mRoot);
    cout<<endl;
}

非遞歸需要用到 棧 的思想，和非遞歸遍歷思想類(lèi)似漾峡。我們還需要用棧保存節(jié)點(diǎn)攻旦，并訪問(wèn)數(shù)據(jù)域。
具體的代碼如下：

//非遞歸實(shí)現(xiàn)前序遍歷
void BinaryTree::nonRec_preOrder(BiTree root){
    if(root == NULL){
        return ;
    }
    stack<BiTree> s;
    BiTree p = root;
    s.push(p);
    while(!s.empty()){
        BiTree node = s.top();
        cout<<node->data<<" ";
        s.pop();
        if(node->right){
            s.push(node->right);
        }
        if(node->left){
            s.push(node->left);
        }
    }
}
void BinaryTree::nonRec_preOrder(){
    cout<<"The result of the non-recursive preorder traversal is "<<endl;
    nonRec_preOrder(mRoot);
    cout<<endl;
}

測(cè)試部分等四種遍歷講完后統(tǒng)一給出生逸。

中序遍歷(遞歸 + 非遞歸)

先來(lái)看中序遍歷的牢屋，中序遍歷的順序是左子樹(shù)，根節(jié)點(diǎn)槽袄，右子樹(shù)烙无。
遞歸方法很簡(jiǎn)單，代碼如下：

//遞歸實(shí)現(xiàn)中序遍歷
void BinaryTree::inOrder(BiTree root){
    if(root != NULL){
        inOrder(root->left);
        cout<<root->data<<" ";
        inOrder(root->right);
    }
}
void BinaryTree::inOrder(){
    cout<<"The result of the in-order traversal is "<<endl;
    inOrder(mRoot);
    cout<<endl;
}

在之前的非遞歸前序遍歷的基礎(chǔ)上遍尺，中序遍歷也就不難了截酷。
具體代碼如下：

//非遞歸實(shí)現(xiàn)中序遍歷
void BinaryTree::nonRec_inOrder(BiTree root){
    if(root == NULL){
        return ;
    }
    stack<BiTree> myStack;
    BiTree rt = root;
    while(rt != NULL || !myStack.empty()){
        while(rt != NULL){
            myStack.push(rt);
            rt = rt->left;
        }
        rt = myStack.top();
        myStack.pop();
        cout<<rt->data<<" ";
        rt = rt->right;
    }
}
void BinaryTree::nonRec_inOrder(){
    cout<<"The result of the non-recursive in-order traversal is "<<endl;
    nonRec_inOrder(mRoot);
    cout<<endl;
}

后序遍歷(遞歸 + 非遞歸)

先來(lái)看后序遍歷的，后序遍歷的順序是左子樹(shù)狮鸭，右子樹(shù)合搅，根節(jié)點(diǎn)。
遞歸方法很簡(jiǎn)單歧蕉，代碼如下：

//遞歸實(shí)現(xiàn)后序遍歷
void BinaryTree::postOrder(BiTree root){
    if(root != NULL){
        postOrder(root->left);
        postOrder(root->right);
        cout<<root->data<<" ";
    }
}
void BinaryTree::postOrder(){
    cout<<"The result of the postorder traversal is "<<endl;
    postOrder(mRoot);
    cout<<endl;
}

仿照之前的非遞歸遍歷灾部，后序遍歷的非遞歸的具體代碼如下：

//非遞歸實(shí)現(xiàn)后序遍歷,雙棧法
/*
    棧 s1 入棧順序：根節(jié)點(diǎn)-> 左節(jié)點(diǎn)-> 右節(jié)點(diǎn)
    棧 s2 入棧順序：右節(jié)點(diǎn)-> 左節(jié)點(diǎn)-> 根節(jié)點(diǎn)
    出棧順序：根節(jié)點(diǎn)-> 左節(jié)點(diǎn)-> 右節(jié)點(diǎn)
*/
void BinaryTree::nonRec_postOrder(BiTree root){
    if(root == NULL){
        return ;
    }
    stack<BiTree> s1;
    stack<BiTree> s2;
    s1.push(root);
    while(!s1.empty()){
        BiTree p = s1.top();
        s1.pop();
        s2.push(p);
        if(p->left){
            s1.push(p->left);
        }
        if(p->right){
            s1.push(p->right);
        }
    }
    while(!s2.empty()){
        cout<<s2.top()->data<<" ";
        s2.pop();
    }
}
void BinaryTree::nonRec_postOrder(){
    cout<<"The result of the non-recursive postorder traversal is "<<endl;
    nonRec_postOrder(mRoot);
    cout<<endl;
}

層次遍歷

層次遍歷需要用到隊(duì)列保存每一層的節(jié)點(diǎn)，一層層地訪問(wèn)惯退，它不需要用到遞歸赌髓。
具體代碼如下：

//非遞歸實(shí)現(xiàn)層次遍歷
void BinaryTree::nonRec_levelOrder(BiTree root){
    queue<BiTree> q;
    q.push(root);
    while(!q.empty()){
        //每層的節(jié)點(diǎn)
        int num_level = q.size();
        while(num_level--){
            BiTree node = q.front();
            q.pop();
            cout<<node->data<<" ";
            if(node->left){
                q.push(node->left);
            }
            if(node->right){
                q.push(node->right);
            }
        }
    }
}
void BinaryTree::nonRec_levelOrder(){
    cout<<"The result of the non-recursive sequence traversal is "<<endl;
    nonRec_levelOrder(mRoot);
    cout<<endl;
}

匯總

我們來(lái)創(chuàng)建一棵樹(shù)，并使用上面的方法分別遍歷這棵樹(shù)。
測(cè)試代碼如下：

int main(){
    BinaryTree tree;
    cout<<"Please enter the tree in the previous order traversal mode.If the node is empty,use # instead:"<<endl;
    //"A B D G # # H # # # C E # I # # F # #";
    tree.createTree();
    cout<<&tree<<endl;
    //前序遍歷
    tree.preOrder();
    //非遞歸前序遍歷
    tree.nonRec_preOrder();
    //中序遍歷
    tree.inOrder();
    //非遞歸中序遍歷
    tree.nonRec_inOrder();
    //后序遍歷
    tree.postOrder();
    //非遞歸后序遍歷
    tree.nonRec_postOrder();
    //非遞歸層次遍歷
    tree.nonRec_levelOrder();
    return 0;
}

打印的結(jié)果如下：

Please enter the tree in the previous order traversal mode.If the node is empty,use # instead:
A B D G # # H # # # C E # I # # F # #
0x62fe10
The result of the preorder traversal is
A B D G H C E I F
The result of the non-recursive preorder traversal is
A B D G H C E I F
The result of the in-order traversal is
G D H B A E I C F
The result of the non-recursive in-order traversal is
G D H B A E I C F
The result of the postorder traversal is
G H D B I E F C A
The result of the non-recursive postorder traversal is
G H D B I E F C A
The result of the non-recursive sequence traversal is
A B C D E F G H I

結(jié)果和我們畫(huà)的樹(shù)是一致的锁蠕。

本節(jié)的內(nèi)容就到這里了夷野，之后繼續(xù)實(shí)現(xiàn)其他的功能。