叉树的各种算法

《叉树的各种算法》由会员分享，可在线阅读，更多相关《叉树的各种算法（9页珍藏版）》请在装配图网上搜索。

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 -2typedef int Status;typedef int KeyType;#define S

3、TACK_INIT_SIZE 100 /#define STACKINCREMENT 10 /#define MAXQSIZE 100存储空间初始分配量存储空间分配增量typedef 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;return FALSE;else if(key=T-data)p=T;r

4、eturn 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(!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 T

5、RUE;else return FALSE;Status PrintElement( ElemType e ) /输出元素e 的值printf(%d , e );return OK;/ PrintElementStatus PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) /前序遍历二叉树T 的递归算法，对每个数据元素调用函数Visit。/ 补全代码 , 可用多个语句if(T)if(Visit(T-data)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverse(T-rchild,

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

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

8、)PreOrderTraverse(T,PrintElement);printf(n);InOrderTraverse(T, PrintElement);printf(n);PostOrderTraverse(T,PrintElement);printf(n);return OK;/ 非递归算法struct SqStackBiTree *base; /BiTree *top; /int stacksize; /; /顺序栈在栈构造之前和销毁之后，base 的值为栈顶指针当前已分配的存储空间，以元素为单位NULLStatus InitStack(SqStack &S)=(BiTree *)mal

9、loc(STACK_INIT_SIZE*sizeof(BiTree);if(!return ERROR;=;=STACK_INIT_SIZE;return OK;Status Push(SqStack &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(Sq

10、Stack S) /若栈 S 为空栈，则返回 TRUE，否则返回 FALSE if 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,p);if(!Visit(p-data)return ERROR;p=p-rchild;return OK;/ 层次遍历typedef structBiTree

11、*base; / int front; / int rear; /初始化的动态分配存储空间头指针 , 若队列不空 , 指向队列头元素尾指针 , 若队列不空 , 指向队列尾元素的下一个位置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的新的

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

13、eueLength(Q);while(QueueLength(Q)!=0)DeQueue(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 BTree

14、Depth(BiTree T)/ 求由 BT 指针指向的一棵二叉树的深度/ int dep1,dep2; 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,

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

16、,&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);InOrderTraverse1(T, PrintElement,S);printf(n);LevelTraverse(T,Q);printf(n);Change(T);Putout(T);Change(T);Putout(T);printf(%d,BTreeDepth(T);printf(n);printf(%d,yezhi(T,Q3);printf(n);return OK;/main