1、1数学与计算机学院计算机系数据结构程序设计报告平衡二叉树学生姓名：万 帅学 好：1004681082班 级：计算机系 102指导老师：陈 文 平报告日期：2011/6/262目录1. 平衡二叉树31.1 平衡二叉树的定义.31.2 平衡二叉树的构造.31.3 平衡二叉树查找的分析.32. 程序功能33. 程序结构类型34. 程序函数45. 算法思想55.1 判断二叉树的旋转方法.55.2 平衡旋转处理.55.3 在平衡二叉树中插入元素.55.4 在平衡二叉树中删除元素.55.5 输出平衡二叉树树形.55.6 销毁平衡二叉树.56.程序设计总结.97.结束语108.附录：程序清单1031. 平衡
2、二叉树1.1 平衡二叉树的定义平衡二叉树(Balanced Binary Tree 或 Height-Balanced Tree)又称 AVL 树。它或者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过 1。若将二叉树上结点的平衡因子 BF(Balanced Factor)定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子之可能是-1、0 和 1。只要二叉树上有一个结点的平衡因子的绝对值大于 1，则该二叉树就是不平衡的。1.2 平衡二叉树的构造构造一颗平衡二叉树的过程就是将一颗空树从根结点起，逐步插
3、入或删除结点并不断对此树进行平衡化。在构造平衡二叉树的过程中有插入和删除两大操作。在树中进行插入和删除操作都可使树失去平衡，然而要让二叉排序树由不平衡转化为平衡，操作就是对二叉树进行旋转，旋转的过程将在算法思想中详细介绍。1.3 平衡二叉树查找的分析在平衡二叉树上进行查找的过程和二叉排序树相同，因此，在查找过程中和给定值进行比较的关键字个数不超过树的深度。因此，在平衡二叉树上进行查找的时间复杂度为O(log n).2. 程序功能本程序的功能就是将二叉排序树转变为平衡二叉树，其操作有:创建二叉树、插入数据、删除数据、输出、销毁二叉树和退出。3. 程序结构类型在本程序中主要用到两个结构类型：结构体和队列。二叉树是链式存储结构，故用结1创 建 二 叉 树2插 入 数 据3删 除 数 据4输 出5销 毁 二 叉 树0退 出请选择:4构体来定义其结构。队列是用作输出二叉树的树形（层序输出） 。4. 程序函数4.1 main()函数：（1）函数原形：void main()（2）功能：显示总菜单，调用子函数4.2 Create()函数 :（1）函数原形：void Create(BSTree int bf;struct BSTNode *lchild,*rchild;BSTNode,*BSTree;
