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

更新時(shí)間：2022年07月08日 16:19:09 作者：小張﹉

二叉樹（Binary?tree）是樹形結(jié)構(gòu)的一個(gè)重要類型。許多實(shí)際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹形式。本文將通過代碼為大家詳細(xì)講講C++二叉樹的一些常規(guī)操作，感興趣的可以學(xué)習(xí)一下

前言
二叉樹的概念
二叉樹的相關(guān)術(shù)語
相關(guān)操作菜單
二叉樹的構(gòu)造
創(chuàng)建二叉樹
先序遍歷二叉樹
中序遍歷二叉樹
后序遍歷二叉樹
層次遍歷二叉樹
二叉樹的深度
二叉樹的葉子結(jié)點(diǎn)數(shù)
二叉樹的結(jié)點(diǎn)數(shù)
整體代碼
結(jié)果展示

前言

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

二叉樹的概念

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

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

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

②節(jié)點(diǎn)的度：一個(gè)節(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層，依此類推，如果某一個(gè)節(jié)點(diǎn)位于第L層，則其子節(jié)點(diǎn)位于第L+1層。

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

二叉樹的構(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)行開辟一個(gè)二叉樹空間
        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)建一個(gè)隊(duì)列qu
    queue<StrBinode> qu;
    //將根結(jié)點(diǎn)的指針壓入隊(duì)列
    qu.push(HT);
    //當(dāng)隊(duì)列不為空的時(shí)候就繼續(xù)進(jìn)行循環(huán)
    while (!qu.empty())
    {
        //讓T里面存放隊(duì)列中第一個(gè)元素的值
        T = qu.front();
        //C++自帶的隊(duì)列出隊(duì)的話是刪除值不返回值
        qu.pop();
        //訪問出隊(duì)元素的值
        cout << T->data << " ";
        //當(dāng)該節(jié)點(diǎn)左孩子不為空的時(shí)候就讓左孩子入隊(duì)
        if (T->lchid != NULL)
        {
            qu.push(T->lchid);
        }
        //當(dāng)該節(jié)點(diǎn)右孩子不為空的時(shí)候就讓左孩子入隊(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)行開辟一個(gè)二叉樹空間
        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)建一個(gè)隊(duì)列qu
    queue<StrBinode> qu;
    //將根結(jié)點(diǎn)的指針壓入隊(duì)列
    qu.push(HT);
    //當(dāng)隊(duì)列不為空的時(shí)候就繼續(xù)進(jìn)行循環(huán)
    while (!qu.empty())
    {
        //讓T里面存放隊(duì)列中第一個(gè)元素的值
        T = qu.front();
        //C++自帶的隊(duì)列出隊(duì)的話是刪除值不返回值
        qu.pop();
        //訪問出隊(duì)元素的值
        cout << T->data << " ";
        //當(dāng)該節(jié)點(diǎn)左孩子不為空的時(shí)候就讓左孩子入隊(duì)
        if (T->lchid != NULL)
        {
            qu.push(T->lchid);
        }
        //當(dāng)該節(jié)點(diǎn)右孩子不為空的時(shí)候就讓左孩子入隊(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   對(duì)二叉樹先序遍歷   *******************" << endl;
    cout << "\t\t\t****************  4.輸入3   對(duì)二叉樹中序遍歷   *******************" << endl;
    cout << "\t\t\t****************  5.輸入4   對(duì)二叉樹后序遍歷   *******************" << endl;
    cout << "\t\t\t****************  6.輸入5   對(duì)二叉樹層次遍歷   *******************" << 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 << "請(qǐng)輸入值對(duì)二叉樹進(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 << "您的輸入有誤，請(qǐng)重新輸入" << endl;
            break;
        }
    }
    return 0;
}