二叉树
- 1.前言
- 2.内容
- 1.二叉树的遍历
- ①先序遍历
- ②中序遍历
- ③后序遍历
- ④层序遍历
- ※※二叉树遍历的完整代码
- 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://cdkjz.cn/article/dogsgs.html
