二叉树.非递归算法.先序遍历.中序遍历.后序遍历

1、/ 二叉树.cpp : Defines the entry point for the console application./#include stdafx.htypedef struct bitnodechar data;struct bitnode *lchild,*rchild;bitnode;typedef bitnode *elemtype;/elemtype声明为指针类型typedef struct stack/栈的存储类型,采用动态分配elemtype *base;elemtype *top;int stacksize;sqstack;#define STACK_INIT_S

2、IZE 100/栈初始分配的空间数#define STACKINCREAMENT 10/栈空间不够时增加的空间数sqstack *initstack(/创建栈sqstack *s;if (!(s = (sqstack *malloc(sizeof(sqstackexit(-1;s-base = (elemtype *malloc(STACK_INIT_SIZE*sizeof(elemtype;if (!s-baseexit(0;/分配失败if (s-base/分配成功s-top = s-base;s-stacksize = STACK_INIT_SIZE;return s;void push(

3、sqstack *s,elemtype e/压栈,if (s-top-s-base=s-stacksizes-base = (elemtype *realloc(s-base,(s-stacksize+STACKINCREAMENT*sizeof(elemtype;if (!s-baseexit(0;s-stacksize += STACKINCREAMENT;*(s-top = e;s-top+;elemtype pop(sqstack *s/出栈elemtype e;if (s-top = s-basereturn 0;s-top-;e = *(s-top;return e;int sta

4、ckempty(sqstack *s/判断栈是否为空if (s-base = s-topreturn 1;else return 0;int count;bitnode *create(/创建二叉链表char ch;bitnode *t;scanf(%c,&ch;if(ch= t=NULL;elset=(bitnode *malloc(sizeof(bitnode;t-data=ch;t-lchild=create(;t-rchild=create(;return t;void xianxubianli(bitnode *t/先序遍历if(tprintf(%c,t-data;xianxubia

5、nli(t-lchild;xianxubianli(t-rchild;void zhongxubianli(bitnode *t/中序遍历if(tzhongxubianli(t-lchild;printf(%c,t-data;zhongxubianli(t-rchild;void houxubianli(bitnode *t/后续遍历if(thouxubianli(t-lchild;houxubianli(t-rchild;printf(%c,t-data;int leafcount(bitnode *t/该二叉树的叶子数if (!t return 0;if (!t-lchild & !t-r

6、childcount+;leafcount(t-lchild;leafcount(t-rchild;return 0;void feidigui(bitnode *t/中序遍历二叉树非递归算法sqstack *s;bitnode *p;s = initstack(;p = t;while (p|!stackempty(swhile (ppush(s,p;p = p-lchild;p = pop(s;printf(%c,p-data;p = p-rchild;int main(int argc, char* argv/主函数bitnode *root;printf(请输入树的序列:;root=create(;printf(n;printf(该树的先序序列是:;xianxubianli(root;printf(n;printf(该树的中序序列是:;zhongxubianli(root;printf(n;printf(该树的后序序列是:;houxubianli(root;printf(n;printf(该