純C++代碼詳解二叉樹相關操作
前言
大傢好,今天給大傢帶來的是二叉樹的相關操作,希望能夠給大傢帶來幫助。
二叉樹的概念
二叉樹(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其它相關文章!