//(递归的)
#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
//#include<math.h>
typedef struct node *BiTree;
struct node{
char ch;
BiTree Lchild,Rchild;
};
BiTree root=NULL;
//创建二叉树
BiTree create(BiTree bt)
{
char ch;
scanf("%c",&ch);
if(ch=='$')
bt=NULL;
else{
bt=(BiTree)malloc(sizeof(node));
bt->ch=ch;
bt->Lchild=create(bt->Lchild);
bt->Rchild=create(bt->Rchild);
}
return bt;
}
//先序遍历二叉树
void PreOrder(BiTree bt)
{
if(bt){
printf("%c",bt->ch);
PreOrder(bt->Lchild);
PreOrder(bt->Rchild);
}
}
//中序遍历二叉树
void InOrder(BiTree bt)
{
if(bt){
InOrder(bt->Lchild);
printf("%c",bt->ch);
InOrder(bt->Rchild);
}
}
//后序遍历二叉树
void PostOrder(BiTree bt)
{
if(bt){
PostOrder(bt->Lchild);
PostOrder(bt->Rchild);
printf("%c",bt->ch);
}
}
//求m的n次方
int pow(int m,int n){
int i,dr=1;
for(i=0;i<n;i++){
dr*=m;
}
return dr;
}
//求结点总数
int NodeCount(BiTree bt){
int BiTreeNodeCount=0,btl,btr;
if(bt!=NULL){
BiTreeNodeCount++;
btl=NodeCount(bt->Lchild);
btr=NodeCount(bt->Rchild);
BiTreeNodeCount=btl+btr+1;
}
return BiTreeNodeCount;
}
//求二叉树深度
int TreeDepth(BiTree bt){
int depth=0,dl,dr;
if(bt!=NULL){
dl=TreeDepth(bt->Lchild);
dr=TreeDepth(bt->Rchild);
depth=dl>dr ? dl:dr;
return (depth+1);
}else{
return depth;
}
}
//判断该二叉树是否为满二叉树?
void IsFullBinaryTree(BiTree bt){
if(NodeCount(bt)==(pow(2,TreeDepth(bt))-1)){
printf("此二叉树是满二叉树!\n");
}else{
printf("此二叉树不是满二叉树!\n");
}
}
void main()
{
printf("请输入你要构建的二叉树序列:形如(ABC$$DE$G$$F$$$,其中'$'代表空格符)\n");
root=create(root);
printf("前序遍历二叉树:\n");
PreOrder(root);
printf("\n");
printf("中序遍历二叉树:\n");
InOrder(root);
printf("\n");
printf("后序遍历二叉树:\n");
PostOrder(root);
printf("\n");
IsFullBinaryTree(root);
}
//(非递归的)
#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
#define MAX_STACK_SIZE 100
typedef struct node *BiTree;
struct node{
char ch;
BiTree Lchild,Rchild;
};
BiTree root=NULL;
BiTree stack[MAX_STACK_SIZE];
int top=-1;
//入栈
void push(int *top,BiTree item)
{
if(*top>=MAX_STACK_SIZE-1)
printf("此栈已满!\n");
else
stack[++*top]=item;
}
//出栈
BiTree pop(int *top)
{
if(*top==-1)
return NULL;
return stack[(*top)--];
}
//创建二叉树
BiTree create(BiTree bt)
{
char ch;
scanf("%c",&ch);
if(ch=='$')
bt=NULL;
else{
bt=(BiTree)malloc(sizeof(node));
bt->ch=ch;
bt->Lchild=create(bt->Lchild);
bt->Rchild=create(bt->Rchild);
}
return bt;
}
//先序遍历二叉树
void iter_PreOrder(BiTree bt)
{
for(;;){
for(;bt;bt=bt->Lchild){
printf("%c",bt->ch);
push(&top,bt);
}
bt=pop(&top);
if(!bt) break;
bt=bt->Rchild;
}
}
//中序遍历二叉树
void iter_InOrder(BiTree bt)
{
for(;;){
for(;bt;bt=bt->Lchild)
push(&top,bt);
bt=pop(&top);
if(!bt) break;
printf("%c",bt->ch);
bt=bt->Rchild;
}
}
//后序遍历二叉树
void iter_PostOrder(BiTree bt)
{
int flag[MAX_STACK_SIZE];
for(;;){
for(;bt&&bt->ch;bt=bt->Lchild){
push(&top,bt);
flag[top]=1;
}
bt=pop(&top);
if(!bt) break;
if(flag[top+1]){
push(&top,bt);
flag[top]=0;
}
else{
printf("%c",bt->ch);
bt->ch=NULL;
}
bt=bt->Rchild;
}
}
//求m的n次方
int pow(int m,int n){
int i,dr=1;
for(i=0;i<n;i++){
dr*=m;
}
return dr;
}
//求结点总数
int NodeCount(BiTree bt){
int BiTreeNodeCount=0,btl,btr;
if(bt!=NULL){
BiTreeNodeCount++;
btl=NodeCount(bt->Lchild);
btr=NodeCount(bt->Rchild);
BiTreeNodeCount=btl+btr+1;
}
return BiTreeNodeCount;
}
//求二叉树深度
int TreeDepth(BiTree bt){
int depth=0,dl,dr;
if(bt!=NULL){
dl=TreeDepth(bt->Lchild);
dr=TreeDepth(bt->Rchild);
depth=dl>dr ? dl:dr;
return (depth+1);
}else{
return depth;
}
}
//判断该二叉树是否为满二叉树?
void IsFullBinaryTree(BiTree bt){
if(NodeCount(bt)==(pow(2,TreeDepth(bt))-1)){
printf("此二叉树是满二叉树!\n");
}else{
printf("此二叉树不是满二叉树!\n");
}
}
void main()
{
printf("请输入你要构建的二叉树序列:形如(ABC$$DE$G$$F$$$,其中'$'代表空格符)\n");
root=create(root);
printf("迭代的前序遍历二叉树:\n");
iter_PreOrder(root);
printf("\n");
printf("迭代的中序遍历二叉树:\n");
iter_InOrder(root);
printf("\n");
printf("迭代的后序遍历二叉树:\n");
iter_PostOrder(root);
printf("\n");
IsFullBinaryTree(root);
}
分享到:
相关推荐
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
二叉树先序、中序、后序遍历非递归算法,简述了二叉树的基本算法。
这是数据结构中二叉树的后序遍历的非递归算法的源代码。
二叉树先序、中序、后序遍历(递归、非递归算法) 其中自己已经开发了栈!
二叉树先序、中序、后序三种遍历的非递归算法
后序遍历二叉树非递归算法的推导及形式化证明,难得的期刊论文资料,对研究二叉树的非递归性遍历有很大帮助
自己编写的实验二叉树的后序遍历非递归算法 包括以递归中序遍历建立二叉树 前序,中序,后序递归以及非递归实现二叉树的遍历 经vc6.0编译通过 自己实验,不足之处应该很多,望指出
非递归中序遍历二叉树(算法2): 层次遍历二叉树: 递归计算单分支结点: 递归计算双分支结点: 递归计算叶子数: 二叉数的深度: 交换二叉树的左右子树: 二叉树已左右交换。 递归先序遍历二叉树: 递归...
二叉树后序遍历的非递归算法,后序遍历运算
数据结构二叉树链式结构的前序遍历,中序遍历,后序遍历用递归的方法,层级遍历采用队列结构
二叉树的基本操作,包括前序、中序、后序遍历的递归和非递归算法,不得不下的资源
数据结构中关于二叉树的遍历,非递归算法数上未给出
本程序采用非递归方法实现对二叉树的先序、中序、后序遍历.自定义栈和树的结构。
已知二叉树的前序和中序遍历,打印后序遍历,采用二叉树的非递归算法,分享给大家~~
二叉树的非递归中序遍历 C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码
数据结构上二叉树的递归算法,先序、中序与后序遍历,是用递归算法写的,(用递归写代码比较少且容易看懂,但效率不高)给初学者参考一下。
关于二叉树前序和后序的非递归遍历算法.rar
1.输入前序和中序遍历结果,建立二叉树 2.实现二叉树的三种递归遍历算方法 3.实现二叉树的三种非递归遍历算法 4.实现二叉树的旋转90°后的打印,直观树形结构
包含一下方法: 1.通过一个数组来构造一颗二叉树 2.通过一个数组来构造一颗完全二叉树 3.使用递归 先序遍历一棵...8.使用非递归 后序遍历一棵二叉树 PS:代码为C++代码 可以直接下载使用!!! PS2:每句代码都有详细注释