真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

二叉樹(C++)-創(chuàng)新互聯(lián)

二叉樹
  • 1.前言
  • 2.內(nèi)容
    • 1.二叉樹的遍歷
      • ①先序遍歷
        • [1]遞歸
        • [2]迭代
        • 力扣先序遍歷
      • ②中序遍歷
        • [1]遞歸
        • [2]迭代
        • 力扣中序遍歷
      • ③后序遍歷
        • [1]遞歸
        • [2]迭代
        • 力扣后序遍歷
      • ④層序遍歷
        • [1]隊(duì)列
        • 2.隊(duì)列 + 哈希
        • 力扣層序遍歷
      • ※※二叉樹遍歷的完整代碼
  • 3.總結(jié)
  • 4.更新日志

創(chuàng)新互聯(lián)是一家專業(yè)提供渾江企業(yè)網(wǎng)站建設(shè),專注與網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、H5頁(yè)面制作、小程序制作等業(yè)務(wù)。10年已為渾江眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站制作公司優(yōu)惠進(jìn)行中。1.前言

數(shù)據(jù)結(jié)構(gòu) 二叉樹

測(cè)試數(shù)據(jù)：利用先序遍歷二叉樹建樹（包括所有空結(jié)點(diǎn)）
'*'表示空結(jié)點(diǎn)

①測(cè)試數(shù)據(jù)1

ABC**DE*G**F***
樹1：
	    A
	 B
   C    D
      E   F
       G
樹深度為5(根結(jié)點(diǎn)為1時(shí))， 3個(gè)葉結(jié)點(diǎn)C、G、F
先序遍歷：ABCDEGF
中序遍歷：CBEGDFA
后序遍歷：CGEFDBA
層序遍歷：ABCDEFG

②測(cè)試數(shù)據(jù)2

AB**CD***
樹2：
		A
	  B   C
	     D
樹深度為3(根結(jié)點(diǎn)為1時(shí))，2個(gè)葉結(jié)點(diǎn)B、D
先序遍歷：ABCD
中序遍歷：BADC
后序遍歷：BDCA
層序遍歷：ABCD
2.內(nèi)容 1.二叉樹的遍歷 ①先序遍歷 [1]遞歸
//Recursion Preorder Traverse
void Preorder(const Tree& T, vector& v)
{if (T == nullptr) return;
	v.emplace_back(T->val);  //根
	Preorder(T->left, v);    //左
	Preorder(T->right, v);   //右
}
vectorPreorderTraversal(const Tree& T)
{vectorv;
	Preorder(T, v);
	return v;
}
[2]迭代
stackpreOrderStk;
	vectorpreOrderVec;
	Tree preTree = T;
	while (preTree || preOrderStk.size())
	{while (preTree)
		{	preOrderVec.emplace_back(preTree->val);
			preOrderStk.emplace(preTree);
			preTree = preTree->left;
		}
		preTree = preOrderStk.top();
		preOrderStk.pop();
		preTree = preTree->right;
	}
	printf("迭代先序遍歷：");
	for (const ElemType& x : preOrderVec)
		cout<< x;
	puts("");
力扣先序遍歷

144. 二叉樹的前序遍歷

②中序遍歷 [1]遞歸
//Recursion Inorder Traverse
void Inorder(const Tree& T, vector& v)
{if (T == nullptr) return;
	Inorder(T->left, v);    //左
	v.emplace_back(T->val); //根
	Inorder(T->right, v);   //右
}
vectorInorderTraversal(const Tree& T)
{vectorv;
	Inorder(T, v);
	return v;
}
[2]迭代
stackinOrderStk;
	vectorinOrderVec;
	Tree inTree = T;
	while (inTree || inOrderStk.size())
	{while (inTree)
		{	inOrderStk.emplace(inTree);
			inTree = inTree->left;
		}
		inTree = inOrderStk.top();
		inOrderStk.pop();
		inOrderVec.emplace_back(inTree->val);
		inTree = inTree->right;
	}
	printf("迭代中序遍歷為：");
	for (const ElemType& x : inOrderVec)
		cout<< x;
	puts("");
力扣中序遍歷

94. 二叉樹的中序遍歷

③后序遍歷 [1]遞歸
//Recursion Postorder Traverse
void Postorder(const Tree& T, vector& v)
{if (T == nullptr) return;
	Postorder(T->left, v);
	Postorder(T->right, v);
	v.emplace_back(T->val);
}
vectorPostorderTraversal(const Tree& T)
{vectorv;
	Postorder(T, v);
	return v;
}
[2]迭代
stackpostOrderStk;
	vectorpostOrderVec;
	Tree postTree = T;
	Tree prev = nullptr;
	while (postTree || postOrderStk.size())
	{while (postTree)
		{	postOrderStk.emplace(postTree);
			postTree = postTree->left;
		}
		postTree = postOrderStk.top();
		postOrderStk.pop();
		if (postTree->right == nullptr || postTree->right == prev) //無右子樹 或 為第二次遍歷的根
		{	postOrderVec.emplace_back(postTree->val);
			prev = postTree;
			postTree = nullptr;
		}
		else {	postOrderStk.emplace(postTree);
			postTree = postTree->right;
		}
	}
	printf("迭代后序遍歷為：");
	for (const ElemType& x : postOrderVec)
		cout<< x;
	puts("");
力扣后序遍歷

145. 二叉樹的后序遍歷

④層序遍歷 [1]隊(duì)列
//[1]隊(duì)列  傳空樹時(shí)要特判
	queuelevelOrderQue;
	vector>levelOrderVec;
	vectorleafVec;   //葉結(jié)點(diǎn)
	levelOrderQue.emplace(T);
	while (levelOrderQue.size())
	{int sz = levelOrderQue.size();
		vectorv;
		for (int i = 0; i< sz; ++i)
		{	auto t = levelOrderQue.front();
			levelOrderQue.pop();

			v.emplace_back(t->val);
			if (t->left) levelOrderQue.emplace(t->left);
			if (t->right) levelOrderQue.emplace(t->right);
			if (t->left == nullptr && t->right == nullptr) leafVec.emplace_back(t->val);  //葉結(jié)點(diǎn)
		}
		levelOrderVec.emplace_back(v);
	}
	cout<< "樹的深度為: "<< levelOrderVec.size()<< endl;
	cout<< "樹的葉結(jié)點(diǎn)個(gè)數(shù)為: "<< leafVec.size()<< " 分別為: ";
	for (const ElemType& x : leafVec)
		cout<< x<< " ";
	puts("");
	printf("層序遍歷為：");
	for (const vector& x : levelOrderVec)
		for (const ElemType& y : x)
			cout<< y;
	puts("");
2.隊(duì)列 + 哈希
//[2]隊(duì)列 + 哈希[注意傳入空樹時(shí)，要特判！]
	queueq;
	unordered_map>v;
	unordered_mapdep;
	vectorleaf;
	q.emplace(T);
	dep[T] = 0;
	int depth = 0;
	while (q.size())
	{auto t = q.front();
		q.pop();

		int d = dep[t];
		v[d].emplace_back(t->val);
		if (t->left) q.emplace(t->left), dep[t->left] = d + 1;
		if (t->right) q.emplace(t->right), dep[t->right] = d + 1;
		if (t->left == nullptr && t->right == nullptr) leaf.emplace_back(t->val), depth = max(depth, d);
	}
	cout<< "樹的深度為："<< depth + 1<< endl;
	cout<< "樹的葉結(jié)點(diǎn)數(shù)為："<< leaf.size()<< " 分別是：";
	for (auto l : leaf)
		cout<< l<< " ";
	puts("");
	printf("層序遍歷為：");
	for (int i = 0; i<= depth; ++i)
		for (auto x : v[i])
			cout<< x;
	puts("");
力扣層序遍歷

102. 二叉樹的層序遍歷

※※二叉樹遍歷的完整代碼
#define _CRT_SECURE_NO_WARNINGS 1

#includeusing namespace std;
#include#include//迭代先序、中序、后序遍歷
#include//層序遍歷1
#include//層序遍歷2

//Definations
typedef char ElemType;
typedef struct TreeNode {ElemType val;
	struct TreeNode* left, * right;
	TreeNode() :val(-1), left(nullptr), right(nullptr) {}
	TreeNode(ElemType e) :val(e), left(nullptr), right(nullptr) {}
}TreeNode, *Tree;

//Build BiTree
void InitBiTree(Tree& T)
{char ch;
	scanf("%c", &ch);
	if (ch == '*') T = nullptr;
	else {T = (Tree)malloc(sizeof(TreeNode));
		if(T == NULL)exit(OVERFLOW);

		T->val = ch;
		InitBiTree(T->left);
		InitBiTree(T->right);
	}
}

//Recursion Preorder Traverse
void Preorder(const Tree& T, vector& v)
{if (T == nullptr) return;
	v.emplace_back(T->val);  //根
	Preorder(T->left, v);    //左
	Preorder(T->right, v);   //右
}
vectorPreorderTraversal(const Tree& T)
{vectorv;
	Preorder(T, v);
	return v;
}
//Recursion Inorder Traverse
void Inorder(const Tree& T, vector& v)
{if (T == nullptr) return;
	Inorder(T->left, v);    //左
	v.emplace_back(T->val); //根
	Inorder(T->right, v);   //右
}
vectorInorderTraversal(const Tree& T)
{vectorv;
	Inorder(T, v);
	return v;
}
//Recursion Postorder Traverse
void Postorder(const Tree& T, vector& v)
{if (T == nullptr) return;
	Postorder(T->left, v);
	Postorder(T->right, v);
	v.emplace_back(T->val);
}
vectorPostorderTraversal(const Tree& T)
{vectorv;
	Postorder(T, v);
	return v;
}

int main()
{//1.建樹
	Tree T;
	InitBiTree(T);

	//2.遞歸遍歷
	//[1]先序
	vectorpreOrderVector = PreorderTraversal(T);
	printf("遞歸先序遍歷：");
	for (const ElemType ch : preOrderVector)
		cout<< ch;
	puts("");
	//[2]中序
	vectorinOrderVector = InorderTraversal(T);
	printf("遞歸中序遍歷：");
	for (const ElemType ch : inOrderVector)
		cout<< ch;
	puts("");
	//[3]后序
	vectorpostOrderVector = PostorderTraversal(T);
	printf("遞歸后序遍歷：");
	for (const ElemType ch : postOrderVector)
		cout<< ch;
	puts("");

	//3.迭代遍歷
	//[1]先序
	stackpreOrderStk;
	vectorpreOrderVec;
	Tree preTree = T;
	while (preTree || preOrderStk.size())
	{while (preTree)
		{	preOrderVec.emplace_back(preTree->val);
			preOrderStk.emplace(preTree);
			preTree = preTree->left;
		}
		preTree = preOrderStk.top();
		preOrderStk.pop();
		preTree = preTree->right;
	}
	printf("迭代先序遍歷：");
	for (const ElemType& x : preOrderVec)
		cout<< x;
	puts("");


	//中序
	stackinOrderStk;
	vectorinOrderVec;
	Tree inTree = T;
	while (inTree || inOrderStk.size())
	{while (inTree)
		{	inOrderStk.emplace(inTree);
			inTree = inTree->left;
		}
		inTree = inOrderStk.top();
		inOrderStk.pop();
		inOrderVec.emplace_back(inTree->val);
		inTree = inTree->right;
	}
	printf("迭代中序遍歷為：");
	for (const ElemType& x : inOrderVec)
		cout<< x;
	puts("");

	//后序
	stackpostOrderStk;
	vectorpostOrderVec;
	Tree postTree = T;
	Tree prev = nullptr;
	while (postTree || postOrderStk.size())
	{while (postTree)
		{	postOrderStk.emplace(postTree);
			postTree = postTree->left;
		}
		postTree = postOrderStk.top();
		postOrderStk.pop();
		if (postTree->right == nullptr || postTree->right == prev) //無右子樹 或 為第二次遍歷的根
		{	postOrderVec.emplace_back(postTree->val);
			prev = postTree;
			postTree = nullptr;
		}
		else {	postOrderStk.emplace(postTree);
			postTree = postTree->right;
		}
	}
	printf("迭代后序遍歷為：");
	for (const ElemType& x : postOrderVec)
		cout<< x;
	puts("");


	//4.層序遍歷
	//[1]隊(duì)列
	queuelevelOrderQue;
	vector>levelOrderVec;
	vectorleafVec;   //葉結(jié)點(diǎn)
	levelOrderQue.emplace(T);
	while (levelOrderQue.size())
	{int sz = levelOrderQue.size();
		vectorv;
		for (int i = 0; i< sz; ++i)
		{	auto t = levelOrderQue.front();
			levelOrderQue.pop();

			v.emplace_back(t->val);
			if (t->left) levelOrderQue.emplace(t->left);
			if (t->right) levelOrderQue.emplace(t->right);
			if (t->left == nullptr && t->right == nullptr) leafVec.emplace_back(t->val);  //葉結(jié)點(diǎn)
		}
		levelOrderVec.emplace_back(v);
	}
	cout<< "樹的深度為: "<< levelOrderVec.size()<< endl;
	cout<< "樹的葉結(jié)點(diǎn)個(gè)數(shù)為: "<< leafVec.size()<< " 分別為: ";
	for (const ElemType& x : leafVec)
		cout<< x<< " ";
	puts("");
	printf("層序遍歷為：");
	for (const vector& x : levelOrderVec)
		for (const ElemType& y : x)
			cout<< y;
	puts("");

	//[2]隊(duì)列 + 哈希[注意傳入空樹時(shí)，要特判！]
	queueq;
	unordered_map>v;
	unordered_mapdep;
	vectorleaf;
	q.emplace(T);
	dep[T] = 0;
	int depth = 0;
	while (q.size())
	{auto t = q.front();
		q.pop();

		int d = dep[t];
		v[d].emplace_back(t->val);
		if (t->left) q.emplace(t->left), dep[t->left] = d + 1;
		if (t->right) q.emplace(t->right), dep[t->right] = d + 1;
		if (t->left == nullptr && t->right == nullptr) leaf.emplace_back(t->val), depth = max(depth, d);
	}
	cout<< "樹的深度為："<< depth + 1<< endl;
	cout<< "樹的葉結(jié)點(diǎn)數(shù)為："<< leaf.size()<< " 分別是：";
	for (auto l : leaf)
		cout<< l<< " ";
	puts("");
	printf("層序遍歷為：");
	for (int i = 0; i<= depth; ++i)
		for (auto x : v[i])
			cout<< x;
	puts("");
	return 0;
}
3.總結(jié)

繞行踩點(diǎn)法
遞歸方法較易，迭代需要思考

4.更新日志

2022.12.2 整理 二叉樹的遍歷

歡迎評(píng)論留言、指正~~

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧


名稱欄目：二叉樹(C++)-創(chuàng)新互聯(lián)
瀏覽路徑：http://weahome.cn/article/dogsgs.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220（工作日）

18980820575（7×24）

提交需求

返回頂部