编写C程序，并上机实现：二叉树的创建与遍历， 网上提交“源代码”和“程序运行结果截图”。

Question

程序要求：
1、输入一个二叉树的先序序列串，例如：“ABCΦΦDEΦGΦΦFΦΦΦ”，建立二叉链表（“Φ”代表空）；
2、利用后序遍历求二叉树的深度；
3、层次遍历二叉树，输出遍历序列；
4、用非递归实现二叉树的中序遍历，输出中序序列。
本来想悬赏高点的，可惜财富值不够了，希望懂的大哥帮帮忙，感激不尽啊！谢谢！

Answer 1

#include <iostream>
using namespace std;
//二杈树的二杈线索存储表示
typedef char ElemType;
typedef enum PointerTag {Link, Thread}; //Link:指针,Thread:线索
typedef struct BiThrNode{
ElemType data;
struct BiThrNode *lchild, *rchild;//左，右孩子指针
PointerTag LTag, RTag; //左，右标志
} *BiThrTree;
void InOrderTraverse_Thr(BiThrTree T);//中序遍历线索二杈树的非递归算法, T 指向头结点
void InThreading(BiThrTree & p, BiThrTree & pre); //中序线索化
BiThrTree InOrderThreading(BiThrTree T);//中序遍历二杈树，并将其中序线索化
void CreateBTree(BiThrTree & bt);//生成一棵二杈排序树（输入单个字符，以#结束）
BiThrTree NewBTree(ElemType x);//构造一个数据域为x的新结点
void Insert(BiThrTree & b, BiThrTree s);//在二杈排序树中插入新结点s
void InOrderPrint_1(BiThrTree p); //中序遍历输出结点（递归）
int main()
{
BiThrTree bt = NULL;
CreateBTree(bt);//生成一棵二杈排序树（输入单个字符，以#结束）
InOrderPrint_1(bt); //中序遍历输出结点（递归）
cout << endl;
BiThrTree BT = InOrderThreading(bt);//中序遍历二杈树，并将其中序线索化
InOrderTraverse_Thr(BT);//中序遍历线索二杈树的非递归算法, T 指向头结点
system("PAUSE");
return EXIT_SUCCESS;
}
void InOrderTraverse_Thr(BiThrTree T)//中序遍历线索二杈树的非递归算法, T 指向头结点
{
BiThrTree p = T->lchild; //p指向根结点
while (p != T) //空树或遍历结束时，p == T
{
while (p->LTag == Link)//寻找第一个结点
{
p = p->lchild;
}
cout << p->data << ' ';//输出该结点
while (p->RTag == Thread && p->rchild != T)//访问后继结点
{
p = p->rchild;
cout << p->data << ' ';//输出该结点
}
p = p->rchild;
}
}
void InThreading(BiThrTree & p, BiThrTree & pre) //中序线索化
{
if (p)
{
InThreading(p->lchild, pre); //左子树线索化
if (! p->lchild)//若当前结点的左子树为空，则建立前驱线索
{
p->LTag = Thread;
p->lchild = pre;
}
else
p->LTag = Link;
if (pre && !pre->rchild)//若前驱结点非空，且其右孩子为空，则建立后继线索
{
pre->RTag = Thread;
pre->rchild = p;
}
pre = p; //中序向前遍历接点 ，保持pre指向p的前驱
pre->RTag = Link;//默认前驱结点右孩子非空
InThreading(p->rchild, pre); //右子树线索化
}
}
BiThrTree InOrderThreading(BiThrTree T)//中序遍历二杈树，并将其中序线索化
{
BiThrTree Thrt = new BiThrNode; //建立头结点
if (!Thrt)
{
printf("Out of space!");
return NULL;
}
Thrt->LTag = Link;
Thrt->RTag = Thread;
Thrt->rchild = Thrt; //右指针回指
if (!T)//若二杈树为空，则左指针回指
Thrt->lchild = Thrt;
else
{
Thrt->lchild = T;
BiThrTree pre = Thrt;
InThreading(T, pre);//中序线索化
pre->rchild = Thrt; //最后一个结点线索化
pre->RTag = Thread;
Thrt->rchild = pre; //此时pre指向最后一个结点
}
return Thrt;
}
void CreateBTree(BiThrTree & bt)//生成一棵二杈排序树（输入单个字符，以#结束）
{
ElemType x;
cin >> x;
while (x != '#')
{
BiThrTree s = NewBTree(x);//构造一个数据域为x的新结点
Insert(bt, s);//在二杈排序树中插入新结点s
cin >> x;
}
}
BiThrTree NewBTree(ElemType x)//构造一个数据域为x的新结点
{
BiThrTree s = new BiThrNode;
if (!s)
{
printf("Out of space!");
exit (1);
}
s->data = x;
s->lchild = s->rchild = NULL;
s->LTag = s->RTag = Link;
return s;
}

void Insert(BiThrTree & b, BiThrTree s)//在二杈排序树中插入新结点s
{
if (b == NULL)
b = s;
else if (b->data == s->data)//不做任何插入操作
return;
else if(b->data > s->data)//把s所指结点插入到左子树中
Insert(b->lchild, s);
else //把s所指结点插入到右子树中
Insert(b->rchild, s);
}
void InOrderPrint_1(BiThrTree p) //中序遍历输出结点（递归）
{
if (p != NULL)
{
InOrderPrint_1(p->lchild); //遍历左子树
cout << p->data << ' ';//输出该结点
InOrderPrint_1(p->rchild); //遍历右子树
}
}

Answer 2

#include <stdio.h>
#include <malloc.h>
typedef struct node
{
char data;
struct node *lchild,*rchild;
struct node *parent;
}tree;
tree *bintree;
tree *root;
void create_tree(tree *&t)
{
char ch;
if((ch=getchar())=='#')
{
t=NULL;
}
else
{
t=(tree * )malloc(sizeof(tree));
t->data=ch;
create_tree(t->lchild);
create_tree(t->rchild);
}
}
void print_tree(tree * t)
{
if(t)
{
print_tree(t->lchild);
printf("%c",t->data);
print_tree(t->rchild);
}
}
int main(int argc, char *argv[])
{
create_tree(bintree);
print_tree(bintree);
return 0;
}

在上面程序输入ABC##DE#G##F###输出中序遍历本回答被网友采纳

Answer 3

#include <iostream>
using namespace std;
struct BiTree
{
char data ;
BiTree *left ;
BiTree *right ;
};
BiTree *CreateBiTree()
{
BiTree *S[100],*b,*p;
int i=0,k,l=0,top=0;
char str[100] ;
char ch;
b=NULL;
while((ch=cin.get())!='#')
str[l++]=ch;
str[l]='\0';
while(str[i])
{
switch(str[i])
{
case '(' :S[++top]=p; k=1; break ;
case ')' :top--; break ;
case ',' : k=2; break ;
default :
{
p=new BiTree ;
p->data=str[i];
p->left=NULL;
p->right=NULL ;
if(b==NULL)
b=p;
else
{
switch(k)
{
case 1:S[top]->left=p; break;
case 2:S[top]->right=p; break;
}
}
}
}
i++;
}cout<<"已为您成功录入二叉树!"<<endl;
return b ;

}
void Inorder(BiTree *root)
{
if (root!=NULL)
{
Inorder(root->left );
cout<<root->data;
Inorder(root->right );
}
}
void preorder(BiTree *root)
{ if (root!=NULL)
{
cout<<root->data;
preorder(root->left);
preorder(root->right);
}
}
void lateorder(BiTree *root)
{
if (root!=NULL)
{
lateorder(root->left);
lateorder(root->right);
cout<<root->data;
}
}
void leftorder(BiTree *p)
{
BiTree *qu[100];
int front=0,rear=0;
if(p!=NULL)
cout<<p->data;
rear++;
qu[rear]=p;
while(rear!=front)
{
front=(front+1)%100;
p=qu[front];
if(p->left!=NULL)
{
cout<<p->left->data;
rear=(rear+1)%100;
qu[rear]=p->left;
}
if(p->right!=NULL)
{
cout<<p->right->data;
rear=(rear+1)%100;
qu[rear]=p->right;
}
}
}
int max(int a,int b)
{
return a>b?a:b;
}
int NodeCount ( BiTree *b )
{ int L,R;
if ( b==NULL ) return 0;
L = NodeCount ( b->left );
R = NodeCount ( b->right );
return 1+L+R;
}
int LeafCount ( BiTree *b )
{ int L,R;
if ( b==NULL ) return 0;
if ( b->left==NULL && b->right==NULL)
return 1;
L = LeafCount ( b->left );
R = LeafCount ( b->right );
return L + R;
}
int max1(int a,int b)
{
return a>b?a:b;
}
int Depth ( BiTree *b )
{int L,R;
if ( b==NULL ) return 0;
L=Depth ( b->left );
R=Depth ( b->right );
return 1+max1(L,R);
}

int main()
{
cout<<"欢迎进入:"<<endl;
BiTree *T;
cout<<"请先将您要进行操作的二叉树以广义表的形式录入,以'#'结束输入(例如:A(B,C(,E))#):"<<endl;
T=CreateBiTree( );
int m=100;
char flag;
while(m)
{
cout<<"请选择操作: ";
cin>>flag;
switch(flag)
{
case '0': cout<<"节点个数为:"<<NodeCount(T)<<endl;break;
case '1': cout<<"叶子节点数为:"<<LeafCount(T)<<endl;break;
case '2': cout<<"树的深度为:"<<Depth(T)<<endl;break;
case '3': cout<<"先序遍历:"<<endl;preorder(T);break;
case '4': cout<<"中序遍历:"<<endl;Inorder(T) ;break;
case '5': cout<<"后序遍历:"<<endl;lateorder(T);break;
case '6': cout<<"层次遍历:"<<endl;leftorder(T);break;
case '7': m=1;break;
}
m--;
}
return 0;
}

这个代码就可以，我运行过了，你可以试试追问

你编写的这个程序，符合我问题补充的四点要求吗？你上机运行了吗？没出错误吗？