純C++程式碼詳解二元樹相關操作

2022-07-08 18:04:44

前言

大家好，今天給大家帶來的是二元樹的相關操作，希望能夠給大家帶來幫助。

二元樹的概念

二元樹（Binary tree）是樹形結構的一個重要型別。許多實際問題抽象出來的資料結構往往是二元樹形式，即使是一般的樹也能簡單地轉換為二元樹，而且二元樹的儲存結構及其演演算法都較為簡單，因此二元樹顯得特別重要。二元樹特點是每個節點最多隻能有兩棵子樹，且有左右之分。

二元樹的相關術語

①節點：包含一個資料元素及若干指向子樹分支的資訊。

②節點的度：一個節點擁有子樹的數目稱為節點的度。

③葉子節點：也稱為終端節點，沒有子樹的節點或者度為零的節點。

④分支節點：也稱為非終端節點，度不為零的節點稱為非終端節點。

⑤樹的度：樹中所有節點的度的最大值。

⑥節點的層次：從根節點開始，假設根節點為第1層，根節點的子節點為第2層，依此類推，如果某一個節點位於第L層，則其子節點位於第L+1層。

⑦樹的深度：也稱為樹的高度，樹中所有節點的層次最大值稱為樹的深度。

二元樹的構造

//構造二元樹
typedef struct Binode
{
    //資料域
    char data;
    //定義左孩子和右孩子
    struct Binode*lchid, *rchid;
}Binode, *StrBinode;

建立二元樹

//先序遍歷建立二元樹
void creatBinode(StrBinode&T)
{
    cin >> ch;
    if (ch == '#')
    {
        //如果輸入是#的話就說明根結點就是葉子結點
        //就沒必要再去進行開闢一個二元樹空間
        T = NULL;
    }
    else
    {
        T = new Binode;
        T->data = ch;
        creatBinode(T->lchid);
        creatBinode(T->rchid);
    }
}

先序遍歷二元樹

//先序遍歷二元樹
void visitBinode(StrBinode&T)
{
    if (T!=NULL)
    {
        cout << T->data << " ";
        visitBinode(T->lchid);
        visitBinode(T->rchid);
    }
    if(T==NULL)
    {
        cout << "#" << " ";
    }
}

中序遍歷二元樹

//中序遍歷二元樹
void MidvisitBinode(StrBinode&T)
{
    if (T != NULL)
    {
        visitBinode(T->lchid);
        cout << T->data << " ";
        visitBinode(T->rchid);
    }
    if (T == NULL)
    {
        cout << "#" << " ";
    }
}

後序遍歷二元樹

//後序遍歷二元樹
void BackvisitBinode(StrBinode&T)
{
    if (T != NULL)
    {
        visitBinode(T->lchid);
        visitBinode(T->rchid);
        cout << T->data << " ";
    }
    if (T == NULL)
    {
        cout << "#" << " ";
    }
}

層次遍歷二元樹

//二元樹的層次遍歷
void Levelorder(StrBinode&HT)
{
    StrBinode T;
    T = new Binode;
    //建立一個佇列qu
    queue<StrBinode> qu;
    //將根結點的指標壓入佇列
    qu.push(HT);
    //當佇列不為空的時候就繼續進行迴圈
    while (!qu.empty())
    {
        //讓T裡面存放佇列中第一個元素的值
        T = qu.front();
        //C++自帶的佇列出隊的話是刪除值不返回值
        qu.pop();
        //存取出隊元素的值
        cout << T->data << " ";
        //當該節點左孩子不為空的時候就讓左孩子入隊
        if (T->lchid != NULL)
        {
            qu.push(T->lchid);
        }
        //當該節點右孩子不為空的時候就讓左孩子入隊
        if (T->rchid != NULL)
        {
            qu.push(T->rchid);
        }
    }
    
}

二元樹的深度

//二元樹的深度
int deep(StrBinode&T)
{
    if (T == NULL)
    {
        return 0;
    }
    else
    {
        int m = deep(T->lchid);
        int n = deep(T->rchid);
        if (m > n)
        {
            return (m + 1);
        }
        else
        {
            return (n + 1);
        }
    }
}

二元樹的葉子結點數

//求二元樹的葉子結點
int leaf(StrBinode&T)
{
    //如果是空樹
    if (T == NULL)
    {
        //返回0
        return 0;
    }
    //如果是葉子結點
    if (T->lchid == NULL && T->rchid == NULL)
    {
        //返回1
        return 1;
    }
    return leaf(T->lchid) + leaf(T->rchid);
}

二元樹的結點數

//求二元樹的結點數
int Nodecount(StrBinode&T)
{
    //如果是根結點沒有資料
    if (T == NULL)
    {
        return 0;
    }
    else
    {
        return Nodecount(T->lchid) + Nodecount(T->rchid) + 1;
    }
}

整體程式碼

#include<iostream>
#include<queue>
using namespace std;
char ch = 0;
 
//構造二元樹
typedef struct Binode
{
    //資料域
    char data;
    //定義左孩子和右孩子
    struct Binode*lchid, *rchid;
}Binode, *StrBinode;
 
//先序遍歷建立二元樹
void creatBinode(StrBinode&T)
{
    cin >> ch;
    if (ch == '#')
    {
        //如果輸入是#的話就說明根結點就是葉子結點
        //就沒必要再去進行開闢一個二元樹空間
        T = NULL;
    }
    else
    {
        T = new Binode;
        T->data = ch;
        creatBinode(T->lchid);
        creatBinode(T->rchid);
    }
}
 
//先序遍歷二元樹
void visitBinode(StrBinode&T)
{
    if (T!=NULL)
    {
        cout << T->data << " ";
        visitBinode(T->lchid);
        visitBinode(T->rchid);
    }
    if(T==NULL)
    {
        cout << "#" << " ";
    }
}
 
//中序遍歷二元樹
void MidvisitBinode(StrBinode&T)
{
    if (T != NULL)
    {
        visitBinode(T->lchid);
        cout << T->data << " ";
        visitBinode(T->rchid);
    }
    if (T == NULL)
    {
        cout << "#" << " ";
    }
}
 
//後序遍歷二元樹
void BackvisitBinode(StrBinode&T)
{
    if (T != NULL)
    {
        visitBinode(T->lchid);
        visitBinode(T->rchid);
        cout << T->data << " ";
    }
    if (T == NULL)
    {
        cout << "#" << " ";
    }
}
 
//二元樹的層次遍歷
void Levelorder(StrBinode&HT)
{
    StrBinode T;
    T = new Binode;
    //建立一個佇列qu
    queue<StrBinode> qu;
    //將根結點的指標壓入佇列
    qu.push(HT);
    //當佇列不為空的時候就繼續進行迴圈
    while (!qu.empty())
    {
        //讓T裡面存放佇列中第一個元素的值
        T = qu.front();
        //C++自帶的佇列出隊的話是刪除值不返回值
        qu.pop();
        //存取出隊元素的值
        cout << T->data << " ";
        //當該節點左孩子不為空的時候就讓左孩子入隊
        if (T->lchid != NULL)
        {
            qu.push(T->lchid);
        }
        //當該節點右孩子不為空的時候就讓左孩子入隊
        if (T->rchid != NULL)
        {
            qu.push(T->rchid);
        }
    }
    
}
 
//二元樹的深度
int deep(StrBinode&T)
{
    if (T == NULL)
    {
        return 0;
    }
    else
    {
        int m = deep(T->lchid);
        int n = deep(T->rchid);
        if (m > n)
        {
            return (m + 1);
        }
        else
        {
            return (n + 1);
        }
    }
}
 
//求二元樹的葉子結點
int leaf(StrBinode&T)
{
    //如果是空樹
    if (T == NULL)
    {
        //返回0
        return 0;
    }
    //如果是葉子結點
    if (T->lchid == NULL && T->rchid == NULL)
    {
        //返回1
        return 1;
    }
    return leaf(T->lchid) + leaf(T->rchid);
}
 
//求二元樹的結點數
int Nodecount(StrBinode&T)
{
    //如果是根結點沒有資料
    if (T == NULL)
    {
        return 0;
    }
    else
    {
        return Nodecount(T->lchid) + Nodecount(T->rchid) + 1;
    }
}
 
//選單
void menu()
{
    cout << "ttt******************************************************************" << endl;
    cout << "ttt****************  1.輸入-1  退出程式           *******************" << endl;
    cout << "ttt****************  2.輸入1   初始化二元樹       *******************" << endl;
    cout << "ttt****************  3.輸入2   對二元樹先序遍歷   *******************" << endl;
    cout << "ttt****************  4.輸入3   對二元樹中序遍歷   *******************" << endl;
    cout << "ttt****************  5.輸入4   對二元樹後序遍歷   *******************" << endl;
    cout << "ttt****************  6.輸入5   對二元樹層次遍歷   *******************" << endl;
    cout << "ttt****************  7.輸入6   二元樹深度         *******************" << endl;
    cout << "ttt****************  8.輸入7   二元樹葉子結點數   *******************" << endl;
    cout << "ttt****************  9.輸入8   二元樹的結點數     *******************" << endl;
    cout << "ttt******************************************************************" << endl;
}
 
int main()
{
    int n = 0;
    StrBinode T;
    menu();
    while (cin >> n)
    {
        if (n < 0)
        {
            break;
        }
        switch (n)
        {
        case 1:
            //初始化二元樹
            cout << "請輸入值對二元樹進行初始化" << endl;
            creatBinode(T);
            cout << "初始化完成" << endl;
            break;
        case 2:
            //先序遍歷
            cout << "先序遍歷的結果為" << endl;
            visitBinode(T);
            cout << "先序遍歷結束" << endl;
            break;
        case 3:
            //中序遍歷
            cout << "中序遍歷的結果為" << endl;
            MidvisitBinode(T);
            cout << "中序遍歷結束" << endl;
            break;
        case 4:
            //後序遍歷
            cout << "後序遍歷的結果為" << endl;
            BackvisitBinode(T);
            cout << "後序遍歷結束" << endl;
            break;
        case 5:
            //層次遍歷
            cout << "層次遍歷的結果為" << endl;
            Levelorder(T);
            cout << "層次遍歷結束" << endl;
            break;
        case 6:
            cout << "二元樹的深度為：";
            cout << deep(T) << endl;
            break;
        case 7:
            cout << "二元樹的葉子結點數為：";
            cout << leaf(T) << endl;
            break;
        case 8:
            cout << "二元樹的結點數為；";
            cout << Nodecount(T) << endl;
            break;
        default:
            cout << "您的輸入有誤，請重新輸入" << endl;
            break;
        }
    }
    return 0;
}