二叉树建立以及递归、非递归遍历

#include"stdio.h"#include"malloc.h"#include"stdlib.h"typedef struct lNode{char data;struct lNode *lchild;struct lNode *rchild;}LNODE,*Tree;typedef struct Node{Tree data; struct Node * Next;}NODE, * PNODE;typedef struct Stack{PNODE pBottom;PNODE pTop;}STACK, * PSTACK;//函数声明PSTACK initStack(void);//创建栈void push(PSTACK S,Tree val);//压栈void pop(PSTACK S);//出栈bool stackEmpty(PSTACK pS);Tree CreateBiTree();//建树void pretraverse(Tree T);//先序递归遍历void Intraverse(Tree T);//中序递归遍历void posttraverse(Tree T);//后序递归遍历void NoIntraverse(Tree T);//中序非递归遍历int main(){Tree T;T=CreateBiTree();pretraverse(T);printf("\n");Intraverse(T);printf("\n");posttraverse(T);printf("\n");NoIntraverse(T);printf("\n");return 0;}//建树Tree CreateBiTree(){ char ch; Tree T; scanf("%c",&ch); if(ch==’#’)T=NULL; else{ T = (Tree)malloc(sizeof(LNODE)); T->data = ch; T->lchild = CreateBiTree(); T->rchild = CreateBiTree(); } return T;//返回根节点}//先序递归遍历(遍历顺序：根左右)void pretraverse(Tree T){if(T!=NULL){printf("%c",T->data);//输出根节点数据pretraverse(T->lchild);//遍历左子树pretraverse(T->rchild);//遍历右子树}}//中序递归遍历(遍历顺序：左根右)void Intraverse(Tree T){if(T!=NULL){ Intraverse(T->lchild);//遍历左子树printf("%c",T->data);//输出根节点数据Intraverse(T->rchild);//遍历右子树}}//后序递归遍历(遍历顺序：左右根)void posttraverse(Tree T){if(T!=NULL){posttraverse(T->lchild);//遍历左子树 posttraverse(T->rchild);//遍历右子树printf("%c",T->data);//输出根节点数据}}//中序遍历（非递归遍历）void NoIntraverse(Tree T){PSTACK s;s=initStack(); Tree p=T;while(p!=NULL||!stackEmpty(s)){while(p){push(s,p);p=p->lchild;}if(!stackEmpty(s)){pop(s);p=p->rchild;}}}PSTACK initStack(void){ PSTACK pS;pS->pTop=(PNODE)malloc(sizeof(NODE));if(pS->pTop==NULL){printf("动态内存分配失败！");exit(-1);}else{ pS->pBottom=pS->pTop;pS->pBottom->Next=NULL;}return pS;}void push(PSTACK pS,Tree val){PNODE q;q=(PNODE)malloc(sizeof(NODE));if(q==NULL){printf("动态内存分配失败！");exit(-1);}else{q->data=val;q->Next=pS->pTop;pS->pTop=q;}}void pop(PSTACK pS){PNODE q;if(pS->pTop==NULL){printf("动态内存分配失败！");exit(-1);}else{q=pS->pTop;printf("%c",q->data);pS->pTop=q->Next;free(q);}}bool stackEmpty(PSTACK pS){if(pS->pTop==pS->pBottom){return true;}return false;}

，而有的旅行是释放负面情绪，换个心情，轻装上阵。

相关文章：

你感兴趣的文章：

标签云：