二叉树的建立及几种简单的遍历方法

《二叉树的建立及几种简单的遍历方法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、#include"stdio.h"#include"stdlib.h"#defineSTACK_INIT_SIZE100//栈存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量//------二叉树的存储结构表示------//typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//-----顺序栈的存储结构表示------//typedefstruct{BiTree*top;BiTr

2、ee*base;intstacksize;}SqStack;//***************************************************//构造一个空栈sSqStack*InitStack();//创建一颗二叉树BiTreeCreatBiTree();//判断栈空intStackEmpty(SqStack*S);//插入元素e为新的栈顶元素voidPush(SqStack*S,BiTreep);//若栈不为空，则删除s栈顶的元素e，将e插入到链表L中voidPop(SqStack*S,

3、BiTree*q);//非递归先序遍历二叉树voidPreOrderTraverse(BiTreeL);//非递归中序遍历二叉树voidInOrderTraverse(BiTreeL);//非递归后序遍历二叉树voidPostOrderTraverse(BiTreeL);//递归后序遍历二叉树voidPostOrder(BiTreebt);//递归中序遍历二叉树voidInOrder(BiTreebt);//递归先序遍历二叉树voidPreOrder(BiTreebt);//********************

4、*******************************intmain(){BiTreebt;intn,k;printf("CreatTreeandtheendwith'.'");bt=CreatBiTree();//创建二叉树do{printf("1.PreOrderTraverse2.InOrderTraverse3.PostOrderTraverse4.PostOrder5.InOrder6.PreOrde");printf("pleaseinputanumton:");scanf("%d",&

5、n);switch(n){case1:PreOrderTraverse(bt);printf("");break;//先序遍历非递归算法case2:InOrderTraverse(bt);printf("");break;//中序非递归遍历算法case3:PostOrderTraverse(bt);printf("");break;//后序非递归遍历算法case4:PostOrder(bt);printf("");break;//后序递归遍历算法case5:InOrder(bt);printf("

6、n");break;//中序递归遍历算法case6:PreOrder(bt);printf("");break;//先序递归遍历算法}printf("ifyouwanttocontinue,pleaseinputanum>0tok:");scanf("%d",&k);}while(k>0);return0;}SqStack*InitStack(){//构造一个空栈SSqStack*S;S=(SqStack*)malloc(sizeof(SqStack));S->base=(BiTree*)malloc(STAC

7、K_INIT_SIZE*sizeof(BiTree));S->top=S->base;S->stacksize=STACK_INIT_SIZE;returnS;}BiTreeCreatBiTree(){//先序方式递归方式建立一个二叉树chark;BiTreeT;k=getchar();if(k=='.')T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));T->data=k;T->lchild=CreatBiTree();T->rchild=CreatBiTree();

8、}returnT;}voidPush(SqStack*S,BiTreep){//插入二叉树p的结点地址为栈顶的新元素if(S->top-S->base>=S->stacksize){S->base=(BiTree*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(BiTree));S->top=S->