二叉树(C++)-创新互联

二叉树

1.前言
2.内容
- 1.二叉树的遍历
- - ①先序遍历
  - - [1]递归
    - [2]迭代
    - 力扣先序遍历
  - ②中序遍历
  - - [1]递归
    - [2]迭代
    - 力扣中序遍历
  - ③后序遍历
  - - [1]递归
    - [2]迭代
    - 力扣后序遍历
  - ④层序遍历
  - - [1]队列
    - 2.队列 + 哈希
    - 力扣层序遍历
  - ※※二叉树遍历的完整代码
3.总结
4.更新日志

创新互联是一家专业提供浑江企业网站建设,专注与网站设计、成都网站制作、H5页面制作、小程序制作等业务。10年已为浑江众多企业、政府机构等服务。创新互联专业网站制作公司优惠进行中。1.前言

数据结构二叉树

测试数据：利用先序遍历二叉树建树（包括所有空结点）
'*'表示空结点

①测试数据1

ABC**DE*G**F***
树1：
	    A
	 B
   C    D
      E   F
       G
树深度为5(根结点为1时)， 3个叶结点C、G、F
先序遍历：ABCDEGF
中序遍历：CBEGDFA
后序遍历：CGEFDBA
层序遍历：ABCDEFG

②测试数据2

AB**CD***
树2：
		A
	  B   C
	     D
树深度为3(根结点为1时)，2个叶结点B、D
先序遍历：ABCD
中序遍历：BADC
后序遍历：BDCA
层序遍历：ABCD

2.内容 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]队列

//[1]队列  传空树时要特判
	queuelevelOrderQue;
	vector>levelOrderVec;
	vectorleafVec;   //叶结点
	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);  //叶结点
		}
		levelOrderVec.emplace_back(v);
	}
	cout<< "树的深度为: "<< levelOrderVec.size()<< endl;
	cout<< "树的叶结点个数为: "<< 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.队列 + 哈希

//[2]队列 + 哈希[注意传入空树时，要特判！]
	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<< "树的叶结点数为："<< 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]队列
	queuelevelOrderQue;
	vector>levelOrderVec;
	vectorleafVec;   //叶结点
	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);  //叶结点
		}
		levelOrderVec.emplace_back(v);
	}
	cout<< "树的深度为: "<< levelOrderVec.size()<< endl;
	cout<< "树的叶结点个数为: "<< 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]队列 + 哈希[注意传入空树时，要特判！]
	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<< "树的叶结点数为："<< 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.总结

绕行踩点法
递归方法较易，迭代需要思考

4.更新日志

2022.12.2 整理二叉树的遍历

欢迎评论留言、指正~~

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站名称：二叉树(C++)-创新互联
本文路径：http://wjwzjz.com/article/dogsgs.html

新网创想网站建设，新征程启航

二叉树(C++)-创新互联

其他资讯