#include <stdio.h>
#include <stdlib.h>
#define STACK-INIT-SIZE 100;
#define STACKINCREMENT 10;
#define MAXSIZE 100
int count0 = 0; //计数器
/**二叉树数据结构定义**/
typedef struct BiTreeNode
{
char data;
struct BiTreeNode *left;
struct BiTreeNode *right;
}BiTreeNode,*BiTree;
typedef struct{
*base;
*top;
int stacksize;
}SqStack;
//构造一个空栈
InitStack(SqStack &S)
S.base=(SElemType * )malloc (STACK-INIT-SIZE * sizeof(ElemType));
if(!S.base)
exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK-INIT-SIZE;
return OK;
}
//入栈
Status Push(SqList &S,SElemType e)
if(S.base-S.top>=S.stacksize){
S.base=(SElemType *)remalloc(S.base,(S.stack+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S. top=S.base+S.stacksize;
S. stack+= STACKINCREMENT;
}
* S. top++= e;
return OK;
}
//出栈
Status Pop(SqStack &S,SElemType &e){
if( S. top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
/**二叉树的建立--按照先序方式建立--插入**/
void CreateBiTree(BiTree &T)
{
char val;
scanf("%c",&val);
if(val == '#')
T = NULL; //null表示为空枝
else
{
T = (BiTree)malloc(sizeof(BiTreeNode));
T->data = val;
CreateBiTree(T->left);
CreateBiTree(T->right);
}
}
/**先序遍历 根左右**/
void PreOrderTravel(BiTree T)
{
if(T==NULL)
return;
printf("%c ",T->data);
PreOrderTravel(T->left);
PreOrderTravel(T->right);
}
/**中序遍历 左根右**/
void InOrderTravel(BiTree T)
{
if(T==NULL)
return;
InOrderTravel(T->left);
printf("%c ",T->data);
InOrderTravel(T->right);
}
/**后序遍历 左右根**/
void TailOrderTravel(BiTree T)
{
if(T==NULL)
return;
TailOrderTravel(T->left);
TailOrderTravel(T->right);
printf("%c ",T->data);
}
/* 计算度为0的结点
void CountNode0(BiTree T)
{
} */
/* 中序遍历非递归*/
//中序遍历二叉树非递归
Status InOrderTraverse(BiTree T,Status (*Vist)(TElemType)){
InitStack(S);
p= T;
while( p|| ! StackEmpty(S)){
if(p){
Push(S, p);
p= p-> lchild;
}
else{
Pop(S,p)
if(! Vist( p->data))
return ERROR;
p= p->rchild;
}
}
return OK
}
/*求二叉树高度*/
int height(BiTree T)
{
//int h1;
// int h2;
if(T==Null)
Return 0;
else{
int LHeight=height(T->left);
int RHeight=height(T->right);
}
if(LHeight>RHeight)
return(LHeight++);
else{
return(RHeight++)
}
}
int main()
{
printf("测试代码\n");
BiTree T;
T = (BiTree)malloc(sizeof(BiTreeNode));
printf("请给二叉树按照先序方式依次输入结点的值(空结点为#):\n");
CreateBiTree(T);
printf("先序方式遍历结果：\n");
PreOrderTravel(T);
printf("\n");
printf("中序方式遍历结果：\n");
InOrderTravel(T);
printf("\n");
printf("后序方式遍历结果：\n");
TailOrderTravel(T);
printf("\n");
// printf("叶子结点结果：\n");
// CountNode0(T);
// printf("共%d个\n",count0);
printf("二叉树的高度：%d\n",height(T));
return 0;
}
