大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
数据结构 二叉树
测试数据:利用先序遍历二叉树建树(包括所有空结点)
'*'表示空结点
①测试数据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.总结绕行踩点法
递归方法较易,迭代需要思考
2022.12.2 整理 二叉树的遍历
欢迎评论留言、指正~~
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧