树的非递归遍历（中序遍历栈实现）

树的非递归遍历（中序遍历栈实现）

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAXSIZE 100
typedef int Status;
typedef char ElemType;
typedef struct Node
{
char data;
struct Node* lchild, * rchild;
}*BiTree, BiNode;
typedef struct SNode
{
BiTree *top;
BiTree *base;
int capacity;
}Stack, SNode;
Status Great(BiTree T)//建立一棵树
{
char e;
scanf("%c", &e);
if (e == ‘#’)
(*T) = NULL;
else
{
(T) = (BiNode)malloc(sizeof(BiNode));
if (!(*T)) exit(0);
(*T)->data = e;
Great(&(*T)->lchild);
Great(&(*T)->rchild);
}
return OK;
}
Status leafnode(BiTree T)//求叶子结点数
{
if(TNULL) return 0;
else if(T->lchildNULL&&T->rchildNULL)
{
return 1;
}
else
return leafnode(T->lchild)+leafnode(T->rchild);
}
Status Nodecount(BiTree T)//求树的节点总数
{
if(TNULL) return 0;
else if(T->lchildNULL&&T->rchildNULL)
{
return 1;
}
else
return Nodecount(T->lchild)+Nodecount(T->rchild)+1;
}
Status Depth(BiTree T)//求树的深度
{
if(T==NULL) return 0;
else
{
int m,n;
m=Depth(T->lchild);
n=Depth(T->rchild);
if(m>n)
return (m+1);
else
return (n+1);
}
}

Status Greats(Stack S)//建立栈
{
S->base = (BiTree*)malloc(MAXSIZE * sizeof(BiTree));
if (!S->base) exit(0);
S->top = S->base;
S->capacity = MAXSIZE;
return OK;
}
Status Push(Stack S, BiTree e)
{
*(S->top)= e;
S->top++;
return OK;
}
Status Pop(Stack S, BiTree *e)
{
*e = *(–S->top);
return OK;
}
Status isEmpty(Stack S)
{
if (S->top == S->base)
{
return 1;
}
else return 0;
}

Status Midtraverst(BiTree &T)//用栈实现树的非递归中序遍历
{
SNode S;
Greats(&S);
BiTree p;
p = T;
while (p || !isEmpty(&S))
{
if §
{

		Push(&S, p);
		p = p->lchild;
	}
	else
	{
		Pop(&S, &p);
		printf("%c", p->data);
		p = p->rchild;
	}
}
return OK;

}

/Status Midtraverst(BiTree &T)//用递归实现中序遍历
{
if(T==NULL) return OK;
else{
Midtraverst(T->lchild);
printf("%c",T->data);
Midtraverst(T->rchild);
}
}/
int main()
{
int n,m,d;
BiTree T;
Great(&T);
d=Depth(T);
n= leafnode(T);
m=Nodecount(T);
printf(“叶子结点：%d\n结点总数：%d\n树的深度：%d\n”,n,m,d);
printf(“树的先序遍历：%d”);
Midtraverst(T);
return 0;
}

输入的树是这个样子：

运行结果：