二叉树的递归算法：建立二叉树、遍历二叉树.doc

文档介绍：/*二叉树的递归算法:建立二叉树、遍历二叉树*/#include""#include""/****二叉链树的类型定义****/typedefcharTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;/********以下为链式队列相关操作*********/typedefBiTreeElemType;/*定义链式队列类型*/typedefstructQNode{ElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;/*初始化链式队列*/voidInitQueue(LinkQueue*Q){Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));if(!(Q->front))exit(0);Q->front->next=NULL;}/*销毁链式队列*/voidDestroyQueue(LinkQueue*Q){while(Q->front){Q->rear=Q->front->next;free(Q->front);Q->front=Q->rear;}}/*判断空队列*/intQueueEmpty(LinkQueueQ){if(==)return1;elsereturn0;}/*入队列*/voidEnQueue(LinkQueue*Q,ElemTypee){QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(0);p->data=e;p->next=NULL;Q->rear->next=p;Q->rear=p;}/*出队列*/voidDeQueue(LinkQueue*Q,ElemType*e){QueuePtrp;if(Q->front!=Q->rear){p=Q->front->next;*e=p->data;Q->front->next=p->next;if(Q->rear==p)Q->rear=Q->front;free(p);}}/********以上为链式队列相关操作*********//****先序建立二叉树****/voidCreateBiTree(BiTree*T){charch;scanf("%c",&ch);if(ch=='')*T=NULL;else{*T=(BiTree)malloc(sizeof(BiTNode));(*T)->data=ch;CreateBiTree(&(*T)->lchild);CreateBiTree(&(*T)->rchild);}}/****先序遍历二叉树****/voidPreOrderTraverse(BiTreeT){if(T){printf("%c",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}/****中序遍历二叉树****/voidInOrderTraverse(BiTree