一个C语言程序非递归中序遍历二叉树

#include

#include

typedef

struct

bitnode

{

char

data

struct

bitnode

*lchild,*rchild

}bitnode,*bitree

bitree

create_tree()

//悉山先序创建

{

char

abitree

root

scanf("%c",&a)

fflush(stdin)

if(a=='#')return

NULL

else

{

root=(bitnode

*)malloc(sizeof(bitnode))

root->data=a

root->lchild=create_tree()

root->rchild=create_tree()

}

return

root

}

void

inorder(bitree

root)//中根遍历

{

bitree

s[100]

int

top=0

while(root||top)

{

while(root)

{

s[++top]=rootroot=root->lchild

}

if(top)

{

putchar(s[top]->data)

root=s[top--]->rchild

}

}

}

void

main()

{

bitree

root=NULL

root=create_tree()//输入序列为先序遍历序列，脊陆烂＃代表空

inorder(root)

printf("\n")

}

//例如输入a(回车）b（回车）#（回车）#(回车樱漏）c(回车）#（回车）#(回车）输出bac

文件 main.cpp 代码如下：

#include<malloc.h>// malloc()等

#include<stdio.h>// 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等

#include<stdlib.h>// atoi()，exit()

#include<math.h>// 数学函数头文件，包括floor()，ceil()，abs()等

#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的 *** 作一样

typedef struct BiTNode

{

int data// 结点的值

BiTNode *lchild,*rchild// 左右孩子指针

}BiTNode,*BiTree

int Nil=0// 设整型以0为空

void visit(int e)

{ printf("%d ",e)// 以整型格式输出

}

void InitBiTree(BiTree &T)

{ // *** 作结果：构造空二叉树T

T=NULL

}

void CreateBiTree(BiTree &T)

{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，

// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修咐凯改

int number

scanf("%d",&number)// 输入结点的值

if(number==Nil) // 结点的值为空

T=NULL

else // 结点的值不为空

{ T=(BiTree)malloc(sizeof(BiTNode))// 生成根结点

if(!T)

exit(OVERFLOW)

T->data=number// 将值赋给T所指结点

CreateBiTree(T->lchild)// 递归构造左子树

CreateBiTree(T->rchild)// 递归构造右子树

}

}

void DestroyBiTree(BiTree &T)

{ // 初始条件：二叉树T存在。 *** 作结果：销毁二叉树T

if(T) // 非空树

{ DestroyBiTree(T->lchild)//镇简中 递归销毁左子树，如无左子树，则不执行任何 *** 作

DestroyBiTree(T->rchild)// 递归销毁右子树，如无右子树，则不执行任何 *** 作

free(T)// 释放根结点

T=NULL// 空指针赋0

}

}

void PreOrderTraverse(BiTree T,void(*Visit)(int))

{ // 初始条件：二叉树T存在，Visit是对结点 *** 作的应用函数。修改算法6.1

// *** 作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次

if(T) // T不空

{ Visit(T->data)// 先访问根结点

PreOrderTraverse(T->lchild,Visit)// 再先序遍历左子树

PreOrderTraverse(T->rchild,Visit)// 最后先序遍历右御山子树

}

}

void InOrderTraverse(BiTree T,void(*Visit)(int))

{ // 初始条件：二叉树T存在，Visit是对结点 *** 作的应用函数

// *** 作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次

if(T)

{ InOrderTraverse(T->lchild,Visit)// 先中序遍历左子树

Visit(T->data)// 再访问根结点

InOrderTraverse(T->rchild,Visit)// 最后中序遍历右子树

}

}

void PostOrderTraverse(BiTree T,void(*Visit)(int))

{ // 初始条件：二叉树T存在，Visit是对结点 *** 作的应用函数

// *** 作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次

if(T) // T不空

{ PostOrderTraverse(T->lchild,Visit)// 先后序遍历左子树

PostOrderTraverse(T->rchild,Visit)// 再后序遍历右子树

Visit(T->data)// 最后访问根结点

}

}

void main()

{

BiTree T

InitBiTree(T)// 初始化二叉树T

printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n")

CreateBiTree(T)// 建立二叉树T

printf("先序递归遍历二叉树：\n")

PreOrderTraverse(T,visit)// 先序递归遍历二叉树T

printf("\n中序递归遍历二叉树：\n")

InOrderTraverse(T,visit)// 中序递归遍历二叉树T

printf("\n后序递归遍历二叉树：\n")

PostOrderTraverse(T,visit)// 后序递归遍历二叉树T

}

这样可以么？

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。巧枣 例如如下的先序遍历字知绝符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入包括1行字符串，长度不超过100。

可能有多组测试数据，对于每组数据，

输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。

每个输出结搭宽姿果占一行。

abc##de#g#f###

c b e g d f a

---