C++二叉樹的創建及遍歷詳情

Posted on by

樹的定義

什麼是樹？

假如給我們一棵二叉樹的前序遍歷和中序遍歷結果，我們應該如何通過這兩個遍歷結果創建一棵樹呢？

通過前序遍歷的結果我們可以找到二叉樹的根節點，那麼既然有瞭二叉樹的根節點，我們在看中序遍歷，在中序遍歷中找到二叉樹的根節點，呢麼根節點之前的所有節點就是二叉樹的左子樹瞭，根節點之後的所有節點就是二叉樹的右子樹瞭。由此就可以對遍歷結果進行分割瞭。

既然已經得到瞭左子樹和右子樹就好辦瞭，我們知道二叉樹的左子樹和右子樹也可以看作是一棵二叉樹，此時二叉樹的規模變小的瞭，但還是符合前序遍歷和中序遍歷的結果，所以可以對左右子樹在分別進行創建。

偽代碼表示：

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++二叉樹的創建及遍歷詳情的文章就介紹到這瞭,更多相關C++二叉樹創建內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：