二叉樹.非遞歸算法.先序遍歷.中序遍歷.后序遍歷

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/棧的存儲(chǔ)類型,采用動(dòng)態(tài)分配elemtype *base;elemtype *top;int stacksize;sqstack;#define STACK_INIT_S

2、IZE 100/棧初始分配的空間數(shù)#define STACKINCREAMENT 10/?？臻g不夠時(shí)增加的空間數(shù)sqstack *initstack(/創(chuàng)建棧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(/創(chuàng)建二叉鏈表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/后續(xù)遍歷if(thouxubianli(t-lchild;houxubianli(t-rchild;printf(%c,t-data;int leafcount(bitnode *t/該二叉樹的葉子數(shù)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/主函數(shù)bitnode *root;printf(請(qǐng)輸入樹的序列:;root=create(;printf(n;printf(該樹的先序序列是:;xianxubianli(root;printf(n;printf(該樹的中序序列是:;zhongxubianli(root;printf(n;printf(該樹的后序序列是:;houxubianli(root;printf(n;printf(該