題解——二叉樹的基本操作

題目鏈接：傳送門

描述

采用括號表示法的字串創建二叉鏈表表示的二叉樹，實作二叉樹的基本運算，如下:

(1)用括號表示法輸出二叉樹；

(2)輸出節點的左、右孩子節點值；

(3)輸出二叉樹的深度；

(4)輸出二叉樹的寬度；

(5)輸出二叉樹的節點個數；

(6)輸出二叉樹的葉子節點個數；

(7)釋放二叉樹，

輸入

兩行資料：
第一行：用括號表示法表示二叉樹的字串；
第二行：要求輸出的是括號表示法里的第幾個節點的左、右孩子節點值；

輸出

按照程式要求輸出，
其中：

• 輸出節點的左、右孩子節點值；
• 若無，則輸出：no leftchild no rightchild

樣例輸入

A(B(D,E(G,)),C(,F))
2

樣例輸出

A(B(D,E(G)),C(,F))
D E
4
3
7
3

提示

參考實驗題7.1

題解

基本操作（1）（3）（4）（5）（6）（7）可以在之前的博客里找到決議：資料結構與演算法——二叉樹

核心難點或許是（2）

輸出節點的左、右孩子節點值；

輸入的時候，第一行我們輸入的是括號運算式，第二行還輸入了一個數n，這個數就是在（2）里起作用——輸出括號運算式中第n個結點的左右孩子

所以我們要做的就是：

1. 找到第n個結點
2. 輸出它的左右孩子

我們可以在創建樹的同時，也就是在CreateTree函式里面，做一個計數器，記錄當前進入樹的結點是第幾個進入樹的結點，如果當前的結點就是第n個，那我們把它保存起來，最后，再輸出它，

按上面的思路，我們：

• 設定一個全域變數n，以確保在主函式輸入n后，可以在其他函式里直接訪問n的值；
• 定義一個BTNode型的指標變數res，用來存盤找到的第n個結點
• 修改CreateTree函式，添加計數器和判斷條件：

int n,num=0; //num是計數器，把它也定義為全域變數的好處是，它順便記錄了樹的結點個數，這樣（5）就可以直接輸出num了

BTNode *res=new BTNode(); //用于記錄第n個結點

void CreateBTree(BTNode *&bt,char *str){
    stack<BTNode*> st;
    bt=NULL;
    int k;
    BTNode *p=NULL;
    int len=strlen(str);
    for(int i=0;i<len;i++){
        if(str[i]=='('){
            k=1;
            st.push(p);
            continue;
        }
        else if(str[i]==')'){
            st.pop();
            continue;
        }
        else if(str[i]==','){
            k=2;
            continue;
        }
        else{
            p=new BTNode();
            p->data=str[i];
            p->lc=p->rc=NULL;
            if(bt==NULL){
                bt=p;
                num++; //計數器記錄
                if(num==n) //判斷
                    res=p; //保存
            }
            else{
                if(k==1)
                    st.top()->lc=p;
                else if(k==2)
                    st.top()->rc=p;
                num++; //計數器記錄
                if(num==n) //判斷
                    res=p; //保存
            }
        }
    }
}

需要注意的是，為什么一定要保存起來，而不是找到就輸出？

因為剛找到第n個結點的時候，它剛進樹，還沒有孩子，所以這時候你就算要輸出，也沒啥好輸出的，只能把它存下來，等它有孩子了你再輸出，它什么時候有孩子？全創建完了就有孩子了，

完整代碼參考：
不可以直接抄啊！

#include <iostream>
#include <stack>
#include <cstring>
#define ElemType char
using namespace std;
struct BTNode{ //"二叉樹點"
    ElemType data; //用define把char定義為ElemType
    BTNode *lc,*rc; //lc是"left child"左孩子，rc是"right child"右孩子
};

int n,num=0; //第n個結點，num是計數器
BTNode *res=new BTNode(); //用于記錄第n個結點
void CreateBTree(BTNode *&bt,char *str){
    stack<BTNode*> st; //STL的堆疊，型別為BTNode的指標
    bt=NULL; //根結點初始化為空
    int k; //用k記錄左右兒子，1為左，2為右
    BTNode *p=NULL; //用p存盤讀取到的字符
    int len=strlen(str); //字串str的長度為len
    for(int i=0;i<len;i++){
        if(str[i]=='('){
            k=1; //k計為左兒子
            st.push(p); //入堆疊
            continue;
        }
        else if(str[i]==')'){
            st.pop(); //出堆疊
            continue; //繼續往后看
        }
        else if(str[i]==','){
            k=2; //k計為右兒子
            continue;
        }
        else{
            p=new BTNode(); //為p申請空間
            p->data=str[i]; //賦值
            p->lc=p->rc=NULL;
            if(bt==NULL){ //如果bt為空，代表p為最開始的根結點
                bt=p;
                num++;
                if(num==n)
                    res=p;
            }
            else{
                if(k==1) //之前讀取到左括號，說明p是左孩子
                    st.top()->lc=p;
                else if(k==2) //之前讀取到逗號，說明p是右孩子
                    st.top()->rc=p;
                num++;
                if(num==n)
                    res=p;
            }
        }
    }
}

void DispBTree(BTNode *bt){ //輸出
    if(bt!=NULL){
        cout<<bt->data;
        if(bt->lc!=NULL|| bt->rc != NULL)
        {
            cout<<'(';
            DispBTree(bt->lc);
            if(bt->rc != NULL)
                cout<<',';
            DispBTree(bt->rc);
            cout<<')';
        }
    }
}

int BTHeight(BTNode *bt){ //求高度
    int lch, rch; //左子樹深度lch和右子樹深度rch
    if(bt==NULL) return 0; //如果是空的，就說明沒有長度，回傳0
    else{
        lch=BTHeight(bt->lc); //左子樹的深度
        rch=BTHeight(bt->rc); //右子樹的深度
        if(lch>rch)return lch+1;
        else return rch+1;
    }
}

int Count[10010];
void WidConut(BTNode *bt, int dep){  //寬度
    if(bt==NULL)
        return ;
    Count[dep]++;
    dep++;
    WidConut(bt->lc,dep);
    WidConut(bt->rc,dep);
}

int NodeCount(BTNode *bt){ //求結點個數
    int num1,num2;
    if(bt==NULL)
        return 0;
    else{
        num1=NodeCount(bt->lc); //左子樹的結點個數
        num2=NodeCount(bt->rc); //右子樹的結點個數
        return num1+num2+1;
    }
}

int LeafCount(BTNode *bt){ //求葉子結點個數
    int num1,num2;
    if(bt==NULL)
        return 0;
    else if(bt->lc==NULL&&bt->rc==NULL)
        return 1;
    else{
        num1=LeafCount(bt->lc); //左子樹的葉子結點
        num2=LeafCount(bt->rc); //右子樹的葉子結點
        return num1+num2;
    }
}

void DestoryBTree(BTNode *&bt){ //釋放
    if(bt!=NULL){ //bt只要不是NULL，就把它的孩子叫來
        DestoryBTree(bt->lc); //讓它叫左孩子
        DestoryBTree(bt->rc); //讓它叫右孩子
        delete bt; //嫩死它
    }
}

int main()
{
    BTNode *bt;
    char str[1000];
    cin>>str;
    cin>>n;
    CreateBTree(bt,str);
    DispBTree(bt);
    cout<<endl;
    if(res->lc!=NULL)
        cout<<res->lc->data<<" ";
    else cout<<"no leftchild ";
    if(res->rc!=NULL)
        cout<<res->rc->data<<endl;
    else cout<<"no rightchild"<<endl;
    cout<<BTHeight(bt)<<endl;
    WidConut(bt,0);
    
    int wid=0;
    for(int i=0;Count[i]!=0;i++)
        wid=max(wid,Count[i]);
    cout<<wid<<endl;
    cout<<NodeCount(bt)<<endl;
    //cout<<"num="<<num<<endl; //"輸出長度"可以直接用num，去掉注視符號試試
    cout<<LeafCount(bt);
    DestoryBTree(bt);
    return 0;
}