欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

純C++代碼詳解二叉樹相關(guān)操作

 更新時間：2022年07月08日 16:19:09   作者：小張﹉  
二叉樹（Binary?tree）是樹形結(jié)構(gòu)的一個重要類型。許多實(shí)際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹形式。本文將通過代碼為大家詳細(xì)講講C++二叉樹的一些常規(guī)操作，感興趣的可以學(xué)習(xí)一下

前言 

大家好，今天給大家?guī)淼氖嵌鏄涞南嚓P(guān)操作，希望能夠給大家?guī)韼椭?/p>

二叉樹的概念

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

二叉樹的相關(guān)術(shù)語

①節(jié)點(diǎn)：包含一個數(shù)據(jù)元素及若干指向子樹分支的信息 。

②節(jié)點(diǎn)的度：一個節(jié)點(diǎn)擁有子樹的數(shù)目稱為節(jié)點(diǎn)的度 。

③葉子節(jié)點(diǎn)：也稱為終端節(jié)點(diǎn)，沒有子樹的節(jié)點(diǎn)或者度為零的節(jié)點(diǎn) 。

④分支節(jié)點(diǎn)：也稱為非終端節(jié)點(diǎn)，度不為零的節(jié)點(diǎn)稱為非終端節(jié)點(diǎn) 。

⑤樹的度：樹中所有節(jié)點(diǎn)的度的最大值 。

⑥節(jié)點(diǎn)的層次：從根節(jié)點(diǎn)開始，假設(shè)根節(jié)點(diǎn)為第1層，根節(jié)點(diǎn)的子節(jié)點(diǎn)為第2層，依此類推，如果某一個節(jié)點(diǎn)位于第L層，則其子節(jié)點(diǎn)位于第L+1層 。

⑦樹的深度：也稱為樹的高度，樹中所有節(jié)點(diǎn)的層次最大值稱為樹的深度  。

相關(guān)操作菜單

//菜單
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   二叉樹葉子結(jié)點(diǎn)數(shù)   *******************" << endl;
    cout << "\t\t\t****************  9.輸入8   二叉樹的結(jié)點(diǎn)數(shù)     *******************" << endl;
    cout << "\t\t\t******************************************************************" << endl;
}

二叉樹的構(gòu)造

//構(gòu)造二叉樹
typedef struct Binode
{
    //數(shù)據(jù)域
    char data;
    //定義左孩子和右孩子
    struct Binode*lchid, *rchid;
}Binode, *StrBinode;

創(chuàng)建二叉樹

//先序遍歷創(chuàng)建二叉樹
void creatBinode(StrBinode&T)
{
    cin >> ch;
    if (ch == '#')
    {
        //如果輸入是#的話就說明根結(jié)點(diǎn)就是葉子結(jié)點(diǎn)
        //就沒必要再去進(jìn)行開辟一個二叉樹空間
        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;
    //創(chuàng)建一個隊(duì)列qu
    queue<StrBinode> qu;
    //將根結(jié)點(diǎn)的指針壓入隊(duì)列
    qu.push(HT);
    //當(dāng)隊(duì)列不為空的時候就繼續(xù)進(jìn)行循環(huán)
    while (!qu.empty())
    {
        //讓T里面存放隊(duì)列中第一個元素的值
        T = qu.front();
        //C++自帶的隊(duì)列出隊(duì)的話是刪除值不返回值
        qu.pop();
        //訪問出隊(duì)元素的值
        cout << T->data << " ";
        //當(dāng)該節(jié)點(diǎn)左孩子不為空的時候就讓左孩子入隊(duì)
        if (T->lchid != NULL)
        {
            qu.push(T->lchid);
        }
        //當(dāng)該節(jié)點(diǎn)右孩子不為空的時候就讓左孩子入隊(duì)
        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);
        }
    }
}

二叉樹的葉子結(jié)點(diǎn)數(shù)

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

二叉樹的結(jié)點(diǎn)數(shù)

//求二叉樹的結(jié)點(diǎn)數(shù)
int Nodecount(StrBinode&T)
{
    //如果是根結(jié)點(diǎn)沒有數(shù)據(jù)
    if (T == NULL)
    {
        return 0;
    }
    else
    {
        return Nodecount(T->lchid) + Nodecount(T->rchid) + 1;
    }
}

整體代碼

#include<iostream>
#include<queue>
using namespace std;
char ch = 0;
 
//構(gòu)造二叉樹
typedef struct Binode
{
    //數(shù)據(jù)域
    char data;
    //定義左孩子和右孩子
    struct Binode*lchid, *rchid;
}Binode, *StrBinode;
 
//先序遍歷創(chuàng)建二叉樹
void creatBinode(StrBinode&T)
{
    cin >> ch;
    if (ch == '#')
    {
        //如果輸入是#的話就說明根結(jié)點(diǎn)就是葉子結(jié)點(diǎn)
        //就沒必要再去進(jìn)行開辟一個二叉樹空間
        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;
    //創(chuàng)建一個隊(duì)列qu
    queue<StrBinode> qu;
    //將根結(jié)點(diǎn)的指針壓入隊(duì)列
    qu.push(HT);
    //當(dāng)隊(duì)列不為空的時候就繼續(xù)進(jìn)行循環(huán)
    while (!qu.empty())
    {
        //讓T里面存放隊(duì)列中第一個元素的值
        T = qu.front();
        //C++自帶的隊(duì)列出隊(duì)的話是刪除值不返回值
        qu.pop();
        //訪問出隊(duì)元素的值
        cout << T->data << " ";
        //當(dāng)該節(jié)點(diǎn)左孩子不為空的時候就讓左孩子入隊(duì)
        if (T->lchid != NULL)
        {
            qu.push(T->lchid);
        }
        //當(dāng)該節(jié)點(diǎn)右孩子不為空的時候就讓左孩子入隊(duì)
        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);
        }
    }
}
 
//求二叉樹的葉子結(jié)點(diǎn)
int leaf(StrBinode&T)
{
    //如果是空樹
    if (T == NULL)
    {
        //返回0
        return 0;
    }
    //如果是葉子結(jié)點(diǎn)
    if (T->lchid == NULL && T->rchid == NULL)
    {
        //返回1
        return 1;
    }
    return leaf(T->lchid) + leaf(T->rchid);
}
 
//求二叉樹的結(jié)點(diǎn)數(shù)
int Nodecount(StrBinode&T)
{
    //如果是根結(jié)點(diǎn)沒有數(shù)據(jù)
    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   二叉樹葉子結(jié)點(diǎn)數(shù)   *******************" << endl;
    cout << "\t\t\t****************  9.輸入8   二叉樹的結(jié)點(diǎn)數(shù)     *******************" << 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 << "請輸入值對二叉樹進(jìn)行初始化" << endl;
            creatBinode(T);
            cout << "初始化完成" << endl;
            break;
        case 2:
            //先序遍歷
            cout << "先序遍歷的結(jié)果為" << endl;
            visitBinode(T);
            cout << "先序遍歷結(jié)束" << endl;
            break;
        case 3:
            //中序遍歷
            cout << "中序遍歷的結(jié)果為" << endl;
            MidvisitBinode(T);
            cout << "中序遍歷結(jié)束" << endl;
            break;
        case 4:
            //后序遍歷
            cout << "后序遍歷的結(jié)果為" << endl;
            BackvisitBinode(T);
            cout << "后序遍歷結(jié)束" << endl;
            break;
        case 5:
            //層次遍歷
            cout << "層次遍歷的結(jié)果為" << endl;
            Levelorder(T);
            cout << "層次遍歷結(jié)束" << endl;
            break;
        case 6:
            cout << "二叉樹的深度為：";
            cout << deep(T) << endl;
            break;
        case 7:
            cout << "二叉樹的葉子結(jié)點(diǎn)數(shù)為：";
            cout << leaf(T) << endl;
            break;
        case 8:
            cout << "二叉樹的結(jié)點(diǎn)數(shù)為；";
            cout << Nodecount(T) << endl;
            break;
        default:
            cout << "您的輸入有誤，請重新輸入" << endl;
            break;
        }
    }
    return 0;
}

結(jié)果展示

以上就是純C++代碼詳解二叉樹相關(guān)操作的詳細(xì)內(nèi)容，更多關(guān)于C++二叉樹的資料請關(guān)注腳本之家其它相關(guān)文章！

相關(guān)文章

  • C++學(xué)習(xí)進(jìn)階篇之類大小計(jì)算和this指針

    C++學(xué)習(xí)進(jìn)階篇之類大小計(jì)算和this指針

    this是C++中的一個關(guān)鍵字,也是一個const指針,它指向當(dāng)前對象,通過它可以訪問當(dāng)前對象的所有成員,下面這篇文章主要給大家介紹了關(guān)于C++學(xué)習(xí)進(jìn)階篇之類大小計(jì)算和this指針的相關(guān)資料,需要的朋友可以參考下
    2023-04-04
  • C語言實(shí)現(xiàn)小型工資管理系統(tǒng)

    C語言實(shí)現(xiàn)小型工資管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)小型工資管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-02-02
  • C++獲取本機(jī)MAC，IP，MASK地址的方法

    C++獲取本機(jī)MAC，IP，MASK地址的方法

    這篇文章主要介紹了C++獲取本機(jī)MAC，IP，MASK地址的方法,主要通過IPHLPAPI.lib調(diào)用相關(guān)函數(shù)實(shí)現(xiàn)該功能,是非常實(shí)用的技巧,需要的朋友可以參考下
    2014-10-10
  • C語言實(shí)現(xiàn)簡易停車場管理系統(tǒng)

    C語言實(shí)現(xiàn)簡易停車場管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡易停車場管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-03-03
  • C++學(xué)習(xí)小結(jié)之二進(jìn)制轉(zhuǎn)換

    C++學(xué)習(xí)小結(jié)之二進(jìn)制轉(zhuǎn)換

    這篇文章主要介紹了C++學(xué)習(xí)小結(jié)之二進(jìn)制轉(zhuǎn)換的相關(guān)資料,需要的朋友可以參考下
    2015-07-07
  • Qt實(shí)現(xiàn)無邊框窗口的示例代碼

    Qt實(shí)現(xiàn)無邊框窗口的示例代碼

    本文主要介紹了Qt實(shí)現(xiàn)無邊框窗口的示例代碼,主要包括鼠標(biāo)光標(biāo)在不同區(qū)域的變化,關(guān)閉拖動窗口,窗口支持任意拉伸等,具有一定的參考價值,感興趣的可以了解一下
    2024-01-01
  • c++?對象分配在棧上還是在堆上問題分析

    c++?對象分配在棧上還是在堆上問題分析

    這篇文章主要為大家介紹了c++?對象在棧上還是在堆上問題分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-11-11
  • Qt實(shí)現(xiàn)字幕無間隙滾動效果

    Qt實(shí)現(xiàn)字幕無間隙滾動效果

    這篇文章主要為大家詳細(xì)介紹了如何利用Qt實(shí)現(xiàn)字幕無間隙滾動效果，文中的實(shí)現(xiàn)過程講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2022-11-11
  • C語言rand和srand函數(shù)使用方法介紹

    C語言rand和srand函數(shù)使用方法介紹

    rand()函數(shù)用來產(chǎn)生隨機(jī)數(shù)，但是，rand()的內(nèi)部實(shí)現(xiàn)是用線性同余法實(shí)現(xiàn)的，是偽隨機(jī)數(shù)，由于周期較長，因此在一定范圍內(nèi)可以看成是隨機(jī)的。srand()用來設(shè)置rand()產(chǎn)生隨機(jī)數(shù)時的隨機(jī)數(shù)種子。參數(shù)seed是整數(shù)，通?？梢岳胻ime(0)或geypid(0)的返回值作為seed
    2023-02-02
  • Java?C++?算法題解leetcode652尋找重復(fù)子樹

    Java?C++?算法題解leetcode652尋找重復(fù)子樹

    這篇文章主要為大家介紹了Java?C++?算法題解leetcode652尋找重復(fù)子樹示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪
    2022-09-09

最新評論