純C++代碼詳解二叉樹相關操作

Posted on by

前言 

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

二叉樹的概念

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

二叉樹的相關術語

①節點：包含一個數據元素及若幹指向子樹分支的信息 。

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

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

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

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

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

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

相關操作菜單

//菜單
void menu()
{
    cout << "\t\t\t******************************************************************" << endl;
    cout << "\t\t\t****************  1.輸入-1  退出程序           *******************" << endl;
    cout << "\t\t\t****************  2.輸入1   初始化二叉樹       *******************" << endl;
    cout << "\t\t\t****************  3.輸入2   對二叉樹先序遍歷   *******************" << endl;
    cout << "\t\t\t****************  4.輸入3   對二叉樹中序遍歷   *******************" << endl;
    cout << "\t\t\t****************  5.輸入4   對二叉樹後序遍歷   *******************" << endl;
    cout << "\t\t\t****************  6.輸入5   對二叉樹層次遍歷   *******************" << endl;
    cout << "\t\t\t****************  7.輸入6   二叉樹深度         *******************" << endl;
    cout << "\t\t\t****************  8.輸入7   二叉樹葉子結點數   *******************" << endl;
    cout << "\t\t\t****************  9.輸入8   二叉樹的結點數     *******************" << endl;
    cout << "\t\t\t******************************************************************" << endl;
}

二叉樹的構造

//構造二叉樹
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 << "\t\t\t******************************************************************" << endl;
    cout << "\t\t\t****************  1.輸入-1  退出程序           *******************" << endl;
    cout << "\t\t\t****************  2.輸入1   初始化二叉樹       *******************" << endl;
    cout << "\t\t\t****************  3.輸入2   對二叉樹先序遍歷   *******************" << endl;
    cout << "\t\t\t****************  4.輸入3   對二叉樹中序遍歷   *******************" << endl;
    cout << "\t\t\t****************  5.輸入4   對二叉樹後序遍歷   *******************" << endl;
    cout << "\t\t\t****************  6.輸入5   對二叉樹層次遍歷   *******************" << endl;
    cout << "\t\t\t****************  7.輸入6   二叉樹深度         *******************" << endl;
    cout << "\t\t\t****************  8.輸入7   二叉樹葉子結點數   *******************" << endl;
    cout << "\t\t\t****************  9.輸入8   二叉樹的結點數     *******************" << endl;
    cout << "\t\t\t******************************************************************" << 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;
}

結果展示

以上就是純C++代碼詳解二叉樹相關操作的詳細內容，更多關於C++二叉樹的資料請關註WalkonNet其它相關文章！

推薦閱讀：