C/C++ 利用栈并且采用非递归先序算法建立二叉树，是建立～，请问有谁能回答，重奖～需要完整可在VC++6.0

Question

需要完整可在VC++6.0运行的源代码，最好能有一定的注释～谢谢

Answer 1

#include <stdio.h>
#include<malloc.h>
#define MaxSize 100

typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *left,*right;
} BTree;

void creatree(BTree **BT,char *str)
{
BTree *stack[MaxSize],*p;
int top=-1,k,j=0;
char ch;
*BT=NULL;
ch=str[j];
while (ch!='\0')
{
switch(ch)
{
case '(':
top++;
stack[top]=p;
k=1; //k=1为左结点
break;
case ')':
top--;
break;
case ',':
k=2; //k=2为右结点
break;
default:
p=(BTree *)malloc(sizeof(BTree));
p->data=ch;
p->left=p->right=NULL;
if (*BT==NULL)
*BT=p;
else
{
switch(k)
{
case 1:stack[top]->left=p;
break;
case 2:stack[top]->right=p;
break;
}
}
}
ch=str[++j];
}
}

void preorder(BTree *BT)//前序遍历递归算法
{
if (BT!=NULL)
{
printf("%c",BT->data);
preorder(BT->left);
preorder(BT->right);
}
}
void preorder1(BTree *BT)//前序遍历非递归算法
{
BTree*p,*stack[MaxSize];
int top=-1;
p=BT;
while(top!=-1||p!=NULL)
{
while(p!=NULL)
{
printf("%c",p->data);
stack[++top]=p;
p=p->left;
}
if(top!=-1)
{
p=stack[top--];
p=p->right;
}
}
}

void inorder(BTree *BT)//中序遍历递归算法
{
if (BT!=NULL)
{
inorder(BT->left);
printf("%c",BT->data);
inorder(BT->right);
}
}
void inorder1(BTree *BT)//中序遍历非递归算法
{
BTree *p,*stack[MaxSize];
int top=-1;
p=BT;
while(top!=-1||p!=NULL)
{
while(p!=NULL)
{
stack[++top]=p;
p=p->left;
}
if(top!=-1)
{
p=stack[top--];
printf("%c",p->data);
p=p->right;
}
}
}

void postorder(BTree *BT)//后序遍历递归算法
{
if (BT!=NULL)
{
postorder(BT->left);
postorder(BT->right);
printf("%c",BT->data);
}
}
void postorder1(BTree *BT)//后序遍历非递归算法
{
typedef enum{L,R} tagtype;
typedef struct
{
BTree *ptr;
tagtype tag;
}stacknode;
stacknode x;
BTree *p;
stacknode stack[MaxSize];
int top=-1;
p=BT;
do
{
while (p!=NULL)
{
x.ptr = p;
x.tag = L;//标记为左子树
stack[++top]=x;
p=p->left;
}
while (top!=-1 && stack[top].tag==R)
{
x=stack[top];
top--;
p=x.ptr;
printf("%c",p->data);
}
if (top!=-1)
{
stack[top].tag=R;//标记为左子树
p=stack[top].ptr->right;
}
}while (top!=-1);
}

int BTreeDepth(BTree *BT)//树的深度
{
int leftdep,rightdep;
if (BT==NULL)
return(0);
else
{
leftdep=BTreeDepth(BT->left);
rightdep=BTreeDepth(BT->right);
if (leftdep>rightdep)
return(leftdep+1);
else
return(rightdep+1);
}
}

int leafcount(BTree *BT)//叶子结点数
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(1);
else
return(leafcount(BT->left)+leafcount(BT->right));
}

void main()
{
BTree *BT;
char *s="A(B(D,E(H,I)),C(F,G))";
creatree(&BT,s);
printf("\n前序遍历(递归算法):");
preorder(BT);
printf("\n前序遍历(非递归算法):");
preorder1(BT);
printf("\n中序遍历(递归算法):");
inorder(BT);
printf("\n中序遍历(非递归算法):");
inorder1(BT);
printf("\n后序遍历(递归算法):");
postorder(BT);
printf("\n后序遍历(非递归算法):");
postorder1(BT);
printf("\nThe depth is %d\n",BTreeDepth(BT));
printf("The leaves is %d\n",leafcount(BT));
}追问

貌似没有用到栈吧？

追答

你可能不是很了解什么是栈呀，栈就是一种，后进先出的的数据结构呀，具体形式有很多的，最简单是就是用数组实现呀，当然还有链表实现的，栈只是一种工具而已，不是什么数据类型

Answer 2

建立，还是遍历追问

建立

追答

再把你的问题详细描述，如：输入是什么、输出是什么、用到什么算法、数据结构

追问

二叉树的二叉链表示法，输入输出为字符数据，没什么其他特别的要求