数据结构05：给出指定二叉树（二叉链表链式存储）求其先、中、后、层序遍历
给出指定二叉树求其先中后序遍历函数递归法(深度优先：先中后序；广度优先：层序)先序递归中序递归后序递归循环实现法先序循环中序循环后序循环源代码验证实现函数递归法(深度优先：先中后序；广度优先：层序)先序递归void PreOrder(BiTree T){/*先序遍历：递归遍历*/if(T != nullptr){visit(T);PreOrder(T->lChild);PreOrder(T-
·
给出指定二叉树求其先中后序遍历
函数递归法(深度优先：先中后序；广度优先：层序)
先序递归
void PreOrder(BiTree T)
{
/*先序遍历：递归遍历*/
if (T != nullptr)
{
visit(T);//访问根节点
PreOrder(T->lChild);//遍历左子树
PreOrder(T->rChild);//遍历右子树
}
}
中序递归
void InOrder(BiTree T)
{
/*中序遍历：递归遍历*/
if (T != nullptr)
{
InOrder(T->lChild);//遍历左子树
visit(T);//访问根节点
InOrder(T->rChild);//遍历右子树
}
}
后序递归
void PostOrder(BiTree T)
{
/*后序遍历：递归办法*/
if (T != nullptr)
{
PostOrder(T->lChild);//遍历左子树
PostOrder(T->rChild);//遍历右子树
visit(T);//访问根节点
}
}
层序递归（循环中递归）
void levelOrder_old(BiTree root,int level){
/*递归求层序遍历结果（每一层）*/
if(root == nullptr || level < 1){
return;
}
if(level == 1){
visit(root);
}
levelOrder_old(root->lChild,level - 1);
levelOrder_old(root->rChild,level - 1);
}
int highLength(BiTree root){
/*递归求树的高度*/
int l_length = 0;
int r_length = 0;
if(root == nullptr){
return 0;
}
else{
l_length = highLength(root->lChild);
r_length = highLength(root->rChild);
if(l_length < r_length){
return r_length + 1;
}
else{
return l_length + 1;
}
}
}
void levelOrder(BiTree T){
/*递归遍历层序*/
if(T == nullptr){
return;
}
int depth = highLength(T);
for(int i = 1; i <= depth; i++){
levelOrder_old(T,i);
}
}
循环实现法
先序循环（一个栈）
void PreOrder_Loop(BiTree T)
{
/*先序遍历：循环办法*/
BiTree s = T;//设置s为遍历指针
BiTree node;//设置指针node指向栈顶元素
ClearStack(&stack_Order);//对栈做清空操作，使之备用
while (!stack_Order.empty() || s != nullptr)
{//当栈为空且同时遍历指针S为空的时候，先序访问结束，退出循环
if (s != nullptr)
{
visit(s); //访问当前节点
stack_Order.push(s);//并将其入栈
s = s->lChild; //若其左孩子不空，则一直向左走
}
else
{
node = stack_Order.top();//s为空，取出栈顶元素
stack_Order.pop(); //栈顶元素出栈
s = node->rChild; //转向栈顶元素的右子树
}
}
}
中序循环（一个栈）
void InOrder_Loop(BiTree T)
{
/*中序遍历：循环办法*/
BiTree s = T;//设置S为遍历指针
BiTree node;//设置node指向栈顶元素
ClearStack(&stack_Order);//对栈做清空操作，使之备用
while (!stack_Order.empty() || s != nullptr)
{ //当栈为空且同时遍历指针S为空的时候，中序访问结束，退出循环
if (s != nullptr)
{
stack_Order.push(s);//s不空，s入栈
s = s->lChild; //左孩子不空，则一直向左走
}
else
{
node = stack_Order.top();//s为空，node取栈顶元素
stack_Order.pop(); //栈顶元素出栈
visit(node); //访问栈顶元素
s = node->rChild; //转向栈顶元素的右子树
}
}
}
后序循环（双栈）
void PostOrder_Loop(BiTree T)
{
/*后序遍历：循环办法,两个栈*/
BiTree s = T; //设置S为遍历指针
BiTree node; //设置node指向栈顶元素
ClearStack(&stack_Order); //对栈做清空操作，使之备用
ClearStack(&stack_PostOutput); //对栈做清空操作，使之备用
while (!stack_Order.empty() || s != nullptr)
{ //当栈为空且同时遍历指针S为空的时候，后序访问结束，退出循环
if (s != nullptr)
{
stack_Order.push(s); //s不空 则s入order栈
stack_PostOutput.push(s);//s入output栈 ：入栈顺序：根、右、左，则出栈顺序为后序的顺序：左、右、根
s = s->rChild; //若右孩子不空，则一路向右
}
else
{
node = stack_Order.top();//s为空，node取order栈栈顶元素
stack_Order.pop(); //order栈弹出栈顶元素
s = node->lChild; //s指向栈顶元素的左子树
}
}
while (!stack_PostOutput.empty())
{ // output栈 ：入栈顺序：根、右、左，则出栈顺序为后序的顺序：左、右、根
visit(stack_PostOutput.top());
stack_PostOutput.pop();
}
}
后序循环（单栈）
void PostOrder_Loop_new_singleStack(BiTree T)
{
/*后序遍历：循环办法，只用一个栈实现*/
ClearStack(&stack_Order);
BiTree s = T; //作为遍历指针
BiTree node; //指向栈顶节点
BiTree prior_node = nullptr; //指向前一个刚刚访问过的指针
while(s!=nullptr || !stack_Order.empty()){
if(s != nullptr)
{
stack_Order.push(s);//s不空，则入栈
s = s->lChild; //s一路向左
}
else
{
node = stack_Order.top();//当s为空时，node取栈顶元素
if(node->rChild && node->rChild != prior_node)
{//若栈顶元素的右子树存在且尚未被访问过，则s转向栈顶元素node的右子树
s = node->rChild;
}
else
{
visit(node); //若其没有右子树或者其右子树已经访问过了，访问node栈顶元素本身
stack_Order.pop();//弹出栈顶元素node
prior_node = node;//将node元素设为刚刚访问的元素
s = nullptr; //s被置空
}
}
}
}
层序循环（队列）
void levelOrder_new(BiTree T)
{
/*层序遍历：利用队列搜索*/
ClearQueue(&queue_LevelOrder);
if (T != nullptr)
{
queue_LevelOrder.push(T);
}
while (!queue_LevelOrder.empty())
{
//s出队，s的左右子树顺序入队，访问出队的s,实现层序遍历
BiTree s = queue_LevelOrder.front();
queue_LevelOrder.pop();
if (s->lChild != nullptr)
{
queue_LevelOrder.push(s->lChild);
}
if (s->rChild != nullptr)
{
queue_LevelOrder.push(s->rChild);
}
visit(s);
}
}
源代码验证实现
//
// Created by 15328 on 2022/1/26.
//
#include <bits/stdc++.h>
typedef double elementType;//任意给定某个数据类型作为此二叉树的节点的数据类型
using namespace std;
typedef struct BiTNode
{
elementType data;
struct BiTNode *lChild, *rChild;
// struct BiTNode *parent;//父节点指针
} BiTNode, *BiTree;
elementType test_value = 0;
BiTree initTree()
{
/*初始化一个根节点
* （或者初始化非根节点的时候调用此函数参与构造）*/
BiTree root = (BiTree)malloc(sizeof(BiTNode));
root->data = -1;
root->lChild = nullptr;
root->rChild = nullptr;
return root;
}
BiTree insertBiTree_left(BiTree root, elementType newData)
{
/*在root节点之后插入新左侧节点*/
if (root != nullptr)
{
BiTree newBiNode = initTree();
newBiNode->data = newData;
root->lChild = newBiNode;
return root->lChild;
}
else
{
return nullptr;
}
}
BiTree insertBiTree_right(BiTree root, elementType newData)
{
/*在root节点之后插入新右侧节点*/
if (root != nullptr)
{
BiTree newBiNode = initTree();
newBiNode->data = newData;
root->rChild = newBiNode;
return root->rChild;
}
else
{
return nullptr;
}
}
void visit(BiTree T)
{
if (T != nullptr)
{
/*访问该结点的操作函数*/
std::cout << T->data << "\t";
}
else
{
std::cout << "null"
<< "\t";
}
}
/*二叉树的先中后序遍历：*/
void PreOrder(BiTree T)
{
/*先序遍历：递归遍历*/
if (T != nullptr)
{
visit(T);//访问根节点
PreOrder(T->lChild);//遍历左子树
PreOrder(T->rChild);//遍历右子树
}
}
void InOrder(BiTree T)
{
/*中序遍历：递归遍历*/
if (T != nullptr)
{
InOrder(T->lChild);//遍历左子树
visit(T);//访问根节点
InOrder(T->rChild);//遍历右子树
}
}
void PostOrder(BiTree T)
{
/*后序遍历：递归办法*/
if (T != nullptr)
{
PostOrder(T->lChild);//遍历左子树
PostOrder(T->rChild);//遍历右子树
visit(T);//访问根节点
}
}
std::stack<BiTree> stack_Order; /*三种遍历的单栈法都要用到存储栈*/
std::stack<BiTree> stack_PostOutput; /*双栈法后序遍历中存储需要输出的遍历序列*/
std::queue<BiTree> queue_LevelOrder; /*层序遍历中利用队列的先进先出的性质实现层序访问*/
bool ClearStack(std::stack<BiTree>* stack)
{/*清空栈*/
if (stack != nullptr)
{
while (!(*stack).empty())
{
(*stack).pop();
}
return true;
}
else
{
return false;
}
}
bool ClearQueue(std::queue<BiTree>* queue)
{/*清空队列*/
if (queue != nullptr)
{
while (!(*queue).empty())
{
(*queue).pop();
}
return true;
}
else
{
return false;
}
}
void PreOrder_Loop(BiTree T)
{
/*先序遍历：循环办法*/
BiTree s = T;//设置s为遍历指针
BiTree node;//设置指针node指向栈顶元素
ClearStack(&stack_Order);//对栈做清空操作，使之备用
while (!stack_Order.empty() || s != nullptr)
{//当栈为空且同时遍历指针S为空的时候，先序访问结束，退出循环
if (s != nullptr)
{
visit(s); //访问当前节点
stack_Order.push(s);//并将其入栈
s = s->lChild; //若其左孩子不空，则一直向左走
}
else
{
node = stack_Order.top();//s为空，取出栈顶元素
stack_Order.pop(); //栈顶元素出栈
s = node->rChild; //转向栈顶元素的右子树
}
}
}
void InOrder_Loop(BiTree T)
{
/*中序遍历：循环办法*/
BiTree s = T;//设置S为遍历指针
BiTree node;//设置node指向栈顶元素
ClearStack(&stack_Order);//对栈做清空操作，使之备用
while (!stack_Order.empty() || s != nullptr)
{ //当栈为空且同时遍历指针S为空的时候，中序访问结束，退出循环
if (s != nullptr)
{
stack_Order.push(s);//s不空，s入栈
s = s->lChild; //左孩子不空，则一直向左走
}
else
{
node = stack_Order.top();//s为空，node取栈顶元素
stack_Order.pop(); //栈顶元素出栈
visit(node); //访问栈顶元素
s = node->rChild; //转向栈顶元素的右子树
}
}
}
void PostOrder_Loop(BiTree T)
{
/*后序遍历：循环办法,两个栈*/
BiTree s = T; //设置S为遍历指针
BiTree node; //设置node指向栈顶元素
ClearStack(&stack_Order); //对栈做清空操作，使之备用
ClearStack(&stack_PostOutput); //对栈做清空操作，使之备用
while (!stack_Order.empty() || s != nullptr)
{ //当栈为空且同时遍历指针S为空的时候，后序访问结束，退出循环
if (s != nullptr)
{
stack_Order.push(s); //s不空 则s入order栈
stack_PostOutput.push(s);//s入output栈 ：入栈顺序：根、右、左，则出栈顺序为后序的顺序：左、右、根
s = s->rChild; //若右孩子不空，则一路向右
}
else
{
node = stack_Order.top();//s为空，node取order栈栈顶元素
stack_Order.pop(); //order栈弹出栈顶元素
s = node->lChild; //s指向栈顶元素的左子树
}
}
while (!stack_PostOutput.empty())
{ // output栈 ：入栈顺序：根、右、左，则出栈顺序为后序的顺序：左、右、根
visit(stack_PostOutput.top());
stack_PostOutput.pop();
}
}
void PostOrder_Loop_new_singleStack(BiTree T)
{
/*后序遍历：循环办法，只用一个栈实现*/
ClearStack(&stack_Order);
BiTree s = T; //作为遍历指针
BiTree node; //指向栈顶节点
BiTree prior_node = nullptr; //指向前一个刚刚访问过的指针
while(s!=nullptr || !stack_Order.empty()){
if(s != nullptr)
{
stack_Order.push(s);//s不空，则入栈
s = s->lChild; //s一路向左
}
else
{
node = stack_Order.top();//当s为空时，node取栈顶元素
if(node->rChild && node->rChild != prior_node)
{//若栈顶元素的右子树存在且尚未被访问过，则s转向栈顶元素node的右子树
s = node->rChild;
}
else
{
visit(node); //若其没有右子树或者其右子树已经访问过了，访问node栈顶元素本身
stack_Order.pop();//弹出栈顶元素node
prior_node = node;//将node元素设为刚刚访问的元素
s = nullptr; //s被置空
}
}
}
}
void levelOrder_old(BiTree root, int level)
{
/*递归求层序遍历结果（每一层）*/
if (root == nullptr || level < 1)
{
return;
}
if (level == 1)
{
visit(root);
}
levelOrder_old(root->lChild, level - 1);
levelOrder_old(root->rChild, level - 1);
}
int highLength(BiTree root)
{
/*递归求树的高度*/
int l_length = 0;
int r_length = 0;
if (root == nullptr)
{
return 0;
}
else
{
l_length = highLength(root->lChild);
r_length = highLength(root->rChild);
if (l_length < r_length)
{
return r_length + 1;
}
else
{
return l_length + 1;
}
}
}
void levelOrder(BiTree T)
{
/*递归遍历层序*/
if (T == nullptr)
{
return;
}
int depth = highLength(T);
for (int i = 1; i <= depth; i++)
{
levelOrder_old(T, i);
}
}
void levelOrder_new(BiTree T)
{
/*层序遍历：利用队列搜索*/
ClearQueue(&queue_LevelOrder);
if (T != nullptr)
{
queue_LevelOrder.push(T);
}
while (!queue_LevelOrder.empty())
{
//s出队，s的左右子树顺序入队，访问出队的s,实现层序遍历
BiTree s = queue_LevelOrder.front();
queue_LevelOrder.pop();
if (s->lChild != nullptr)
{
queue_LevelOrder.push(s->lChild);
}
if (s->rChild != nullptr)
{
queue_LevelOrder.push(s->rChild);
}
visit(s);
}
}
void test()
{
BiTree root = initTree();
BiTree root1 = root;
srand(time(nullptr));
/*用当前时间设置一个随机数种子*/
root->data = 5779*5607%100;
for (int i = 1; i < 3; i++)
{
test_value = rand() % 100;
//获取一百以内elementType类型随机数
root1 = insertBiTree_left(root1, test_value);
test_value = rand() % 100;
root1 = insertBiTree_right(root1, test_value);
}
root1 = root;
for (int i = 1; i < 3; i++)
{
test_value = rand() % 100;
root1 = insertBiTree_right(root1, test_value);
test_value = rand() % 100;
root1 = insertBiTree_left(root1, test_value);
}
/*BiTree root2 = root;
root1 = insertBiTree_left(root1,2);
root2 = insertBiTree_right(root2,5);
root2 = root1;
root1 = insertBiTree_left(root1,3);
root2 = insertBiTree_right(root2,4);*/
std::cout << "先序递归： ";
PreOrder(root);
std::cout << endl;
std::cout << "中序递归： ";
InOrder(root);
std::cout << endl;
std::cout << "后序递归： ";
PostOrder(root);
std::cout << endl;
std::cout << "层序递归： ";
levelOrder(root);
std::cout << endl;
std::cout << "先序循环： ";
PreOrder_Loop(root);
std::cout << endl;
std::cout << "中序循环: ";
InOrder_Loop(root);
std::cout << endl;
std::cout << "后序循环(双栈): ";
PostOrder_Loop(root);
std::cout << endl;
std::cout << "后序循环(单栈): ";
PostOrder_Loop_new_singleStack(root);
std::cout << endl;
std::cout << "层序循环： ";
levelOrder_new(root);
std::cout << std::endl;
}
int main()
{
test();
}
验证结果
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
0
0- 0
已为社区贡献2条内容
所有评论(0)