溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇“C++二叉樹如何創建及遍歷”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“C++二叉樹如何創建及遍歷”文章吧。
假如給我們一棵二叉樹的前序遍歷和中序遍歷結果，我們應該如何通過這兩個遍歷結果創建一棵樹呢？
通過前序遍歷的結果我們可以找到二叉樹的根節點，那么既然有了二叉樹的根節點，我們在看中序遍歷，在中序遍歷中找到二叉樹的根節點，呢么根節點之前的所有節點就是二叉樹的左子樹了，根節點之后的所有節點就是二叉樹的右子樹了。由此就可以對遍歷結果進行分割了。
既然已經得到了左子樹和右子樹就好辦了，我們知道二叉樹的左子樹和右子樹也可以看作是一棵二叉樹，此時二叉樹的規模變小的了，但還是符合前序遍歷和中序遍歷的結果，所以可以對左右子樹在分別進行創建。
偽代碼表示：
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)
{
//首先我們需要購買一個節點，讓其作為根節點，所以就需要一個購買節點函數
BtNode* root = BuyNode();//購買節點
root->value = pre[0];
//要想構建二叉樹，我們還需要在中序遍歷中找到根節點的位置，從而確定左右子樹，所以還需要一個查找函數，返回值是根節點的位置pos
int pos = FindPos(in,n,pre[0]);//在中序遍歷中查找pre[0]的位置,如果沒有找到，說明兩個遍歷結果不是一棵二叉樹，直接退出
if(pos == -1) exit(0);
//此時我們已經有了新的左子樹和右子樹，分別來創建
CreateBinaryTree(左子樹的前序遍歷結果,左子樹的中序遍歷結果,左子樹的大小);//創建左子樹
CreateBinaryTree(右子樹的前序遍歷結果,右子樹的中序遍歷結果,右子樹的大小);//創建右子樹
}
//pre 表示前序遍歷數組，in表示中序遍歷數組，n表示節點的個數
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);//開始創建
}構建二叉樹以及使用遞歸方式前中后序遍歷完整代碼如下：
#include<iostream>
#include<stack>
#include<queue>
#include<memory>
/*
*二叉樹的存儲方式有兩種，一種是以鏈表的方式進行存儲，一種是以數組的方式進行存儲
* 當以數組的方式進行存儲的時候，要注意節點之間的關系，假設根節點的位置為POS那么左子樹的位置就是
* 2*POS+1，右子樹的位置就是2*POS+2。正是由于這層關系，當二叉樹不是滿二叉樹的時候，使用數組進行存儲
* 是非常的浪費空間的，空間的利用率較低。
* 當以鏈表的方式存儲二叉樹的時候，每一個二叉樹節點都含有一個左孩子指針和一個右孩子指針，兩個指針分別
* 指向相應的節點，節省空間，并且更容易使用。
*/
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;
}
//通過前中序數組創建二叉樹
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];//后序遍歷的最后一位數據是根節點
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;
}
//通過后中序數組建立二叉樹
BinaryTree CreateLITree(ElemType* Li, ElemType* In)
{
int n = strlen(Li);
if (Li == nullptr || In == nullptr)
{
return nullptr;
}
else
return CreateLI(Li, In, n);
}
//二叉樹的前序遍歷（遞歸方式）根節點-左子樹-右子樹
void PreOrder(BtNode* root)
{
if (root != nullptr)
{
cout << root->value << " ";
PreOrder(root->leftchild);
PreOrder(root->rightchild);
}
}
//二叉樹的中序遍歷（遞歸方式）左子樹-根節點-右子樹
void InOrder(BtNode* root)
{
if (root != nullptr)
{
InOrder(root->leftchild);
cout << root->value << " ";
InOrder(root->rightchild);
}
}
//二叉樹的后序遍歷（遞歸方式）左子樹-右子樹-根節點
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;
}這里我們需要借助一個棧來實現，利用棧的特性，后進先出，當我們到達端節點時，打印端節點。按照中序的順序，既左中右打印二叉樹。具體怎么操作呢？
申請一個站用來存儲節點，當根節點不為空，或者棧不為空的時候判斷棧中節點的左孩子是否為空，如果左孩子不為空就繼續將左孩子入棧，如果左孩子為空，就打印該節點，然后在訪問右孩子，繼續之前的判斷。
要點在于我們訪問每一個節點的時候，都要將其當做根節點來判斷，將其當做一個小的二叉樹，完成中序遍歷，那么總的實現下來就是整個二叉樹的中序遍歷啦。
代碼實現:
void NiceInOrder(BtNode* root)
{
//如果根節點為空的話，直接返回就不用排序
if(root == nullptr) return;
std::stack<BtNode*> st;
while(root!=nullptr || !st.empty())
{
//不斷將左子樹入棧，當左子樹為空時，說明到達端節點
while(root!=nullptr)
{
st.push(root);
root = root->leftchild;
}
root = st.top(); st.pop();
cout<< root->value;
root = root->rightchild;
}
}
}二叉樹的非遞歸后序遍歷：
后序遍歷的順序是左右中，優先訪問左子樹當左子樹訪問完畢之后，在訪問右子樹，最后訪問根節點。那么非遞歸的后序遍歷的難點在于，我們訪問到端節點之后如何判斷是否打印該節點呢，該節點是否還有右子樹沒有訪問。
假設二叉樹只有三個節點，如圖所示：
如果根節點不為空就將根節點入棧，因為是后序遍歷，所以要再訪問根節點的左子樹，可以看到左子樹也不為空，繼續向左子樹訪問，當左子樹為空時返回到根節點繼續判斷右子樹是否為空，當左右子樹都為空的時候，才能打印根節點。
代碼實現：
void NicePastOrder(BtrNode* root)
{
if(root == nullptr) return;
std::stack<BtNode*> st;
BtNode* tag = nullptr;//標志位，總是指向最近打印的那個節點
while(root != nullptr || !st.empty())
{
while(root!=nullptr)
{
st.push(root);
root = root->left;
}
//當上面的循環執行完畢，說明當前的*root已經指向了nullptr，那么他的雙親節點就是沒有左子樹的，然后可以進行出戰操作了
//當執行完出棧操作之后，我們就已經知道了root節點的左孩子是空的，或者左孩子已經打印過了。
root= st.top(); st.pop();
//因為執行的是后序遍歷、出棧之后我們還需要判斷，該節點是否有右子樹，如果有并且還沒有遍歷，那么要將右子樹遍歷完畢才能打印根節點
if(root->rightchild == nullptr || root->rightchild == tag)
{
cout << root->value;
tag = ptr;
ptr =nullptr;
}
else
{
//如果右子樹不為空，就要再將右子樹入棧，繼續判斷
st.push(root);
root = root->rightchild；
}
}
}要實現前序遍歷就需要先打印根節點，然后打印左子樹再打印右子樹，還是要使用分治的策略。使用一個棧，先將根節點入棧，只要root不為空或者棧不為空就一直循環，每次循環都出棧頂元素，并判斷并將棧頂元素的左右孩子入棧。
代碼實現：
void NicePreOrder(BtNode* root)
{
if (root == nullptr) return;
stack<BtNode*> s;
s.push(root);//先將根節點放進去
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;
}
}
}#include<iostream>
#include<stack>
#include<queue>
#include<memory>
/*
*二叉樹的存儲方式有兩種，一種是以鏈表的方式進行存儲，一種是以數組的方式進行存儲
* 當以數組的方式進行存儲的時候，要注意節點之間的關系，假設根節點的位置為POS那么左子樹的位置就是
* 2*POS+1，右子樹的位置就是2*POS+2。正是由于這層關系，當二叉樹不是滿二叉樹的時候，使用數組進行存儲
* 是非常的浪費空間的，空間的利用率較低。
* 當以鏈表的方式存儲二叉樹的時候，每一個二叉樹節點都含有一個左孩子指針和一個右孩子指針，兩個指針分別
* 指向相應的節點，節省空間，并且更容易使用。
*/
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;
}
//通過前中序數組創建二叉樹
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];//后序遍歷的最后一位數據是根節點
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;
}
//通過后中序數組建立二叉樹
BinaryTree CreateLITree(ElemType* In , ElemType* Li)
{
int n = strlen(In );
if (Li == nullptr || In == nullptr)
{
return nullptr;
}
else
return CreateLI(In,Li , n);
}
//二叉樹的前序遍歷（遞歸方式）根節點-左子樹-右子樹
void PreOrder(BtNode* root)
{
if (root != nullptr)
{
cout << root->value << " ";
PreOrder(root->leftchild);
PreOrder(root->rightchild);
}
}
//二叉樹的中序遍歷（遞歸方式）左子樹-根節點-右子樹
void InOrder(BtNode* root)
{
if (root != nullptr)
{
InOrder(root->leftchild);
cout << root->value << " ";
InOrder(root->rightchild);
}
}
//二叉樹的后序遍歷（遞歸方式）左子樹-右子樹-根節點
void PastOrder(BtNode* root)
{
if (root != nullptr)
{
InOrder(root->leftchild);
InOrder(root->rightchild);
cout << root->value << " ";
}
}
二叉樹的中序遍歷（非遞歸方式）
//使用循環的方式一般是面試時考察的重點，原理是使用棧去存儲相應的子樹，當到達終端節點時，再將棧中的節點一一出棧
void NiceInOrder(BtNode* root)
{
if (root == nullptr) return;
stack<BtNode*> s;
while (root !=nullptr || !s.empty())
{
//將整個左子樹入棧
while (root != nullptr)
{
s.push(root);
root = root->leftchild;
}
//到達端節點時開始出棧
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;/
}以上就是關于“C++二叉樹如何創建及遍歷”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
