数据结构大作业(平衡二叉树)VIP专享VIP免费

1 数学与计算机学院计算机系数据结构程序设计报告 平衡二叉树 学生姓名：* * 学 好：1 0 0 4 6 8 1 0 2 8 班 级：计算机系 1 0 2 指导老师：* * * 报告日期：2 0 1 1 /6 /2 6 2 目录 1 . 平衡二叉树…………………………………………………3 1 .1 平衡二叉树的定义…………………………………...3 1 .2 平衡二叉树的构造…………………………………...3 1 .3 平衡二叉树查找的分析……………………………...3 2 . 程序功能……………………………………………………3 3 . 程序结构类型………………………………………………3 4 . 程序函数……………………………………………………4 5 . 算法思想……………………………………………………5 5 .1 判断二叉树的旋转方法……………………………...5 5 .2 平衡旋转处理………………………………………...5 5 .3 在平衡二叉树中插入元素…………………………...5 5 .4 在平衡二叉树中删除元素………………………...…5 5 .5 输出平衡二叉树树形………………………………...5 5 .6 销毁平衡二叉树……………………………………...5 6 .程序设计总结……………………………………………….9 7 .结束语………………………………………………………1 0 8 .附录：程序清单……………………………………………1 0 3 1. 平衡二叉树 1.1 平衡二叉树的定义 平衡二叉树(Balanced Binary Tree或 Height-Balanced Tree)又称 AVL 树。它或者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过 1。若将二叉树上结点的平衡因子 BF(Balanced Factor)定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子之可能是-1、0 和 1。只要二叉树上有一个结点的平衡因子的绝对值大于 1，则该二叉树就是不平衡的。 1.2 平衡二叉树的构造 构造一颗平衡二叉树的过程就是将一颗空树从根结点起，逐步插入或删除结点并不断对此树进行平衡化。在构造平衡二叉树的过程中有插入和删除两大操作。在树中进行插入和删除操作都可使树失去平衡，然而要让二叉排序树由不平衡转化为平衡，操作就是对二叉树进行旋转，旋转的过程将在算法思想中详细介绍。 1.3 平衡二叉树查找的分析 在平衡二叉树上进行查找的过程和二叉排序树相同，...