#include <stdio.h>
#include <stdlib.h>
#define maxValue 1000
struct binTreeNode{
int data;
binTreeNode * left,*right;
};
binTreeNode * root;
/*
递归创建二叉树,返回根节点指针
输入要求:类似先根遍历的输入顺序,如果哪个节点的孩子为空,那么输入0
例如针对
1
2 3
4 5 6 7
输入顺序为:
1 2 4 0 0 5 0 0 3 6 0 0 7 0 0
针对 1
2 3
4 5 0 7
输入顺序为:
1 2 4 0 0 5 0 0 3 0 7 0 0
*/
binTreeNode * recCreateBinTree()
{
int _data = 0;
binTreeNode * r;
scanf("%d",&_data);
if(_data == 0)
r = NULL;
else
{
r = (binTreeNode*)malloc(sizeof(binTreeNode));
r->data = _data;
r->left = recCreateBinTree();
r->right = recCreateBinTree();
}
return r;
}
/*
递归版本的先根遍历
*/
void recPreOrder(binTreeNode *root)
{
if(root != NULL)
{
printf("%d\n",root->data);
recPreOrder(root->left);
recPreOrder(root->right);
}
}
/*
递归版本的中根遍历
*/
void recInOrder(binTreeNode *root)
{
if(root != NULL)
{
recInOrder(root->left);
printf("%d\n",root->data);
recInOrder(root->right);
}
}
/*
递归版本的后根遍历
*/
void recPostOrder(binTreeNode *root)
{
if(root != NULL)
{
recPostOrder(root->left);
recPostOrder(root->right);
printf("%d\n",root->data);
}
}
/*
层次遍历
利用数组模拟队列
但是当元素多于1000时候,不可处理
*/
void leverOrder(binTreeNode * root)
{
binTreeNode * queue[1000];
binTreeNode *tmp;
int head = 0;
int tail = 0;
if(root != NULL)
{
queue[tail] = root; //队列操作,while前边先压入首元素
tail ++ ;
while(tail > head)
{
tmp = queue[head]; //弹出队列头元素
head ++;
printf("%d\n",tmp->data); //针对首元素的操作
//压入后继元素
if(tmp->left != NULL)
{
queue[tail] = tmp->left;
tail ++ ;
}
if(tmp->right != NULL)
{
queue[tail] = tmp->right;
tail ++;
}
}
}
}
/*
层次遍历
利用数组模拟队列
而且利用取余,模拟循环队列
*/
void leverOrder2(binTreeNode * root)
{
binTreeNode * queue[maxValue];
binTreeNode *tmp;
int head = 0;
int tail = 0;
if(root != NULL)
{
queue[tail] = root; //队列操作,while前边先压入首元素
tail ++ ;
while(tail != head)
{
tmp = queue[head]; //弹出队列头元素
head = (head + 1) % maxValue;
printf("%d\n",tmp->data); //针对首元素的操作
//压入后继元素
if(tmp->left != NULL)
{
queue[tail] = tmp->left;
tail = (tail + 1)% maxValue;
}
if(tmp->right != NULL)
{
queue[tail] = tmp->right;
tail = (tail + 1)% maxValue;
}
}
}
}
int main()
{
freopen("in.txt","r",stdin);
root = recCreateBinTree();
fclose(stdin);
printf("preOrder:\n");
recPreOrder(root);
printf("inOrder:\n");
recInOrder(root);
printf("postOrder:\n");
recPostOrder(root);
printf("leverOrder:\n");
leverOrder2(root);
return 0;
}
分享到:
相关推荐
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
二叉树的创建与三种遍历的递归与非递归实现 包括二叉树的动态创建,前序遍历,中序遍历,后续遍历的递归与非递归方法的实现。
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
二叉树递归与非递归遍历
中根顺序递归建立二叉树,递归及非递归遍历二叉树。C++面向过程实现
递归先序遍历二叉树: 递归中序遍历二叉树: 递归后序遍历二叉树: 非递归先序遍历二叉树: 非递归中序遍历二叉树: 非递归后序遍历二叉树: 非递归中序遍历二叉树(算法2): 层次遍历二叉树: 递归计算单...
数据结构 二叉树三种遍历的非递归算法(背诵版). 数据结构 二叉树三种遍历的非递归算法(背诵版). 数据结构 二叉树三种遍历的非递归算法(背诵版).
二叉树深度 二叉树前序遍历 递归实现 二种非递归实现 二叉树中序遍历: 递归实现 非递归实现 二叉树后序遍历: ...二叉树层次创建,创建方法遵循卡特兰数 http://write.blog.csdn.net/postedit/17380455
按先序遍历的扩展序列建立二叉树的二叉链表存储结构,实现二叉树先序、中序、后序遍历的递归算法,实现二叉树中序遍历的非递归算法,实现二叉树层次遍历的非递归算法(要求使用顺序队列,调用顺序队列基本操作...
二叉树先序、中序、后序三种遍历的非递归算法
二叉树的三种遍历,递归与非递归,按层。适合初学者。
二叉树的基本操作,C语言编码,包括二叉树的创建,非递归先序中序和后序遍历,叶子结点的数目以及求树的高度
二叉树先序、中序、后序遍历非递归算法,简述了二叉树的基本算法。
二叉树的非递归遍历 二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历
二叉树的非递归中序遍历 C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码
C语言实现二叉树的前序遍历(非递归),下载下来看看哦!
二叉树的非递归遍历,使用C++实现二叉树的非递归遍历,对正在学习算法的同学应该挺有帮助的
C语言实现二叉树的前序、中序、后续遍历(递归法),大家可以看看哈。。。
二叉树先序、中序、后序遍历(递归、非递归算法) 其中自己已经开发了栈!