C++二叉樹的創(chuàng)建及遍歷詳情
樹的定義
什么是樹?
假如給我們一棵二叉樹的前序遍歷和中序遍歷結(jié)果,我們應(yīng)該如何通過這兩個(gè)遍歷結(jié)果創(chuàng)建一棵樹呢?
通過前序遍歷的結(jié)果我們可以找到二叉樹的根節(jié)點(diǎn),那么既然有了二叉樹的根節(jié)點(diǎn),我們?cè)诳粗行虮闅v,在中序遍歷中找到二叉樹的根節(jié)點(diǎn),呢么根節(jié)點(diǎn)之前的所有節(jié)點(diǎn)就是二叉樹的左子樹了,根節(jié)點(diǎn)之后的所有節(jié)點(diǎn)就是二叉樹的右子樹了。由此就可以對(duì)遍歷結(jié)果進(jìn)行分割了。
既然已經(jīng)得到了左子樹和右子樹就好辦了,我們知道二叉樹的左子樹和右子樹也可以看作是一棵二叉樹,此時(shí)二叉樹的規(guī)模變小的了,但還是符合前序遍歷和中序遍歷的結(jié)果,所以可以對(duì)左右子樹在分別進(jìn)行創(chuàng)建。
偽代碼表示:
BtNode* BuyNode() { BtNode* s = (BtNode*)malloc(sizeof(BtNode)); if(s == nullptr) return nullptr; memset(s,0,sizeof(BtNode)); return s; } int FindPos(char* in,int n,char a) { int pos = -1; for(int i =0;i<n;++i) { if(in[i] == a) { pos = i; break; } } return pos; } BinaryTree CreateBinaryTree(char* Pre,char* in,int n) { //首先我們需要購買一個(gè)節(jié)點(diǎn),讓其作為根節(jié)點(diǎn),所以就需要一個(gè)購買節(jié)點(diǎn)函數(shù) BtNode* root = BuyNode();//購買節(jié)點(diǎn) root->value = pre[0]; //要想構(gòu)建二叉樹,我們還需要在中序遍歷中找到根節(jié)點(diǎn)的位置,從而確定左右子樹,所以還需要一個(gè)查找函數(shù),返回值是根節(jié)點(diǎn)的位置pos int pos = FindPos(in,n,pre[0]);//在中序遍歷中查找pre[0]的位置,如果沒有找到,說明兩個(gè)遍歷結(jié)果不是一棵二叉樹,直接退出 if(pos == -1) exit(0); //此時(shí)我們已經(jīng)有了新的左子樹和右子樹,分別來創(chuàng)建 CreateBinaryTree(左子樹的前序遍歷結(jié)果,左子樹的中序遍歷結(jié)果,左子樹的大小);//創(chuàng)建左子樹 CreateBinaryTree(右子樹的前序遍歷結(jié)果,右子樹的中序遍歷結(jié)果,右子樹的大小);//創(chuàng)建右子樹 } //pre 表示前序遍歷數(shù)組,in表示中序遍歷數(shù)組,n表示節(jié)點(diǎn)的個(gè)數(shù) BinaryTree CreateBtree(char* Pre,char* in) { int n = sizeof(pre)/sizeof(pre[0]); if(pre==nullptr||in==nullptr||n<=0) { return nullptr;//不滿足以上條件說明不存在該二叉樹,直接返回空指針 } CreateBinaryTree(pre,in,n);//開始創(chuàng)建 }
構(gòu)建二叉樹以及使用遞歸方式前中后序遍歷完整代碼如下:
#include<iostream> #include<stack> #include<queue> #include<memory> /* *二叉樹的存儲(chǔ)方式有兩種,一種是以鏈表的方式進(jìn)行存儲(chǔ),一種是以數(shù)組的方式進(jìn)行存儲(chǔ) * 當(dāng)以數(shù)組的方式進(jìn)行存儲(chǔ)的時(shí)候,要注意節(jié)點(diǎn)之間的關(guān)系,假設(shè)根節(jié)點(diǎn)的位置為POS那么左子樹的位置就是 * 2*POS+1,右子樹的位置就是2*POS+2。正是由于這層關(guān)系,當(dāng)二叉樹不是滿二叉樹的時(shí)候,使用數(shù)組進(jìn)行存儲(chǔ) * 是非常的浪費(fèi)空間的,空間的利用率較低。 * 當(dāng)以鏈表的方式存儲(chǔ)二叉樹的時(shí)候,每一個(gè)二叉樹節(jié)點(diǎn)都含有一個(gè)左孩子指針和一個(gè)右孩子指針,兩個(gè)指針分別 * 指向相應(yīng)的節(jié)點(diǎn),節(jié)省空間,并且更容易使用。 */ using namespace std; typedef char ElemType; typedef struct BtNode { ElemType value; BtNode* leftchild; BtNode* rightchild; }BtNode,*BinaryTree; BtNode* BuyNode() { BtNode* s = (BtNode*)malloc(sizeof(BtNode)); if (s == NULL)return nullptr; memset(s, 0, sizeof(BtNode)); return s; } int FindPos(ElemType* In, int n, ElemType val) { int pos = -1; for (int i = 0; i < n ; ++i) { if (In[i] == val) { pos = i; break; } } return pos; } BinaryTree CreateBinTree(ElemType* Pr, ElemType* In, int n) { BtNode* s = nullptr; if (n >= 1) { s = BuyNode(); s->value = Pr[0]; int pos = FindPos(In, n, Pr[0]); if (pos == -1) exit(0); s->leftchild = CreateBinTree(Pr + 1, In, pos); s->rightchild = CreateBinTree(Pr + pos + 1, In + pos + 1, n - pos - 1); } return s; } //通過前中序數(shù)組創(chuàng)建二叉樹 BinaryTree CreateBinaryTree(ElemType* Pr, ElemType* In) { int n = strlen(Pr); if (Pr == nullptr || In == nullptr) { return nullptr; } else return CreateBinTree(Pr, In, n); } BinaryTree CreateLI(ElemType* Li, ElemType* In, int n) { BtNode* s = nullptr; if (n >= 1) { s = BuyNode(); s->value = Li[n - 1];//后序遍歷的最后一位數(shù)據(jù)是根節(jié)點(diǎn) int pos = FindPos(In, n, Li[n - 1]); if (pos == -1)exit(0); s->leftchild = CreateLI(Li, In, pos); s->rightchild = CreateLI(Li + pos, In + pos + 1, n - pos - 1); } return s; } //通過后中序數(shù)組建立二叉樹 BinaryTree CreateLITree(ElemType* Li, ElemType* In) { int n = strlen(Li); if (Li == nullptr || In == nullptr) { return nullptr; } else return CreateLI(Li, In, n); } //二叉樹的前序遍歷(遞歸方式)根節(jié)點(diǎn)-左子樹-右子樹 void PreOrder(BtNode* root) { if (root != nullptr) { cout << root->value << " "; PreOrder(root->leftchild); PreOrder(root->rightchild); } } //二叉樹的中序遍歷(遞歸方式)左子樹-根節(jié)點(diǎn)-右子樹 void InOrder(BtNode* root) { if (root != nullptr) { InOrder(root->leftchild); cout << root->value << " "; InOrder(root->rightchild); } } //二叉樹的后序遍歷(遞歸方式)左子樹-右子樹-根節(jié)點(diǎn) void PastOrder(BtNode* root) { if (root != nullptr) { InOrder(root->leftchild); InOrder(root->rightchild); cout << root->value << " "; } } int main() { char ar[] = { "ABCDEFGH" }; char br[] = { "CBEDFAGH" }; char cr[] = { "CBEDFGHA" }; //BinaryTree root = CreateBinaryTree(ar, br); BinaryTree root = CreateLITree(cr, br); PreOrder(root); cout << endl; InOrder(root); cout << endl; PastOrder(root); cout << endl; }
非遞歸的中序遍歷的實(shí)現(xiàn)
這里我們需要借助一個(gè)棧來實(shí)現(xiàn),利用棧的特性,后進(jìn)先出,當(dāng)我們到達(dá)端節(jié)點(diǎn)時(shí),打印端節(jié)點(diǎn)。按照中序的順序,既左中右打印二叉樹。具體怎么操作呢?
申請(qǐng)一個(gè)站用來存儲(chǔ)節(jié)點(diǎn),當(dāng)根節(jié)點(diǎn)不為空,或者棧不為空的時(shí)候判斷棧中節(jié)點(diǎn)的左孩子是否為空,如果左孩子不為空就繼續(xù)將左孩子入棧,如果左孩子為空,就打印該節(jié)點(diǎn),然后在訪問右孩子,繼續(xù)之前的判斷。
要點(diǎn)在于我們?cè)L問每一個(gè)節(jié)點(diǎn)的時(shí)候,都要將其當(dāng)做根節(jié)點(diǎn)來判斷,將其當(dāng)做一個(gè)小的二叉樹,完成中序遍歷,那么總的實(shí)現(xiàn)下來就是整個(gè)二叉樹的中序遍歷啦。
代碼實(shí)現(xiàn):
void NiceInOrder(BtNode* root) { //如果根節(jié)點(diǎn)為空的話,直接返回就不用排序 if(root == nullptr) return; std::stack<BtNode*> st; while(root!=nullptr || !st.empty()) { //不斷將左子樹入棧,當(dāng)左子樹為空時(shí),說明到達(dá)端節(jié)點(diǎn) while(root!=nullptr) { st.push(root); root = root->leftchild; } root = st.top(); st.pop(); cout<< root->value; root = root->rightchild; } } }
二叉樹的非遞歸后序遍歷:
后序遍歷的順序是左右中,優(yōu)先訪問左子樹當(dāng)左子樹訪問完畢之后,在訪問右子樹,最后訪問根節(jié)點(diǎn)。那么非遞歸的后序遍歷的難點(diǎn)在于,我們?cè)L問到端節(jié)點(diǎn)之后如何判斷是否打印該節(jié)點(diǎn)呢,該節(jié)點(diǎn)是否還有右子樹沒有訪問。
假設(shè)二叉樹只有三個(gè)節(jié)點(diǎn),如圖所示:
如果根節(jié)點(diǎn)不為空就將根節(jié)點(diǎn)入棧,因?yàn)槭呛笮虮闅v,所以要再訪問根節(jié)點(diǎn)的左子樹,可以看到左子樹也不為空,繼續(xù)向左子樹訪問,當(dāng)左子樹為空時(shí)返回到根節(jié)點(diǎn)繼續(xù)判斷右子樹是否為空,當(dāng)左右子樹都為空的時(shí)候,才能打印根節(jié)點(diǎn)。
代碼實(shí)現(xiàn):
void NicePastOrder(BtrNode* root) { if(root == nullptr) return; std::stack<BtNode*> st; BtNode* tag = nullptr;//標(biāo)志位,總是指向最近打印的那個(gè)節(jié)點(diǎn) while(root != nullptr || !st.empty()) { while(root!=nullptr) { st.push(root); root = root->left; } //當(dāng)上面的循環(huán)執(zhí)行完畢,說明當(dāng)前的*root已經(jīng)指向了nullptr,那么他的雙親節(jié)點(diǎn)就是沒有左子樹的,然后可以進(jìn)行出戰(zhàn)操作了 //當(dāng)執(zhí)行完出棧操作之后,我們就已經(jīng)知道了root節(jié)點(diǎn)的左孩子是空的,或者左孩子已經(jīng)打印過了。 root= st.top(); st.pop(); //因?yàn)閳?zhí)行的是后序遍歷、出棧之后我們還需要判斷,該節(jié)點(diǎn)是否有右子樹,如果有并且還沒有遍歷,那么要將右子樹遍歷完畢才能打印根節(jié)點(diǎn) if(root->rightchild == nullptr || root->rightchild == tag) { cout << root->value; tag = ptr; ptr =nullptr; } else { //如果右子樹不為空,就要再將右子樹入棧,繼續(xù)判斷 st.push(root); root = root->rightchild; } } }
二叉樹的非遞歸的前序遍歷的實(shí)現(xiàn)
要實(shí)現(xiàn)前序遍歷就需要先打印根節(jié)點(diǎn),然后打印左子樹再打印右子樹,還是要使用分治的策略。使用一個(gè)棧,先將根節(jié)點(diǎn)入棧,只要root不為空或者棧不為空就一直循環(huán),每次循環(huán)都出棧頂元素,并判斷并將棧頂元素的左右孩子入棧。
代碼實(shí)現(xiàn):
void NicePreOrder(BtNode* root) { if (root == nullptr) return; stack<BtNode*> s; s.push(root);//先將根節(jié)點(diǎn)放進(jìn)去 while (root != nullptr || !s.empty()) { root = s.top(); s.pop(); cout << root->value; if (root->rightchild != nullptr) { s.push(root->rightchild); root = root->rightchild; } if (root->leftchild != nullptr) { s.push(root->leftchild); root = root->leftchild; } } }
二叉樹的創(chuàng)建以及前中后序遍歷的代碼總結(jié)
#include<iostream> #include<stack> #include<queue> #include<memory> /* *二叉樹的存儲(chǔ)方式有兩種,一種是以鏈表的方式進(jìn)行存儲(chǔ),一種是以數(shù)組的方式進(jìn)行存儲(chǔ) * 當(dāng)以數(shù)組的方式進(jìn)行存儲(chǔ)的時(shí)候,要注意節(jié)點(diǎn)之間的關(guān)系,假設(shè)根節(jié)點(diǎn)的位置為POS那么左子樹的位置就是 * 2*POS+1,右子樹的位置就是2*POS+2。正是由于這層關(guān)系,當(dāng)二叉樹不是滿二叉樹的時(shí)候,使用數(shù)組進(jìn)行存儲(chǔ) * 是非常的浪費(fèi)空間的,空間的利用率較低。 * 當(dāng)以鏈表的方式存儲(chǔ)二叉樹的時(shí)候,每一個(gè)二叉樹節(jié)點(diǎn)都含有一個(gè)左孩子指針和一個(gè)右孩子指針,兩個(gè)指針分別 * 指向相應(yīng)的節(jié)點(diǎn),節(jié)省空間,并且更容易使用。 */ using namespace std; typedef char ElemType; typedef struct BtNode { ElemType value; BtNode* leftchild; BtNode* rightchild; }BtNode,*BinaryTree; BtNode* BuyNode() { BtNode* s = (BtNode*)malloc(sizeof(BtNode)); if (s == NULL)return nullptr; memset(s, 0, sizeof(BtNode)); return s; } int FindPos(ElemType* In, int n, ElemType val) { int pos = -1; for (int i = 0; i < n ; ++i) { if (In[i] == val) { pos = i; break; } } return pos; } BinaryTree CreateBinTree(ElemType* Pr, ElemType* In, int n) { BtNode* s = nullptr; if (n >= 1) { s = BuyNode(); s->value = Pr[0]; int pos = FindPos(In, n, Pr[0]); if (pos == -1) exit(0); s->leftchild = CreateBinTree(Pr + 1, In, pos); s->rightchild = CreateBinTree(Pr + pos + 1, In + pos + 1, n - pos - 1); } return s; } //通過前中序數(shù)組創(chuàng)建二叉樹 BinaryTree CreateBinaryTree(ElemType* Pr, ElemType* In) { int n = strlen(Pr); if (Pr == nullptr || In == nullptr) { return nullptr; } else return CreateBinTree(Pr, In, n); } BinaryTree CreateLI(ElemType* In, ElemType* Li, int n) { BtNode* s = nullptr; if (n >= 1) { s = BuyNode(); s->value = Li[n - 1];//后序遍歷的最后一位數(shù)據(jù)是根節(jié)點(diǎn) int pos = FindPos(In, n, Li[n - 1]); if (pos == -1)exit(0); s->leftchild = CreateLI( In,Li, pos); s->rightchild = CreateLI( In + pos + 1,Li + pos, n - pos - 1); } return s; } //通過后中序數(shù)組建立二叉樹 BinaryTree CreateLITree(ElemType* In , ElemType* Li) { int n = strlen(In ); if (Li == nullptr || In == nullptr) { return nullptr; } else return CreateLI(In,Li , n); } //二叉樹的前序遍歷(遞歸方式)根節(jié)點(diǎn)-左子樹-右子樹 void PreOrder(BtNode* root) { if (root != nullptr) { cout << root->value << " "; PreOrder(root->leftchild); PreOrder(root->rightchild); } } //二叉樹的中序遍歷(遞歸方式)左子樹-根節(jié)點(diǎn)-右子樹 void InOrder(BtNode* root) { if (root != nullptr) { InOrder(root->leftchild); cout << root->value << " "; InOrder(root->rightchild); } } //二叉樹的后序遍歷(遞歸方式)左子樹-右子樹-根節(jié)點(diǎn) void PastOrder(BtNode* root) { if (root != nullptr) { InOrder(root->leftchild); InOrder(root->rightchild); cout << root->value << " "; } } 二叉樹的中序遍歷(非遞歸方式) //使用循環(huán)的方式一般是面試時(shí)考察的重點(diǎn),原理是使用棧去存儲(chǔ)相應(yīng)的子樹,當(dāng)?shù)竭_(dá)終端節(jié)點(diǎn)時(shí),再將棧中的節(jié)點(diǎn)一一出棧 void NiceInOrder(BtNode* root) { if (root == nullptr) return; stack<BtNode*> s; while (root !=nullptr || !s.empty()) { //將整個(gè)左子樹入棧 while (root != nullptr) { s.push(root); root = root->leftchild; } //到達(dá)端節(jié)點(diǎn)時(shí)開始出棧 root = s.top(); s.pop(); cout << root->value; root = root->rightchild; } cout << endl; } //二叉樹的前序遍歷(非遞歸方式) void NicePreOrder(BtNode* root) { if (root == nullptr) return; stack<BtNode*> s; BtNode* node = nullptr; s.push(root); while (!s.empty()) { node = s.top(); s.pop(); cout << node->value; if (node->rightchild) s.push(node->rightchild); if (node->leftchild) s.push(node->leftchild); } cout << endl; } //二叉樹的后序遍歷(非遞歸方式) void NicePastOrder(BtNode* root) { if (root == nullptr)return; stack<BtNode*> st; BtNode* tag = nullptr; while (root != nullptr || !st.empty()) { while (root != nullptr) { st.push(root); root = root->leftchild; } root = st.top(); st.pop(); if (root->rightchild == nullptr || root->rightchild == tag) { cout << root->value; tag = root; root = nullptr; } else { st.push(root); root = root->rightchild; } } cout << endl; } int main() { char ar[] = { "ABCDEFGH" }; char br[] = { "CBEDFAGH" }; char cr[] = { "CEFDBHGA" }; //BinaryTree root = CreateBinaryTree(ar, br); BinaryTree root = CreateLITree(br,cr ); NiceInOrder(root); NicePreOrder(root); PreOrder(root); /*PreOrder(root); cout << endl; InOrder(root); cout << endl; PastOrder(root); cout << endl;*/ }
ightchild == tag) { cout << root->value; tag = root; root = nullptr; } else { st.push(root); root = root->rightchild; } } cout << endl; } int main() { char ar[] = { “ABCDEFGH” }; char br[] = { “CBEDFAGH” }; char cr[] = { “CEFDBHGA” }; //BinaryTree root = CreateBinaryTree(ar, br); BinaryTree root = CreateLITree(br,cr ); NiceInOrder(root); NicePreOrder(root); PreOrder(root); /PreOrder(root); cout << endl; InOrder(root); cout << endl; PastOrder(root); cout << endl;/ }
到此這篇關(guān)于C++二叉樹的創(chuàng)建及遍歷詳情的文章就介紹到這了,更多相關(guān)C++二叉樹創(chuàng)建內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Qt數(shù)據(jù)庫應(yīng)用之實(shí)現(xiàn)通用數(shù)據(jù)庫采集
這篇文章主要為大家介紹了Qt中是如何實(shí)現(xiàn)通用數(shù)據(jù)庫采集的,文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)Qt有一定幫助,感興趣的小伙伴可以了解一下2022-03-03c++函數(shù)中的指針參數(shù)與地址參數(shù)區(qū)別介紹
c++函數(shù)中的指針參數(shù)與地址參數(shù)區(qū)別介紹;可供參考2012-11-11C語言實(shí)現(xiàn)對(duì)bmp格式圖片打碼
這篇文章主要介紹了C語言實(shí)現(xiàn)對(duì)bmp格式圖片打碼2016-01-01C++實(shí)現(xiàn)學(xué)生成績管理系統(tǒng)最新版
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)學(xué)生成績管理系統(tǒng)最新版,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-06-06使用Qt開發(fā)實(shí)現(xiàn)字幕滾動(dòng)效果
我們經(jīng)常能夠在外面看到那種滾動(dòng)字幕,那么就拿qt來做一個(gè)吧,文章通過代碼示例給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作有有一定的參考價(jià)值,需要的朋友可以參考下2023-11-11Cocos2dx實(shí)現(xiàn)數(shù)字跳動(dòng)效果
這篇文章主要為大家詳細(xì)介紹了Cocos2dx實(shí)現(xiàn)數(shù)字跳動(dòng)效果,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-09-09C++實(shí)現(xiàn)將s16le的音頻流轉(zhuǎn)換為float類型
這篇文章主要為大家詳細(xì)介紹了如何利用C++實(shí)現(xiàn)將s16le的音頻流轉(zhuǎn)換為float類型,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起了解一下2023-04-04linux c 查找使用庫的cflags與libs的方法詳解
本篇文章是對(duì)在linux中使用c語言查找使用庫的cflags與libs的方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05