資源描述：
《二叉樹的建立、遍歷、各種算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、基于二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)以下操作:1、用先序遍歷創(chuàng)建二叉樹2、對(duì)二叉樹進(jìn)行非遞歸遍歷（先序、中序、后序）3、求二叉樹所有結(jié)點(diǎn)和葉子結(jié)點(diǎn)個(gè)數(shù)4、求二叉樹的深度5、#include"stdio.h"#include"malloc.h"#include"math.h"#include"stdlib.h"#defineOK1#defineERROR0#defineTRUE1#defineFALSE0//#defineOVERFLOW#defineNULL0typedefintStatus;type
2、defcharTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;typedefBiTreeSElemType;//tepedefBiNodeSElemType;//#defineMAX_TREE_SIZE100//typedefTElemtypeSqBiTree[MAX_TREE_SIZE];//SqBiTreebt;typedefstruct{SElemType*b
3、ase;SElemType*top;intstacksize;}SqStack;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK
4、;}StatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(O
5、VERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}StatusPop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}StatusStackEmpty(SqStackS){if(S.top==S.base)returnTRUE;elsereturnFALSE;}StatusCreate
6、BiTree(BiTree&T){//按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），空格字符表示空樹，//構(gòu)造二叉鏈表表示的二叉樹T。charch;scanf("%c",&ch);if(ch=='@')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}returnOK;}//CreateBiTr
7、eeStatusPreoderTraverse(BiTreeT){//二叉樹先序遍歷非遞歸算法SqStackS;BiTreep;InitStack(S);p=T;while(p
8、
9、!StackEmpty(S)){if(p){printf("%ct",p->data);p=p->lchild;Push(S,p->rchild);}elsePop(S,p);}returnOK;}//PostoderTraverseStatusInoderTraverse(BiTreeT){//二叉樹中序遍歷非遞歸算
10、法SqStackS;BiTreep;InitStack(S);p=T;while(p
11、
12、!StackEmpty(S)){if(p){Push(S,p);p=p->lchild;}else{Pop(S,p);printf("%ct",p->data);p=p->rchild;}}returnOK;}//InoderTraverse//Algorithm:先沿著左指針走到二叉樹中最左下的結(jié)點(diǎn)，將沿途經(jīng)過的根節(jié)點(diǎn)指針進(jìn)//棧，若右子樹為空，則彈棧并訪問根節(jié)點(diǎn)，否則，跳到右子樹上。///
