純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ī)淼氖嵌鏄涞南嚓P(guān)操作，希望能夠給大家?guī)韼椭?/p>
二叉樹的概念
二叉樹（Binary tree）是樹形結(jié)構(gòu)的一個(gè)重要類型。許多實(shí)際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹形式，即使是一般的樹也能簡單地轉(zhuǎn)換為二叉樹，而且二叉樹的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡單，因此二叉樹顯得特別重要。二叉樹特點(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)的層次最大值稱為樹的深度 。
相關(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 對(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;
}
二叉樹的構(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;
}結(jié)果展示
以上就是純C++代碼詳解二叉樹相關(guān)操作的詳細(xì)內(nèi)容，更多關(guān)于C++二叉樹的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
STL priority_queue（優(yōu)先隊(duì)列）詳解
這篇文章主要介紹了 STL priority_queue（優(yōu)先隊(duì)列）詳解的相關(guān)資料,需要的朋友可以參考下2016-10-10
這篇文章主要為大家詳細(xì)介紹了C語言計(jì)算大數(shù)相加的方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-05-05
C++實(shí)現(xiàn)LeetCode(41.首個(gè)缺失的正數(shù))
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(41.首個(gè)缺失的正數(shù)),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
一文帶你學(xué)習(xí)C++析構(gòu)函數(shù)
在C++中，析構(gòu)函數(shù)是一種特殊類型的成員函數(shù)，用于在對(duì)象生命周期結(jié)束時(shí)被自動(dòng)調(diào)用，本文我們將介紹C++析構(gòu)函數(shù)的一些重要知識(shí)點(diǎn)，并提供相應(yīng)代碼示例，需要的朋友可以參考下2023-05-05
下面小編就為大家?guī)硪黄獪\談C++ 類的實(shí)例中 內(nèi)存分配詳解。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-12-12
C語言中g(shù)etchar的用法以及實(shí)例解析
getchar()是stdio.h中的庫函數(shù),它的作用是從stdin流中讀入一個(gè)字符,下面這篇文章主要給大家介紹了關(guān)于C語言中g(shù)etchar的用法以及實(shí)例的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-03-03
C語言實(shí)現(xiàn)的學(xué)生選課系統(tǒng)代碼分享
這篇文章主要介紹了C語言實(shí)現(xiàn)的學(xué)生選課系統(tǒng)代碼分享，具有一定參考價(jià)值，需要的朋友可以了解下。2017-10-10
這篇文章主要介紹了C++中簡單使用HP-Socket，HP-Socket 是一套通用的高性能 TCP/UDP /HTTP 通信 框架 ，包含服務(wù)端組件、客戶端組件和 Agent 組件，廣泛適用于各種不同應(yīng)用場景的 TCP/UDP /HTTP 通信系統(tǒng)，下面來看看更具體的介紹吧2021-11-11
手把手帶你學(xué)習(xí)C++的數(shù)據(jù)類型
這篇文章主要為大家介紹了C++的數(shù)據(jù)類型，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助,希望能夠給你帶來幫助2021-11-11
一文搞懂C語言static關(guān)鍵字的三個(gè)作用
這篇文章主要介紹了C語言static關(guān)鍵字的三個(gè)作用,本文通過實(shí)例代碼圖文相結(jié)合給大家介紹的非常詳細(xì)，需要的朋友可以參考下2022-04-04