/* 先序创建一棵任意二叉树 */
/* 注意:输入数据的顺序很有特点,本题输入的顺序要求为,先是根节点,再是左子树,再是右子树 */
#include <iostream>
#include <malloc.h>
using namespace std;
typedef int elementtype; //给int起别名为elementtype, typedef是起别名的意思
typedef struct bitnode //定义二叉树节点数据类型
{
elementtype data;
struct bitnode *left, *right;
} bitnode, *bitree; //bitree为指向bitnode这种结构的指针
//先序创建一棵二叉树
bitree percreatetree()
{
bitree t;
elementtype item;
cin >> item;
if( item == 0 ) //叶节点数据标志:其后根两个0
t = null; //若某一节点为叶子结点,则其左右子树均为null,0表示建空树
else
{
t = (bitree)malloc(sizeof(bitnode));
t->data = item;
t->left = percreatetree(); //递归创建其左子树
t->right = percreatetree(); //递归创建其右子树
}
return t; //返回根节点
}
//先序递归遍历二叉树
void perorder(bitree t)
{
if( t ) // t != null
{
cout << t->data << ” “;
perorder(t->left); //递归先序周游其左子树
perorder(t->right); //递归先序周游其右子树
}
}
void inorder(bitree t)
{
if(t)
{
inorder(t->left);
cout<<t->data<<” “;
inorder(t->right);
}
}
void inorder(bitree t)
{
//还是模拟上面的遍历过程
bitree ptr[20];
int top = -1;
/*下面的双重判断和前面的一样,在进栈、出栈的过程中可能会出现栈空的情况,而此时的遍历还没有结束,
所以需要据此来维持循环的进行。*/
while(t || top!=-1)
{
while(t)
{
ptr[++top] = t;
t = t->left;
}
if(top!=-1)
{
t = ptr[top–];
cout<<t->data<<” “; //输出在出栈后
t = t->right;
}
}
}
//后序递归遍历二叉树
void postorder(bitree t)
{
if( t ) // t != null
{
postorder(t->left); //递归先序周游其左子树
postorder(t->right); //递归先序周游其右子树
cout << t->data << ” “;
}
}
//释放空间
bitree freetree(bitree t)
{
if( t )
{
freetree(t->left); //递归释放其左子树
freetree(t->right); //递归释放其右子树
free(t); //释放根节点
t = null; //释放指向根节点的指针
}
return t; //返回释放后的根节点null
}
int main()
{
bitree root;
cout << “请输入数据先序创建一棵二叉树:”;
root = percreatetree(); //先序创建一棵二叉树
cout << “先序递归遍历的结果:”;
perorder(root); //先序递归遍历
cout << endl;
cout << “中序递归遍历的结果:”;
inorder(root); //中序递归遍历
cout << endl;
cout << “中序非递归遍历的结果:”;
inorder(root); //中序非递归遍历
cout << endl;
cout << “后序递归遍历的结果:”;
postorder(root); //后序递归遍历
cout << endl;
return 0;
}
运行结果:
请输入数据先序创建一棵二叉树:4 6 8 0 0 1 0 0 2 0 0
先序递归遍历的结果:4 6 8 1 2
中序递归遍历的结果:8 6 1 4 2
中序非递归遍历的结果:8 6 1 4 2
后序递归遍历的结果:8 1 6 2 4
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/601025.html