純C++代碼詳解二叉樹相關操作
更新時間：2022年07月08日 16:19:09 作者：小張﹉
二叉樹（Binary?tree）是樹形結構的一個重要類型。許多實際問題抽象出來的數(shù)據(jù)結構往往是二叉樹形式。本文將通過代碼為大家詳細講講C++二叉樹的一些常規(guī)操作，感興趣的可以學習一下
前言
大家好，今天給大家?guī)淼氖嵌鏄涞南嚓P操作，希望能夠給大家?guī)韼椭?/p>
二叉樹的概念
二叉樹（Binary tree）是樹形結構的一個重要類型。許多實際問題抽象出來的數(shù)據(jù)結構往往是二叉樹形式，即使是一般的樹也能簡單地轉(zhuǎn)換為二叉樹，而且二叉樹的存儲結構及其算法都較為簡單，因此二叉樹顯得特別重要。二叉樹特點是每個節(jié)點最多只能有兩棵子樹，且有左右之分 。
二叉樹的相關術語
①節(jié)點：包含一個數(shù)據(jù)元素及若干指向子樹分支的信息 。
②節(jié)點的度：一個節(jié)點擁有子樹的數(shù)目稱為節(jié)點的度 。
③葉子節(jié)點：也稱為終端節(jié)點，沒有子樹的節(jié)點或者度為零的節(jié)點 。
④分支節(jié)點：也稱為非終端節(jié)點，度不為零的節(jié)點稱為非終端節(jié)點 。
⑤樹的度：樹中所有節(jié)點的度的最大值 。
⑥節(jié)點的層次：從根節(jié)點開始，假設根節(jié)點為第1層，根節(jié)點的子節(jié)點為第2層，依此類推，如果某一個節(jié)點位于第L層，則其子節(jié)點位于第L+1層 。
⑦樹的深度：也稱為樹的高度，樹中所有節(jié)點的層次最大值稱為樹的深度 。
相關操作菜單
//菜單
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 二叉樹葉子結點數(shù) *******************" << endl;
cout << "\t\t\t**************** 9.輸入8 二叉樹的結點數(shù) *******************" << endl;
cout << "\t\t\t******************************************************************" << endl;
}
二叉樹的構造
//構造二叉樹
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 == '#')
{
//如果輸入是#的話就說明根結點就是葉子結點
//就沒必要再去進行開辟一個二叉樹空間
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)建一個隊列qu
queue<StrBinode> qu;
//將根結點的指針壓入隊列
qu.push(HT);
//當隊列不為空的時候就繼續(xù)進行循環(huán)
while (!qu.empty())
{
//讓T里面存放隊列中第一個元素的值
T = qu.front();
//C++自帶的隊列出隊的話是刪除值不返回值
qu.pop();
//訪問出隊元素的值
cout << T->data << " ";
//當該節(jié)點左孩子不為空的時候就讓左孩子入隊
if (T->lchid != NULL)
{
qu.push(T->lchid);
}
//當該節(jié)點右孩子不為空的時候就讓左孩子入隊
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);
}
}
}
二叉樹的葉子結點數(shù)
//求二叉樹的葉子結點
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);
}
二叉樹的結點數(shù)
//求二叉樹的結點數(shù)
int Nodecount(StrBinode&T)
{
//如果是根結點沒有數(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;
//構造二叉樹
typedef struct Binode
{
//數(shù)據(jù)域
char data;
//定義左孩子和右孩子
struct Binode*lchid, *rchid;
}Binode, *StrBinode;
//先序遍歷創(chuàng)建二叉樹
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;
//創(chuàng)建一個隊列qu
queue<StrBinode> qu;
//將根結點的指針壓入隊列
qu.push(HT);
//當隊列不為空的時候就繼續(xù)進行循環(huán)
while (!qu.empty())
{
//讓T里面存放隊列中第一個元素的值
T = qu.front();
//C++自帶的隊列出隊的話是刪除值不返回值
qu.pop();
//訪問出隊元素的值
cout << T->data << " ";
//當該節(jié)點左孩子不為空的時候就讓左孩子入隊
if (T->lchid != NULL)
{
qu.push(T->lchid);
}
//當該節(jié)點右孩子不為空的時候就讓左孩子入隊
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);
}
//求二叉樹的結點數(shù)
int Nodecount(StrBinode&T)
{
//如果是根結點沒有數(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 二叉樹葉子結點數(shù) *******************" << endl;
cout << "\t\t\t**************** 9.輸入8 二叉樹的結點數(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 << "請輸入值對二叉樹進行初始化" << 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 << "二叉樹的葉子結點數(shù)為：";
cout << leaf(T) << endl;
break;
case 8:
cout << "二叉樹的結點數(shù)為；";
cout << Nodecount(T) << endl;
break;
default:
cout << "您的輸入有誤，請重新輸入" << endl;
break;
}
}
return 0;
}結果展示
以上就是純C++代碼詳解二叉樹相關操作的詳細內(nèi)容，更多關于C++二叉樹的資料請關注腳本之家其它相關文章！
相關文章
this是C++中的一個關鍵字,也是一個const指針,它指向當前對象,通過它可以訪問當前對象的所有成員,下面這篇文章主要給大家介紹了關于C++學習進階篇之類大小計算和this指針的相關資料,需要的朋友可以參考下2023-04-04
這篇文章主要為大家詳細介紹了C語言實現(xiàn)小型工資管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-02-02
這篇文章主要介紹了C++獲取本機MAC，IP，MASK地址的方法,主要通過IPHLPAPI.lib調(diào)用相關函數(shù)實現(xiàn)該功能,是非常實用的技巧,需要的朋友可以參考下2014-10-10
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡易停車場管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要介紹了C++學習小結之二進制轉(zhuǎn)換的相關資料,需要的朋友可以參考下2015-07-07
本文主要介紹了Qt實現(xiàn)無邊框窗口的示例代碼,主要包括鼠標光標在不同區(qū)域的變化,關閉拖動窗口,窗口支持任意拉伸等,具有一定的參考價值,感興趣的可以了解一下2024-01-01
這篇文章主要為大家介紹了c++?對象在棧上還是在堆上問題分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-11-11
這篇文章主要為大家詳細介紹了如何利用Qt實現(xiàn)字幕無間隙滾動效果，文中的實現(xiàn)過程講解詳細，感興趣的小伙伴可以跟隨小編一起學習一下2022-11-11
rand()函數(shù)用來產(chǎn)生隨機數(shù)，但是，rand()的內(nèi)部實現(xiàn)是用線性同余法實現(xiàn)的，是偽隨機數(shù)，由于周期較長，因此在一定范圍內(nèi)可以看成是隨機的。srand()用來設置rand()產(chǎn)生隨機數(shù)時的隨機數(shù)種子。參數(shù)seed是整數(shù)，通常可以利用time(0)或geypid(0)的返回值作為seed2023-02-02
Java?C++?算法題解leetcode652尋找重復子樹
這篇文章主要為大家介紹了Java?C++?算法題解leetcode652尋找重復子樹示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-09-09