#include <string.h>

struct treenode{

    int value

    treenode* left

    treenode* right

}

typedef treenode* BiTree

void visit(treenode* node)

{

    printf("%2d ", node->value)

}

//    结点总数 

int node(BiTree T)

{

    if( !T ){

        return 0

    }

    return node(T->left) + node(T->right) + 1

}

//    前序 

void preOrder(BiTree T)

{

    if( T ){

        visit(T)

        preOrder(T->left)

        preOrder(T->right)    

    }

}

//    中序

void inOrder(BiTree T)

{

    if( T ){

        inOrder(T->left)

        visit(T)

        inOrder(T->right)    

    }    

} 

//    后序

void postOrder(BiTree T)

{

    if( T ){

        postOrder(T->left)

        postOrder(T->right)    

        visit(T)

    }    

} 

//    叶子节点数

int leafnode(BiTree T)

{

    if( T ){

        if( !T->left && !T->right )

            return 1

        else

            leafnode(T->left) + leafnode(T->right)    

    }else{

        return 0

    }

} 

int height(BiTree T)

{

    if( T ){

        int lh = height(T->left)

        int rh = height(T->right)

        return (lh>rh ? lh:rh) + 1

    }else{

        return 0

    }

}

int main()

{

    return 0

}

#include "stdlib.h"

#define STACK_INIT_SIZE 10 //栈的初始长度

#define STACKINCREMENT 5 //栈的追加长度

typedef struct bitree{

char data

struct bitree *lchild,*rchild

}bitree //二叉树结点定义

typedef struct {

bitree **base

bitree **top

int stacksize

}sqstack // 链栈结点定义top栈顶 base栈底 且栈元素是指向二叉树结点的二级指针

//建立一个空栈

int initstack(sqstack *s)

{s->base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree))//栈底指向开辟空间

if(!s->base) exit(1) //抛出异常

s->top=s->base //栈顶=栈尾 表示栈空

s->stacksize=STACK_INIT_SIZE //栈长度为开辟空间大小

return 1

}

//进栈

int push(sqstack *s,bitree *e)

{if(s->top-s->base>=s->stacksize) //如果栈满 追加开辟空间

{s->base=(bitree *)realloc (s->base,(s->stacksize+STACKINCREMENT)* sizeof(bitree))

if(!s->base) exit(1)//抛出异常

s->top=s->base+s->stacksize//感觉这一句没用

s->stacksize+=STACKINCREMENT}

*(s->top)=es->top++ //进栈 栈顶后移

return 1

}

//出栈

int pop(sqstack *s,bitree **e)

{if(s->top==s->base) return 0 //栈空 返回0

--s->top*e=*(s->top) //栈顶前移 取出栈顶元素给e

return 1}

//取栈顶

int gettop(sqstack *s,bitree **e)//去栈顶元素 注意top指向的是栈顶的后一个

{if(s->top==s->base) return 0 //所以 s->top-1

*e=*(s->top-1)

return 1

}

/*------------------------非递归-----先序建立二叉树----------------------------------*/

bitree *createprebitree()

{char chbitree *ht,*p,*q

sqstack *s

s=malloc(sizeof(bitree)) //加上这一句为s 初始化开辟空间

ch=getchar()

if(ch!='#'&&ch!='\n') /* 输入二叉树先序顺序 是以完全二叉树的先序顺序

不是完全二叉树的把没有的结点以#表示*/

{ht=(bitree *)malloc(sizeof(bitree))

ht->data=ch

ht->lchild=ht->rchild=NULL

p=ht

initstack(s)

push(s,ht) //根节点进栈

while((ch=getchar())!='\n') // 算

{if(ch!='#') {q=(bitree *)malloc(sizeof(bitree)) // 法

q->data=ch //

if(p==*(s->top-1)) p->lchild=q // 核

else p->rchild=q //

push(s,q)p=q // 心

} //

else {if(p==*(s->top-1)) p->lchild=NULL // 的

else p->rchild=NULL //

pop(s,&p)} // 步

//

} // 骤

return ht

}

else return NULL

}

/*--------------------------递归---------先序建立二叉树-------------------------------*/

void CreateBiTree(bitree **T) {

//按先序次序输入二叉树中的结点的值（一个字符），空格字符表示空树，

//构造二叉链表表示二叉树

char ch

scanf("%c",&ch)

if(ch=='#') *T=NULL

else{

*T=(bitree * )malloc(sizeof(bitree))

if(!*T) exit(1)

(*T)->data=ch //生成根结点

CreateBiTree(&(*T)->lchild)//构造左子树

CreateBiTree(&(*T)->rchild)//构造右子树

}

}

/*--------------------------非递归-------中序建立二叉树-------------------------------*/

/*--------------------------递归---------中序建立二叉树-------------------------------*/

/*--------------------------非递归-------后序建立二叉树-------------------------------*/

/*--------------------------递归---------后序建立二叉树-------------------------------*/

/*-----------------------非递归------先序输出二叉树------------------------------*/

void preordertraverse(bitree *h)

{sqstack m

initstack(&m)

while(h||m.base!=m.top)

{if(h) {push(&m,h)printf("%c",h->data)h=h->lchild}

else{pop(&m,&h)

h=h->rchild}

}

}

/*------------------------非递归-----中序输出二叉树----------------------------*/

void inordertraverse(bitree *h)

{sqstack m

initstack(&m)

while(h||m.base!=m.top)

{if(h) {push(&m,h)h=h->lchild}

else {

pop(&m,&h)

printf("%c",h->data)

h=h->rchild

}

}

}

/*---------------------非递归----后序遍历二叉树----------------------------------*/

void postordertraverse(bitree *h)

{

sqstack m

initstack(&m)

while(h||m.base!=m.top)

{if(h) {

push(&m,h)

h=h->lchild}

else {

bitree *r//使用r结点表示访问了右子树 代替标志域

gettop(&m,&h)

if(h->rchild&&h->rchild!=r)

{h=h->rchild

push(&m,h)

h=h->lchild}

else{pop(&m,&h)

printf("%c",h->data)

r=hh=NULL}

}

}

}

//层次遍历二叉树 用队列 哈哈以后做

/*-------------------------------主过程-------------------------------*/

int main()

{bitree *ht

printf("先序非递归建立一个二叉树:")

if((ht=createprebitree())!=NULL) //非递归建立

//CreateBiTree(&ht)

//if(ht!=NULL)//递归建立

{

printf("先序遍历输出二叉树:")

preordertraverse(ht)

putchar('\n')

printf("中序遍历输出二叉树:")

inordertraverse(ht)

putchar('\n')

printf("后序遍历输出二叉树:")

postordertraverse(ht)

putchar('\n')

}

else printf("空二叉树\n")

}