二叉树的各种算法.pdf

二叉树的各种算法 .txt 男人的承诺就像 80 岁老太太的牙齿，很少有真的。你嗜烟成性的时 候，只有三种人会高兴，医生 你的仇人和卖香烟的。 /* 用函数实现如下二叉排序树算法： （1） 插入新结点 （2 ） 前序、中序、后序遍历二叉树 （3 ） 中序遍历的非递归算法 （4 ） 层次遍历二叉树 （5 ） 在二叉树中查找给定关键字 ( 函数返回值为成功 1, 失败 0) （6 ） 交换各结点的左右子树 （7 ） 求二叉树的深度 （8 ） 叶子结点数 Input 第一行：准备建树的结点个数 n 第二行：输入 n 个整数，用空格分隔 第三行：输入待查找的关键字 第四行：输入待查找的关键字 第五行：输入待插入的关键字 Output 第一行：二叉树的先序遍历序列 第二行：二叉树的中序遍历序列 第三行：二叉树的后序遍历序列 第四行：查找结果 第五行：查找结果 第六行 ~第八行：插入新结点后的二叉树的先、中、序遍历序列 第九行：插入新结点后的二叉树的中序遍历序列 ( 非递归算法 ) 第十行：插入新结点后的二叉树的层次遍历序列 第十一行 ~第十三行：第一次交换各结点的左右子树后的先、中、后序遍历序列 第十四行 ~第十六行：第二次交换各结点的左右子树后的先、中、后序遍历序列 第十七行：二叉树的深度 第十八行：叶子结点数 */ #include stdio.h #include malloc.h #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int KeyType; #define STACK_INIT_SIZE 100 // 存储空间初始分配量 #define STACKINCREMENT 10 // 存储空间分配增量 #define MAXQSIZE 100 typedef int ElemType; typedef struct BiTNode{ ElemType 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;return TRUE;} else if(keyT-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-rchild=NULL; if(!p)T=s; else if(ep-data)p-lchild=s; else p-rchild=s; return TRUE; } else return FALSE; } Status PrintElement( ElemType e ) { // 输出元素 e 的值 printf(%d , e ); return OK; }// PrintElement Status PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) { // 前序遍历二叉树