简单遍历二叉树
2019-11-08 16:01:42来源:博客园 阅读 ()
简单遍历二叉树
/* 先序创建一棵任意二叉树 */
/* 注意:输入数据的顺序很有特点,本题输入的顺序要求为,先是根节点,再是左子树,再是右子树 */
#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
原文链接:https://www.cnblogs.com/liyajuan333/p/11820823.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:C++引用与常量
- 二叉搜索树_BST 2020-05-30
- 二叉树 2020-05-02
- 二叉排序树 2020-05-02
- 加边的无向图--并查集 2020-04-10
- 排兵布阵 2020-02-21
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash