二叉树的各种算法

1、二叉树的各种算法、 txt 男人的承诺就像 80 岁老太太的牙齿 , 很少有真的。您嗜烟成性的时 候, 只有三种人会高兴 , 医生 您的仇人与卖香烟的。/* 用函数实现如下二叉排序树算法 :(1) 插入新结点(2) 前序、中序、后序遍历二叉树(3) 中序遍历的非递归算法(4) 层次遍历二叉树(5) 在二叉树中查找给定关键字 ( 函数返回值为成功 1, 失败 0)(6) 交换各结点的左右子树(7) 求二叉树的深度(8) 叶子结点数Input第一行 : 准备建树的结点个数 n第二行：输入n个整数，用空格分隔第三行 : 输入待查找的关键字第四行 ： 输入待查找的关键字第五行 ： 输入待插入的关键字O

2、utput第一行 ： 二叉树的先序遍历序列第二行 ： 二叉树的中序遍历序列第三行 ： 二叉树的后序遍历序列第四行 ： 查找结果第五行 ： 查找结果第六行 第八行 ： 插入新结点后的二叉树的先、中、序遍历序列第九行 ： 插入新结点后的二叉树的中序遍历序列 ( 非递归算法 )第十行 ： 插入新结点后的二叉树的层次遍历序列第十一行 第十三行 ： 第一次交换各结点的左右子树后的先、中、后序遍历序列第十四行 第十六行 ： 第二次交换各结点的左右子树后的先、中、后序遍历序列第十七行 ： 二叉树的深度第十八行 ： 叶子结点数*/#include stdio 、 h#include malloc 、 h#de

3、fine TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int KeyType;#define STACK_INIT_SIZE 100 / 存储空间初始分配量#define STACKINCREMENT 10 / 存储空间分配增量#define MAXQSIZE 100typedef int ElemType;typedef struct BiTNodeElemType data;struct BiTNode *

4、lchild,*rchild;/ 左右孩子指针 BiTNode,*BiTree;Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p)if(!T)p=f;return FALSE;else if(key=T-data)p=T;return TRUE;else if(keydata)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(!

5、SearchBST(T,e,NULL,p) s=(BiTree)malloc(sizeof(BiTNode); s-data=e;s-lchild=s-rchild=NULL; if(!p)T=s;else if(edata)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(*

6、Visit)(ElemType) ) Visit 。/前序遍历二叉树T的递归算法，对每个数据元素调用函数/ 补全代码 , 可用多个语句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 的递归算法 , 对

7、每个数据元素调用函数/ 补全代码 , 可用多个语句if(T)if(InOrderTraverse(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(PostOrderTr

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

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

10、 OK;Status Push(SqStack &S,BiTree e)if(S 、 top-S 、 base)=S 、 stacksize)base,(SS 、 base=(BiTree*)realloc(S 、 stacksize+STACKINCREMENT)*sizeof(BiTree);if(!S、 base)return ERROR;S、 top=S 、 base+S、 stacksize;S、 stacksize+=STACKINCREMENT;*S 、 top+=e;return OK;Status Pop(SqStack &S,BiTree &e)if(S、 top=S 、

11、base)return ERROR;e=*-S 、 top;return OK;Status StackEmpty(SqStack S) / 若栈S为空栈,则返回TRUE否则返回FALSEif(S 、 top-S 、 base=0)return TRUE;else return FALSE;Status InOrderTraverse1(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,

12、p);if(!Visit(p-data)return ERROR;p=p-rchild;return OK;/ 层次遍历typedef structBiTree *base; / 初始化的动态分配存储空间int front; / 头指针 , 若队列不空 , 指向队列头元素int rear; / 尾指针 , 若队列不空 , 指向队列尾元素的下一个位置SqQueue;Status InitQueue(SqQueue &Q)Q 、base=(BiTree*)malloc(MAXQSIZE*sizeof(BiTree);if(!Q 、 base)return ERROR;Q 、front=Q 、 re

13、ar=0;return OK;int QueueLength(SqQueue Q)/ 返回 Q 的元素个数/ 请补全代码return(Q、 rear-Q 、 front+MAXQSIZE)%MAXQSIZE;Status EnQueue(SqQueue &Q,BiTree e)/插入元素e为Q的新的队尾元素/ 请补全代码if(Q、rear+1)%MAXQSIZE=Q、front)return ERROR;Q 、baseQ 、rear=e;Q 、rear=(Q 、 rear+1)%MAXQSIZE;return OK;Status DeQueue(SqQueue &Q,BiTree &e)/若队

14、列不空,则删除Q的队头元素,用e返回其值,并返回0K;否则返回ERROR/ 请补全代码if(Q 、 front=Q 、 rear)return ERROR;e=Q 、 baseQ、front;Q 、front=(Q 、 front+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(

15、Q,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);/ return OK;int BTreeDepth(BiTree T)/求由 BT 指针指向的一棵二叉树的深度/int dep1,dep

16、2;if(T!=NULL)/ 计算左子树的深度int dep1=BTreeDepth(T-lchild);/ 计算右子树的深度int dep2=BTreeDepth(T-rchild);/ 返回树的深度 if(dep1dep2) return dep1+1; elsereturn dep2+1;else return 0;/ 叶子结点数Status yezhi(BiTree T,SqQueue Q)int i=0;InitQueue(Q);BiTree p;p=T;if(T)EnQueue(Q,T);/ printf(%d,QueueLength(Q); while(QueueLength(Q

17、)!=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;int i,n,e,a,b,c;scanf(%d,&n);for(i=0;in;i+)scanf(%d,&e);InsertBST(T,e); scanf(%d,&a);scanf(%d,&b);scanf(%d,&c);Putout(T); printf(%dn,Se