叉树的各种算法

1、1 ) 插入新结点2 ) 前序、中序、后序遍历二叉树3) 中序遍历的非递归算法4) 层次遍历二叉树5) 在二叉树中查找给定关键字 ( 函数返回值为成功 1, 失败 0)6) 交换各结点的左右子树7) 求二叉树的深度8) 叶子结点数Input第一行：准备建树的结点个数 n 第二行：输入 n 个整数，用空格分隔 第三行：输入待查找的关键字 第四行：输入待查找的关键字 第五行：输入待插入的关键字Output第一行：二叉树的先序遍历序列第二行：二叉树的中序遍历序列第三行：二叉树的后序遍历序列第四行：查找结果第五行：查找结果第六行 第八行：插入新结点后的二叉树的先、中、序遍历序列 第九行：插入新结点后的

2、二叉树的中序遍历序列 ( 非递归算法 ) 第十行：插入新结点后的二叉树的层次遍历序列第十一行 第十三行：第一次交换各结点的左右子树后的先、中、后序遍历序列 第十四行 第十六行：第二次交换各结点的左右子树后的先、中、后序遍历序列 第十七行：二叉树的深度 第十八行：叶子结点数*/ #include ""#include ""#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status;ty

3、pedef int KeyType;#define STACK_INIT_SIZE 100 /存储空间初始分配量#define STACKINCREMENT 10 / 存储空间分配增量#define MAXQSIZE 100typedef int ElemType;typedef struct BiTNodeElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p)if(!T)p=f;retur

4、n FALSE;else if(key=T->data)p=T;return TRUE;else if(key<T->data)return SearchBST(T->lchild,key,T,p);else return(SearchBST(T->rchild,key,T,p);Status InsertBST(BiTree &T,ElemType e)BiTree s,p;if(!SearchBST(T,e,NULL,p) s=(BiTree)malloc(sizeof(BiTNode); s->data=e;s->lchild=s->

5、;rchild=NULL; if(!p)T=s;else if(e<p->data)p->lchild=s;else p->rchild=s; return TRUE;else return FALSE;Status PrintElement( ElemType e ) /输出元素 e 的值printf("%d ", e );return OK;/ PrintElementStatus PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) / 前序遍历二叉树 T 的递归算法，对每个数据元素调用函

6、数 Visit/ 补全代码 , 可用多个语句if(T)if(Visit(T->data)if(PreOrderTraverse(T->lchild,Visit) if(PreOrderTraverse(T->rchild,Visit)return OK; return ERROR;else return OK; / PreOrderTraverseStatus InOrderTraverse( BiTree T, Status(*Visit)(ElemType) )/ 中序遍历二叉树 T 的递归算法，对每个数据元素调用函数/ 补全代码 , 可用多个语句if(T)if(InOr

7、derTraverse(T->lchild,Visit)if(Visit(T->data) if(InOrderTraverse(T->rchild,Visit) return OK;return ERROR;else return OK; / InOrderTraverseStatus PostOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) / 后序遍历二叉树 T 的递归算法，对每个数据元素调用函数/ 补全代码 , 可用多个语句if(T)if(PostOrderTraverse(T->lchild,Visit)

8、if(PostOrderTraverse(T->rchild,Visit) if(Visit(T->data)return OK; return ERROR;else return OK; / PostOrderTraverseStatus Putout(BiTree T)Visit 。Visit 。PreOrderTraverse(T,PrintElement);printf("n");InOrderTraverse(T, PrintElement);printf("n");PostOrderTraverse(T,PrintElement)

9、;printf("n");return OK;/ 非递归算法struct SqStackBiTree *base; / 在栈构造之前和销毁之后， base 的值为 NULLBiTree *top; / 栈顶指针int stacksize; / 当前已分配的存储空间，以元素为单位; / 顺序栈Status InitStack(SqStack &S)=(BiTree *)malloc(STACK_INIT_SIZE*sizeof(BiTree); if(!return ERROR;一 J=STACK_INIT_SIZE;return OK;Status Push(SqS

10、tack &S,BiTree e)if( =(BiTree*)realloc,+STACKINCREMENT)*sizeof(BiTree);if(!return ERROR;=+;+=STACKINCREMENT;*+=e;return OK;Status Pop(SqStack &S,BiTree &e)if=return ERROR;e=*;return OK;Status StackEmpty(SqStack S) / 若栈S为空栈，则返回 TRUE否则返回FALSE if TRUE;else return FALSE;Status InOrderTravers

11、e1(BiTree T,Status(*Visit)(ElemType e),SqStack S) BiTree p;InitStack(S);p=T; while(p|!StackEmpty(S)if(p)Push(S,p);p=p->lchild;elsePop(S,p); if(!Visit(p->data)return ERROR; p=p->rchild;return OK;/ 层次遍历BiTree *base; / int front; /typedef struct初始化的动态分配存储空间头指针 , 若队列不空 , 指向队列头元素int rear; /尾指针 ,

12、 若队列不空 , 指向队列尾元素的下一个位置SqQueue;Status InitQueue(SqQueue &Q)=(BiTree*)malloc(MAXQSIZE*sizeof(BiTree);if(!return ERROR;=0;return OK;int QueueLength(SqQueue Q)/ 返回 Q 的元素个数/ 请补全代码returnStatus EnQueue(SqQueue &Q,BiTree e)/插入元素e为Q的新的队尾元素/ 请补全代码if(+1)%MAXQSIZE=return ERROR;=e;=+1)%MAXQSIZE;return OK

13、;Status DeQueue(SqQueue &Q,BiTree &e)/若队列不空,则删除Q的队头元素,用e返回其值,并返回0K;否则返回ERROR / 请补全代码if=return ERROR;e=;=+1)%MAXQSIZE;return OK;Status LevelTraverse(BiTree T,SqQueue Q)/层次遍历二叉树InitQueue(Q);BiTree p;p=T;if(T)EnQueue(Q,T);/ printf("%d",QueueLength(Q);while(QueueLength(Q)!=0)DeQueue(Q,

14、p); / 根结点出队printf("%d ",p->data); / 输出数据if(p->lchild)EnQueue(Q,p->lchild); /左孩子进队if(p->rchild)EnQueue(Q,p->rchild); /右孩子进队return OK;void Change(BiTree T) BiTNode *p; if(T) p=T->lchild;T->lchild=T->rchild; T->rchild=p; Change(T->lchild);Change(T->rchild); /

15、return OK;int BTreeDepth(BiTree T)/求由 BT 指针指向的一棵二叉树的深度/int dep1,dep2;if(T!=NULL)/ 计算左子树的深度int dep1=BTreeDepth(T->lchild);/ 计算右子树的深度int dep2=BTreeDepth(T->rchild);/ 返回树的深度 if(dep1>dep2) return dep1+1; else return dep2+1;else return 0;/ 叶子结点数Status yezhi(BiTree T,SqQueue Q)int i=0;InitQueue(Q

16、);BiTree p;p=T;if(T)EnQueue(Q,T);/ printf("%d",QueueLength(Q); while(QueueLength(Q)!=0)DeQueue(Q,p);if(p->lchild)EnQueue(Q,p->lchild); if(p->rchild)EnQueue(Q,p->rchild); if(!p->lchild&&!p->rchild)i+;return i;int main() / 主函数SqStack S;SqQueue Q,Q3;BiTree T=NULL,f,p

17、;int i,n,e,a,b,c;scanf("%d",&n); for(i=0;i<n;i+) scanf("%d",&e);InsertBST(T,e);scanf("%d",&a);scanf("%d",&b);scanf("%d",&c);Putout(T); printf("%dn",SearchBST(T,a,f,p);printf("%dn",SearchBST(T,b,f,p);InsertBST(T,c);Putout(T);In