1、 算算 法法 与与 数数 据据 结结 构构 课课 程程 设设 计计 报报 告告 题题 目目: AVLree 的实现及分析的实现及分析 班班 级级: 学学 号号: 姓姓 名名: 成成 绩绩: 2013 年年 12 月月 31 日日 一、一、AVLreeAVLree 的实现及分析的实现及分析 AVL 树是平衡的二元查找树。 一株平衡的二元查找树就是指对其每一个节点， 其左子树和右 子树的高度只差不超过 1. 编写程序实现 AVL 树的判别；并实现 AVL 树的 ADT，包括其上的基本操作；节点的加入和删 除。BSt 和 AVL 的差别就在平衡性上，所以 AVL 的操作关键要考虑如何在保持二元查找树
2、定 义条件下对二元树进行平衡化。 （1） 编写 AVL 树的判别程序，并判别一个人元查找数是否为 AVL 树。二元查找树用其先序 遍历结果表示，如：5,2,1,3,7,8. （2） 实现 AVL 树的 ADT，包括其上的基本操作：节点的加入和删除，另外包括将一般二元 查找树转变为 AVL 树的操作。 二、设计思想（宋体，三号加粗）二、设计思想（宋体，三号加粗） 任意给定一组数据，设计一个算法，建立一棵平衡二叉树，对它进行查找、插入、删除等操 作。平衡二叉树 ADT 结构如下： typedef struct Status key; ElemType; typedef struct BSTNode
3、 ElemType data; Status bf; struct BSTNode *lchild,*rchild; BSTNode,*BSTree; 给出一组数据，通过 InsertAVL(BSTree typedef char TElemType; typedef struct Status key; ElemType; typedef struct BSTNode ElemType data; Status bf; struct BSTNode *lchild,*rchild; BSTNode,*BSTree; Status SearchBST(BSTree T, Status key,
4、 BSTree f, BSTree return FALSE; / 查找不成功 else if (key=T-data.key) p = T; return TRUE; / 查找成功 else if (keydata.key) return SearchBST(T-lchild, key, T, p); / 在左 子树中继续查找 else return SearchBST(T-rchild, key, T, p); / 在右 子树中继续查找 / SearchBST Status InsertBST(BSTree if (!SearchBST(T, e.key, NULL, p) / 查找不成
5、功 s = (BSTree)malloc(sizeof(BSTNode); s-data = e; s-lchild = s-rchild = NULL; if (!p) T = s; / 插入 s 为新的根结点 else if (e.keydata.key) p-lchild=s; / 插入 s 为左孩子 else p-rchild = s; / 插入 s 为右孩子 return TRUE; else return FALSE; / 树中已有关键字相同的结点， 不再插入 / Insert BST Status CreateBST(BSTree ElemType e; coutnum; whi
6、le(num!=0) coute.key; InsertBST(T,e);/按二叉排序树插入方法； num-; return 0; Status max(Status lchild,Status rchild)/取较大的值返 回 if(lchildrchild) return lchild; else return rchild; Status Depth_bt(BSTree T)/求二叉树深度 if (T=NULL) return 0; return 1+max(Depth_bt(T-lchild),Depth_bt(T-rchild); Status Balance(BSTree T)/递归判断是不是平衡二叉树 Status bl,br; if (T=NULL) return 1;/空树输出是平衡二叉树 bl=Depth_bt(T-lchild);/将左子树的深度赋值给 bl br=Dept
