数据结构：实现平衡二叉树的各种算法

#include "stdio.h" #include "stdlib.h" #include "malloc.h" #include "math.h" #define MAXSIZE 100 // 存储空间初始分配量 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef int status; typedef int ElemType; //平衡二叉排序树的结构 typedef struct Tnode { ElemType data; struct Tnode *lchild,*rchild; int height; //以该节点为根的子树的深度 } BBTnode,*BBTree; typedef BBTree Position; //栈定义 typedef struct { BBTree *base,*top; //栈指针成员 int initsize; //栈初始长度 } Stack; //队列定义 typedef struct { BBTree *front,*rear; //队列指针成员 int InitSize; //队列初始长度 } Queue; //需要使用的函数 //构建数据结构以及插入结点的函数 status InsertBBT(BBTree &T,ElemType e); //插入新结点 status CreatStack(Stack &S); //建立栈 status CreatQueue(Queue &Q); //建立队列 status FirstViewRoot(BBTree T); //递归前序遍历 status MiddleViewRoot(BBTree T); //递归中序遍历 status LastViewRoot(BBTree T); //递归后序遍历 status ViewAll(BBTree T); //当经常要遍历时可以用来减少代码量 status NonFirstView(BBTree T,Stack S); //非递归前序遍历 status NonMiddleView(BBTree T,Stack S); //非递归中序遍历 status NonLastView(BBTree T,Stack S); //非递归后序遍历 status NonViewAll(BBTree T,Stack S); //当经常要遍历时可以用来减少代码量 status LevelView(BBTree T,Queue Q); //层次遍历 status FindKeyword(BBTree T,ElemType e);//在二叉树中查找给定关键字(函数返回值为成功1,失败0) status SwapSubtree(BBTree T); //交换各结点的左右子树 int DeepOfTree(BBTree T); //求二叉树的深度 int LeafNodeNumber(BBTree T); //叶子结点数 status DeleteBBT(BBTree &T,ElemType e); //删除某结点 //以下函数是为了实现平衡二叉树算法而设计 Position FindMin(BBTree T); //找最小的元素 int Height(BBTree T); //求树的深度(以空树为-1，并定义树的深度为树的层次数减1，如只有一个节点的树的深度为0，两层的树深度为1) int Max(int l,int r); //求较大的数 BBTree LL_SingleRotate(BBTree k2); //向左旋转一次 BBTree RR_SingleRotate(BBTree k1); //向右旋转一次 BBTree LR_DoubleRotate(BBTree k3); //向左转一次，向右转一次 BBTree RL_DoubleRotate(BBTree k1); //向右转一次，向左转一次 int Max(int l,int r) //求较大的数 { if(l>r) return l; else return r; } int Height(BBTree T) //求树的高度 { if(T == NULL) return -1; else return T->height; } status InsertBBT(BBTree &T,ElemType e) //插入新结点 { if(T == NULL) //空树，给树建节点 { T = (BBTree)malloc(sizeof(BBTnode)); if(!T) return ERROR; T->data = e; T->lchild = T->rchild = NULL; T->height = 0; } else if(e < T->data) //向左插入 { InsertBBT(T->lchild,e); if(Height(T->lchild) - Height(T->rchild) == 2) //二叉树不平衡 { if(e < T->lchild->data) // LL 型 T = LL_SingleRotate(T); else // LR 型 T = LR_DoubleRotate(T); } } else if(e > T->data) //向右插入 { InsertBBT(T->rchild,e); if(Height(T->rchild) - Height(T->lchild) == 2) //二叉树不平衡 { if(e > T->rchild->data) // RR 型 T = RR_SingleRotate(T); else //RL 型 T = RL_DoubleRotate(T); } } else return ERROR; // 最后要记录T->height T->height = Max(Height(T->lchild),Height(T->rchild)) + 1; return OK; } Position FindMin(BBTree T) //找最小的元素 { if(T == NULL) return NULL; else if(T->lchild == NULL) return T; else return FindMin(T->lchild); } status DeleteBBT(BBTree &T,ElemType e) //删除某结点 { Position temp; if(T == NULL) return ERROR; //找不到要删除的结点 else if(e < T->data) return DeleteBBT(T->lchild,e); else if(e > T->data) return DeleteBBT(T->rchild,e); else //找到要删除的结点 { if(T->lchild != NULL && T->rchild !=NULL) //有两个孩子 { temp = FindMin(T->rchild); T->data = temp->data; DeleteBBT(T->rchild,T->data); //删除右边找出的最小的节点 } else //有一个或者没有孩子 { temp = T; if(T->lchild == NULL) //也处理了0个孩子的情况 T = T->rchild; else if(T->rchild == NULL) T = T->lchild; free(temp); } return OK; } } BBTree LL_SingleRotate(BBTree k2) //向左旋转一次 { BBTree k1; k1 = k2->lchild; k2->lchild = k1->rchild; k1->rchild = k2; k1->height = Max(Height(k1->lchild),k2->height) + 1; k2->height = Max(Height(k2->lchild),Height(k2->rchild)) +1; return k1; //新的root } BBTree RR_SingleRotate(BBTree k1) //向右旋转一次 { BBTree k2; k2 = k1->rchild; k1->rchild = k2->lchild; k2->lchild = k1; k1->height = Max(Height(k1->lchild),Height(k1->rchild)) +1; k2->height = Max(Height(k1->rchild),k1->height) + 1; return k2; //新的root } BBTree LR_DoubleRotate(BBTree k3) //向左转一次，向右转一次 { k3->lchild = RR_SingleRotate(k3->lchild); //先逆时针转 return LL_SingleRotate(k3); //再顺时针转 } BBTree RL_DoubleRotate(BBTree k1) //向右转一次，向左转一次 { k1->rchild = LL_SingleRotate(k1->rchild); //先顺时针转 return RR_SingleRotate(k1); //再逆时针转 } status CreatStack(Stack &S) //建立栈 { S.base = (BBTree *)malloc(MAXSIZE * sizeof(BBTree)); if(!S.base) return ERROR; S.top = S.base; S.initsize = MAXSIZE; return OK; } status CreatQueue(Queue &Q) //建立队列 { Q.front = (BBTree *)malloc(MAXSIZE * sizeof(BBTree)); if(!Q.front) return ERROR; Q.rear = Q.front; Q.InitSize = MAXSIZE; return OK; } status FirstViewRoot(BBTree T) //递归前序遍历 { if(T != NULL) { printf("%d ",T->data); FirstViewRoot(T->lchild); FirstViewRoot(T->rchild); } return OK; } status MiddleViewRoot(BBTree T) //递归中序遍历 { if(T != NULL) { MiddleViewRoot(T->lchild); printf("%d ",T->data); MiddleViewRoot(T->rchild); } return OK; } status LastViewRoot(BBTree T) //递归后序遍历 { if(T != NULL) { LastViewRoot(T->lchild); LastViewRoot(T->rchild); printf("%d ",T->data); } return OK; } status ViewAll(BBTree T) { printf("the FirstViewRoot is:\n"); FirstViewRoot(T); printf("\n"); printf("the MiddleViewRoot is:\n"); MiddleViewRoot(T); printf("\n"); printf("the LastViewRoot is:\n"); LastViewRoot(T); printf("\n"); return OK; } status NonFirstView(BBTree T,Stack S) //非递归前序遍历 { while(S.base != S.top || T != NULL) { while(T != NULL) //向左走到最左 { printf("%d ",T->data); //输出元素 *S.top++ = T; T = T->lchild; } T=*--S.top; //出栈 T = T->rchild; //转向右 } return OK; } status NonMiddleView(BBTree T,Stack S) //非递归中序遍历 { while(S.base != S.top || T != NULL) { while(T != NULL) //向左走到最左 { *S.top++ = T; T = T->lchild; } T=*--S.top; //出栈 printf("%d ",T->data); //输出元素 T = T->rchild; //转向右 } return OK; } status NonLastView(BBTree T,Stack S) { BBTree pre = NULL; while(S.base !