C++二叉樹的創(chuàng)建及遍歷詳情

更新時(shí)間：2022年07月22日 11:55:14 作者：樂十九

這篇文章主要介紹了C++二叉樹的創(chuàng)建及遍歷詳情，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下，希望對你的學(xué)習(xí)有所幫助

樹的定義

什么是樹？

假如給我們一棵二叉樹的前序遍歷和中序遍歷結(jié)果，我們應(yīng)該如何通過這兩個(gè)遍歷結(jié)果創(chuàng)建一棵樹呢？

通過前序遍歷的結(jié)果我們可以找到二叉樹的根節(jié)點(diǎn)，那么既然有了二叉樹的根節(jié)點(diǎn)，我們在看中序遍歷，在中序遍歷中找到二叉樹的根節(jié)點(diǎn)，呢么根節(jié)點(diǎn)之前的所有節(jié)點(diǎn)就是二叉樹的左子樹了，根節(jié)點(diǎn)之后的所有節(jié)點(diǎn)就是二叉樹的右子樹了。由此就可以對遍歷結(jié)果進(jìn)行分割了。

既然已經(jīng)得到了左子樹和右子樹就好辦了，我們知道二叉樹的左子樹和右子樹也可以看作是一棵二叉樹，此時(shí)二叉樹的規(guī)模變小的了，但還是符合前序遍歷和中序遍歷的結(jié)果，所以可以對左右子樹在分別進(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>
/*
*二叉樹的存儲方式有兩種，一種是以鏈表的方式進(jìn)行存儲，一種是以數(shù)組的方式進(jìn)行存儲
* 當(dāng)以數(shù)組的方式進(jìn)行存儲的時(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)行存儲
* 是非常的浪費(fèi)空間的，空間的利用率較低。
* 當(dāng)以鏈表的方式存儲二叉樹的時(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)。按照中序的順序，既左中右打印二叉樹。具體怎么操作呢？

申請一個(gè)站用來存儲節(jié)點(diǎn)，當(dāng)根節(jié)點(diǎn)不為空，或者棧不為空的時(shí)候判斷棧中節(jié)點(diǎn)的左孩子是否為空，如果左孩子不為空就繼續(xù)將左孩子入棧，如果左孩子為空，就打印該節(jié)點(diǎn)，然后在訪問右孩子，繼續(xù)之前的判斷。

要點(diǎn)在于我們訪問每一個(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)在于，我們訪問到端節(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>
/*
*二叉樹的存儲方式有兩種，一種是以鏈表的方式進(jìn)行存儲，一種是以數(shù)組的方式進(jìn)行存儲
* 當(dāng)以數(shù)組的方式進(jìn)行存儲的時(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)行存儲
* 是非常的浪費(fèi)空間的，空間的利用率較低。
* 當(dāng)以鏈表的方式存儲二叉樹的時(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)，原理是使用棧去存儲相應(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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: