大数据结构 平衡二叉树的操作演示

一、平衡二叉树的概念平衡二叉树(Balanced binary tree)是由阿德尔森-维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。

定义：平衡二叉树或为空树,或为如下性质的二叉排序树:（1）左右子树深度之差的绝对值不超过1;（2）左右子树仍然为平衡二叉树.平衡因子BF=左子树深度－右子树深度.平衡二叉树每个结点的平衡因子只能是1，0，-1。

若其绝对值超过1，则该二叉排序树就是不平衡的。

如图所示为平衡树和非平衡树示意图：二、平衡二叉树算法思想若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。

首先要找出插入新结点后失去平衡的最小子树根结点的指针。

然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。

当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。

失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树。

假设用A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况。

1）LL型平衡旋转法由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。

故需进行一次顺时针旋转操作。

即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右子树的根结点。

而原来B的右子树则变成A的左子树。

（2）RR型平衡旋转法由于在A的右孩子C 的右子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。

故需进行一次逆时针旋转操作。

即将A的右孩子C向左上旋转代替A作为根结点，A向左下旋转成为C的左子树的根结点。

而原来C的左子树则变成A的右子树。

（3）LR型平衡旋转法由于在A的左孩子B的右子数上插入结点F，使A的平衡因子由1增至2而失去平衡。

故需进行两次旋转操作（先逆时针，后顺时针）。

即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。

数据结构与算法—二叉排序树详解前言前面介绍学习的大多是线性表相关的内容，把指针搞懂后其实也没有什么难度。

规则相对是简单的。

再数据结构中树、图才是数据结构标志性产物，(线性表大多都现成api可以使用),因为树的难度相比线性表大一些并且树的拓展性很强，你所知道的树、二叉树、二叉排序树，AVL树，线索二叉树、红黑树、B数、线段树等等高级数据结构。

然而二叉排序树是所有的基础，所以彻底搞懂二叉排序树也是非常重要的。

树参考王道数据结构二叉树也是树的一种，而二叉排序树又是二叉树的一种。

•树是递归的，将树的任何一个节点以及节点下的节点都能组合成一个新的树。

并且很多操作基于递归完成。

•根节点：最上面的那个节点(root)，根节点没有前驱节点，只有子节点（0个或多个都可以）•层数：一般认为根节点是第1层(有的也说第0层)。

而树的高度就是层数最高(上图层数开始为1)节点的层数•节点关系:父节点：就是链接该节点的上一层节点,孩子节点:和父节点对应，上下关系。

而祖先节点是父节点的父节点(或者祖先）节点。

兄弟节点：拥有同一个父节点的节点们！•度：节点的度就是节点拥有孩子节点的个数(是孩子不是子孙).而树的度(最大)节点的度。

同时，如果度大于0就成为分支节点,度等于0就成为叶子节点（没有子孙）。

相关性质：•树的节点数=所有节点度数 1.•度为m的树第i层最多有mi-1个节点。

(i>=1)•高度而h的m叉树最多（mh-1）/(m-1)个节点(等比数列求和) •n个节点的m叉树最小高度[logm(n(m-1) 1)]二叉树二叉树是一树的一种，但应用比较多，所以需要深入学习。

二叉树的每个节点最多只有两个节点。

二叉树与度为2的树的区别：•一：度为2的的树必须有三个节点以上，二叉树可以为空。

•二：二叉树的度不一定为2：比如说斜树。

•三：二叉树有左右节点区分，而度为2的树没有左右节点的区分。

几种特殊二叉树：•满二叉树。

高度为n的满二叉树有2n-1个节点•完全二叉树：上面一层全部满，最下一层从左到右顺序排列•二叉排序树：树按照一定规则插入排序(本文详解)。

数据结构—树二叉树前序遍历、中序遍历、后序遍历【图解实现】AI研习图书馆，发现不一样的精彩世界数据结构二叉树的遍历一、树在谈二叉树的知识点之前，我们首先来看一下树和图的基本概念。

树：不包含回路的连通无向图，树是一种简单的非线性结构。

由于树有一个不包含回路的特点，因此树被赋予了许多特性，如下所示：1、一棵树中任意的两个结点有且仅有唯一的一条路径连通2、一棵树如果有n个结点，那么它一定恰好有n-1条边3、在一棵树中加上一条边，将会构成一个回路4、一棵树中有且仅有一个没有前驱的结点，即为根结点通常情况下，我们在对树进行讨论的时候，将一棵树中的每个点称为结点:根结点：没有父结点的结点叶结点：没有子结点的结点内部结点：一个结点既不是根结点也不是叶结点每个结点有一个深度的概念，例如上图左边的树，4号结点深度是3。

二、二叉树1. 基本概念二叉树是一种非线性结构，二叉树是由递归定义的，其结点有左右子树之分。

2. 二叉树的存储结构二叉树一般采用链式存储结构，存储结点由数据域和指针域组成，二叉树的链式存储结构也称为二叉链表。

指针域：左指针域和右指针域特点：1、每个结点最多有两颗子树2、左子树和右子树是有顺序的，次序不能颠倒3、即使某个结点只有一颗子树，也要区分左右子树4、二叉树可为空，空的二叉树没有结点，非空二叉树有且仅有一个根节点二叉树中有两种比较特殊的二叉树：满二叉树、完全二叉树，对于满二叉树和完全二叉树可以按照层次进行顺序存储。

满二叉树：二叉树中每个内部结点都存在左子树和右子树满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

满二叉树的严格定义：一颗深度为h且具有2h-1个结点的二叉树。

完全二叉树：解释一：如果一颗二叉树除了最右边位置上有一个或几个叶结点缺少外，其他都是丰满的，那么这样的二叉树就是完全二叉树。

解释二：除第h层外，其他各层（1到h-1）的结点数都达到最大个数，第h层从右向左连续缺若干结点，则这个二叉树就是完全二叉树。

平衡二叉树操作演示.数据结构实习报告题目：平衡二叉树的操作演示班级：信息管理与信息系统11-平衡二叉树的操作演示班级：信息管理与信息系统11：崔佳学号：201101050903完成日期：2013.06.25一、需求分析1. 初始，平衡二叉树为空树，操作界面给出两棵平衡二叉树的显示、查找、插入、删除、销毁、合并两棵树，几种选择。

其中查找、插入和删除操作均要提示用户输入关键字。

每次插入或删除一个节点后都会更新平衡二叉树的显示。

2. 平衡二叉树的显示采用凹入表形式。

3.每次操作完毕后都会给出相应的操作结果，并进入下一次操作，知道用户选择退出二、概要设计1.平衡二叉树的抽象数据类型定义：ADT BalancedBinaryTree{ 数据对象D：D是具有相同特性的数据元素的集合。

各个数据元素均含有类型相同，可唯一标志的数据元素的关键字。

数据关系R：数据元素同属一个集合。

基本操作P：InitA VL(BSTree T) 操作结果：构造一个空的平衡二叉树T DestroyA VL(BSTree T) 初始条件：平衡二叉树T存在操作结果：销毁平衡二叉树T SearchA VL(BSTree T,int key) 初始条件：平衡二叉树T存在，key为和关键字相同类型的给定值操作结果：若T中存在关键字和key相等的数据元素，则返回指向该元素的指针，否则为空InsertA VL(BSTree T,int key,Status taller) 初始条件：平衡二叉树T存在，key和关键字的类型相同操作结果：若T中存在关键字等于key的数据元素则返回，若不存在则插入一个关键字为key的元素DeleteA VL(BSTree T,int key,Status lower) 初始条件：平衡二叉树T存在，key和关键字的类型相同操作结果：若T中存在关键字和key相同的数据元素则删除它}ADT BalancedBinaryTree2.本程序包含二个模块1）主程序模块：void main（）{ 接收命令；While(“命令”！＝“退出”){ 处理命令；清屏并得新打印提示信息；接收下一条命令；}}2）平衡二叉树基本操作实现平衡二叉树的抽象数据类型的各函数原型。

平衡⼆叉树的定义及基本操作（查找、插⼊、删除）及代码实现⽂章⽬录平衡⼆叉树的定义 为了避免树的⾼度增长过快，降低⼆叉排序树的性能，我们规定在插⼊和删除⼆叉树结点时，要保证在任意结点的左、右⼦树⾼度差的绝对值不超过1，将这样的树称为平衡⼆叉树（Balanced Binary Tree），简称平衡树（AVL）。

此外，AVL树⼜称为⾼度平衡的⼆叉查找树。

 定义结点左⼦树与右⼦树的⾼度差为该结点的平衡因⼦，则平衡⼆叉树结点的平衡因⼦的值只可能是-1，0或1 。

平衡⼆叉树可定义为：或者是⼀棵空树，或者是具有下列性质的⼆叉树：它的左⼦树和右⼦树都是平衡⼆叉树，且左⼦树和右⼦树的⾼度差的绝对值不超过1。

平衡⼆叉树的结点类型描述：typedef struct AVLNode{int data;//数据域int bf;//平衡因⼦struct AVLNode *lchild,*rchild;//指针域}AVLNode,*AVLTree;平衡⼆叉树的查找 平衡⼆叉树上进⾏查找的过程与⼆叉排序树相同，详细完整代码请参照。

因此，在查找过程中，与给定值进⾏⽐较的关键字个数不超过树的深度。

 可以证明，含有n个结点的平衡⼆叉树的最⼤深度为O(log n)，因此平衡⼆叉树的平均查找长度为O(log n)。

22平衡⼆叉树的平衡旋转 ⼆叉排序树保证平衡的基本思想如下： 每当在⼆叉排序树中插⼊（或删除）⼀个结点时，⾸先检查其插⼊路径上的结点是否因为此次操作导致了不平衡。

若导致了不平衡，则先找到插⼊路径上离插⼊结点最近的平衡因⼦的绝对值⼤于1的结点A，再对以A为根的⼦树，在保持⼆叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

 ⼀般可将失去平衡后进⾏调整的规律归纳为下列四种情况：LL平衡旋转，RR平衡旋转，LR平衡旋转，RL平衡旋转。

LL平衡旋转（右单旋转） 由于在结点A的左孩⼦（L）的左⼦树（L）上插⼊了新结点，A的平衡因⼦由1增⾄2，导致了以A为根的⼦树失去平衡。

平衡二叉树关于树的深度是平衡的，具有较高的检索效率。

平衡二叉树或是一棵空树，或是具有下列性质的二叉排序树：其左子树和右子树都是平衡二叉树，而且左右子树深度之差绝对值不超过1. 由此引出了平衡因子（balance factor）的概念，bf定义为该结点的左子树的深度减去右子树的深度（有些书是右子树深度减去左子树深度，我是按照左子树减去右子树来计算的，下面的代码也是这样定义的），所以平衡二叉树的结点的平衡因子只可能是-1，0，1 ，某个结点的平衡因子绝对值大于1，该二叉树就不平衡。

平衡二叉树在出现不平衡状态的时候，要进行平衡旋转处理，有四种平衡旋转处理（单向右旋处理，单向左旋处理，双向旋转（先左后右）处理，双向旋转（先右后左）处理），归根到底是两种（单向左旋处理和单向右旋处理）。

文件"tree.h"view plain1.#include<iostream>2.#include<stack>3.#include<queue>ing namespace std;5.6.const int LH=1; //左子树比右子树高17.const int EH=0; //左右子树一样高8.const int RH=-1;//右子树比左子树高19.const int MAX_NODE_NUM=20; //结点数目上限10.11.class AVL_Tree;12.13.class AvlNode14.{15.int data;16.int bf; //平衡因子17. AvlNode *lchild;18. AvlNode *rchild;19.friend class AVL_Tree;20.};21.22.class AVL_Tree23.{24.public:25.int Get_data(AvlNode *p)26. {27.return p->data;28. }29.30.void Create_AVl(AvlNode *&T) //建树31. {32. cout<<"输入平衡二叉树的元素,输入-1代表结束输入：";33.int num[MAX_NODE_NUM];34.int a,i=0;35.while(cin>>a && a!=-1)36. {37. num[i]=a;38. i++;39. }40.41.if(num[0]==-1)42. {43. cout<<"平衡树为空"<<endl;44. T=NULL;45.return;46. }47.48.int k=i;49.bool taller=false;50.for(i=0;i<k;i++)51. Insert_Avl(T,num[i],taller);//逐个进行插入，插入过程看下面的示意图52. cout<<"_____建树完成____"<<endl;53. }54.55.void L_Rotate(AvlNode *&p)56. {57.//以p为根节点的二叉排序树进行单向左旋处理58. AvlNode *rc=p->rchild;59. p->rchild=rc->lchild;60. rc->lchild=p;61. p=rc;62. }63.64.void R_Rotate(AvlNode *&p)65. {66.//以p为根节点的二叉排序树进行单向右旋处理67. AvlNode *lc=p->lchild;68. p->lchild=lc->rchild;69. lc->rchild=p;70. p=lc;71. }72.73.void Left_Balance(AvlNode *&T)74. {75.//以T为根节点的二叉排序树进行左平衡旋转处理76. AvlNode *lc,*rd;77. lc=T->lchild;78.switch(lc->bf)79. {80.case LH:81.//新结点插在T的左孩子的左子树上，做单向右旋处理82. T->bf=lc->bf=EH;83. R_Rotate(T);84.break;85.case RH:86.//新结点插在T的左孩子的右子树上，要进行双旋平衡处理（先左后右）87. rd=lc->rchild;88.switch(rd->bf)89. {90.case LH:91.//插在右子树的左孩子上92. T->bf=RH;93. lc->bf=EH;94.break;95.case EH:96. T->bf=lc->bf=EH;97.break;98.case RH:99. T->bf=EH;100. lc->bf=LH;101.break;102. }103. rd->bf=EH;104. L_Rotate(T->lchild);//先对T的左子树进行单向左旋处理105. R_Rotate(T); //再对T进行单向右旋处理106. }107. }108.109.void Right_Balance(AvlNode *&T)110. {111.//以T为根节点的二叉排序树进行右平衡旋转处理112. AvlNode *rc,*ld;113. rc=T->rchild;114.switch(rc->bf)115. {116.case RH:117.//新结点插在右孩子的右子树上，进行单向左旋处理118. T->bf=rc->bf=EH;119. L_Rotate(T);120.break;121.case LH:122.//新结点插在T的右孩子的左子树上，要进行右平衡旋转处理（先右再左）123. ld=rc->lchild;124.switch(ld->bf)125. {126.case LH:127. T->bf=LH;128. rc->bf=EH;129.break;130.case EH:131. T->bf=rc->bf=EH;132.break;133.case RH:134. T->bf=EH;135. rc->bf=RH;136.break;137. }138. ld->bf=EH;139. R_Rotate(T->rchild);//先对T的右子树进行单向右旋处理140. L_Rotate(T); //再对T进行单向左旋处理141. }142. }143.144.bool Insert_Avl(AvlNode *&T,int num,bool &taller) //插入145. {146.//若在平衡二叉树中不存在结点值和num一样大小的结点147.//则插入值为num的新结点，并返回true148.//若因为插入而使得二叉排序树失去平衡，则做平衡旋转处理149.//taller反映树是否长高150.151.if(!T)152. {153.//插入新结点，树长高，taller为true154. T=new AvlNode;155. T->data=num;156. T->lchild=T->rchild=NULL;157. T->bf=EH;158. taller=true;159. }161. {162.if(num==T->data)163. {164.//不重复插入165. taller=false;166.return false;167. }168.if(num<T->data) //继续在T的左子树中进行搜索169. {170.if(!Insert_Avl(T->lchild,num,taller))//插入不成功171.return false;172.if(taller) //已插入T的左子树,且左子树长高173. {174.switch(T->bf)175. {176.case LH:177./*—————————————————————178. / 插入前左子树高于右子树，需要进行做平衡处理179. / 不管是单向左旋处理，还是先左后右平衡处理180. / 处理结果都是使得插入新结点后，树的高度不变181. /—————————————————————*/182.183. Left_Balance(T);184. taller=false;185.break;186.case EH:187.//插入前左右子树等高，现在插入新街点后，左子树比右子树高188.189. T->bf=LH;190. taller=true;191.break;192.case RH:193.//插入前右子树比左子树高，现在新结点插入左子树后，树变为左右子树等高194.195. T->bf=EH;196. taller=false;197.break;198.199. }200. }201. }202.else204.//num>T->data 在T的右子树中继续搜索205.if(!Insert_Avl(T->rchild,num,taller))206.return false;207.if(taller)208. {209.switch(T->bf)210. {211.case LH:212.//插入前左子树比右子树高，现在插入T的右子树后，左右子树等高213.214. T->bf=EH;215. taller=false;216.break;217.case EH:218.//插入前左右子树等高，现在插入后，右子树比左子树高219.220. T->bf=RH;221. taller=true;222.break;223.224.case RH:225.//插入前右子树比坐子树高，插入后，排序树失去平衡，需要进行右平衡处理226. Right_Balance(T);227. taller=false;228.break;229.230. }231. }232. }233. }234.return true;235. }236.237.bool Search_Avl(AvlNode *T,int num,AvlNode *&f,AvlNode *&p) //搜索238. {239.//用p带回查找到的顶点的地址,f带回p的双亲结点240. p=T;241.while(p)242. {243.if(p->data==num)244.return true;245.if(p->data>num)246. {247. f=p;248. p=p->lchild;249. }250.else251. {252. f=p;253. p=p->rchild;254. }255. }256.return false;257. }258.259.void Delete_AVL(AvlNode *&T,int num) //删除260. {261./*---------------------------------------------------------262. / 从树中删除一个节点后，要保证删后的树还是一棵平衡二叉树，263. / 删除前，首先是在树中查找是否有这个结点，用p指向该结点，264. / 用f指向p的双亲结点，这个结点在树中的位置有下面四种情况: 265. / 266. / 1:如果p指向的结点是叶子结点，那么直接将f指针的左子树或者267. / 右子树置空，然后删除p结点即可。

平衡二叉树操作的演示#include<stdio.h>#include<malloc.h>typedef int KeyType; //定义关键字类型typedef struct node //记录类型{KeyType key; //关键字项int bf; //平衡因子struct node *lchild,*rchild; //左右孩子指针}BSTNode;void LeftProcess(BSTNode *&p,int &taller) {//对以指针p所指结点为根的二叉树作左平衡旋转处理，本算法结束时，//指针p指向新的根结点BSTNode *p1,*p2;if(p->bf==0) //原本左右子树等高，现因左子树增高而使树增高{p->bf=1;taller=1;}else if(p->bf==-1) //原本右子树比左子树高，现左右子树等高{p->bf=0;taller=0;}else //原本左子树比右子树高，须作左子树的平衡处理{p1=p->lchild; //p指向*p的左子树根节点if(p1->bf==1) //新结点插入在*p的左孩子的左子树上，要做LL调整{p->lchild=p1->rchild;p1->rchild=p;p->bf=p1->bf=0;p=p1;}else if(p1->bf==-1) //新结点插入在*p的左孩子的右子树上，要做LR调整{p2=p1->rchild;p1->rchild=p2->lchild;p2->lchild=p1;p->lchild=p2->rchild;p2->rchild=p;if(p2->bf==0) //新结点插入在*p2处作为叶子结点的情况p->bf=p1->bf=0;else if(p2->bf==1) //新结点插在*p2的左子树上的情况{p1->bf=0;p->bf=-1;}else //新结点插在*p2的右子树上的情况{p1->bf=1;p->bf=0;}p=p2;p->bf=0; //仍将p指向新的根结点，并置其bf值为0}taller=0;}}void RightProcess(BSTNode *&p,int &taller) {//对以指针p所指结点为根的二叉树作右平衡旋转处理，本算法结束时，//指针p指向新的根结点BSTNode *p1,*p2;if(p->bf==0) //原本左右子树等高，现因右子树增高而使树增高{p->bf=-1;taller=1;}else if(p->bf==1) //原本左子树比右子树高，现左右子树等高{p->bf=0;taller=0;}else //原本右子树比左子树高，须作右子树的平衡处理{p1=p->rchild; //p指向*p的右子树根结点if(p1->bf==-1) //新结点插入在*p的右孩子的左子树上，要做RR调整{p->rchild=p1->lchild;p1->lchild=p;p->bf=p1->bf=0;p=p1;}else if(p1->bf==1) //新结点插入在*p的右孩子的左子树上，要做RL调整{p2=p1->lchild;p1->lchild=p2->rchild;p2->rchild=p1;p->rchild=p2->lchild;p2->lchild=p;if(p2->bf==0) //新结点插在*p2处作为叶子结点的情况p->bf=p1->bf=0;else if(p2->bf==-1) //新结点插在*p2的右子树上的情况{p1->bf=0;p->bf=1;}else //新结点插在*p2的左子树上的情况{p1->bf=-1;p->bf=0;}p=p2;p->bf=0; //仍将p指向新的结点，并置其bf值为0}taller=0;}}int InsertA VL(BSTNode*&b,KeyType e,int &taller){//若在平衡二叉排序树b中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点，//并返回1，否则返回0。

数据结构平衡二叉树的操作演示平衡二叉树（AVL树）是一种自平衡的二叉树，可以在O(log n)的时间内完成插入、删除和操作。

AVL树的平衡性是通过对树节点进行左旋和右旋操作来实现的。

下面将详细介绍AVL树的操作演示。

AVL树的定义和二叉树相似，每个节点包含一个键值和指向左右子树的指针。

任意节点的左子树和右子树的高度最多相差1，这个特性使得AVL树始终保持平衡。

1.插入操作插入操作是AVL树中最复杂的操作之一，因为插入后可能会破坏树的平衡性。

下面通过一个示例来演示AVL树的插入操作。

假设我们要向一棵空树插入节点5，插入过程如下：1.创建一个新节点，值为52.将新节点插入根节点。

3.检查树的平衡性。

根据AVL树的定义，左子树和右子树的高度差最多为1、在这个例子中，树是平衡的。

4.更新每个节点的高度值。

如果我们插入节点6，插入过程如下：1.创建一个新节点，值为62.将新节点插入到节点5的右子树。

3.检查树的平衡性。

在这个例子中，树不再是平衡的，因为节点5的左子树和右子树的高度差为24.执行旋转操作来恢复树的平衡性。

在这个例子中，我们需要对节点5进行左旋操作。

5.更新每个节点的高度值。

2.删除操作删除操作是AVL树中另一个可能破坏树的平衡性的操作。

下面通过一个示例来演示AVL树的删除操作。

假设我们要删除节点5，删除过程如下：1.在树中找到要删除的节点，即节点52.如果要删除的节点是叶子节点或只有一个子节点，直接删除。

在这个例子中，节点5是一个叶子节点，可以直接删除。

3.如果要删除的节点有两个子节点，找到其后继节点（即右子树中的最小节点）或前驱节点（即左子树中的最大节点）来取代它。

在这个例子中，我们找到节点6来取代节点54.如果取代节点是叶子节点或只有一个子节点，直接用它取代要删除的节点。

在这个例子中，我们用节点6取代了节点55.检查树的平衡性。

在这个例子中，树是平衡的。

6.更新每个节点的高度值。

3.左旋操作左旋操作用于恢复树的平衡性。

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称《数据结构》课题名称完全二叉树操作演示专业班级计算机科学与技术专升本1班学号********、********、********姓名李鹏王帅李泳波联系方式指导教师严小燕完成日期: 2014年12月27 日目录1 数据结构课程设计任务书 (1)1.1题目 (1)1.2目的 (1)1.3要求 (1)2 总体设计 (1)2.1功能模块设计 (1)2.2所有功能模块流程图 (1)3 详细设计 (2)3.1程序中所采用的数据结构及存储结构的说明 (2)3.2算法设计思想 (3)3.3主要的功能函数 (3)4 调试与测试 (3)4.1调试方法与步骤 (4)4.2测试结果分析与讨论 (4)4.3测试过程中遇到的主要问题及采取的解决措施 (5)5 时间复杂度分析 (6)6 程序清单 (6)7 总结 (12)参考文献 (13)1 数据结构课程设计任务书1.1题目完全二叉树操作演示1.2目的（1）掌握二叉树的概念和性质。

（2）掌握完全二叉树存储结构。

（3）掌握完全二叉树的基本操作。

1.3 要求（1）创建完全二叉树（用字母表示节点）(用顺序方式存储)。

（2）求二叉树的深度和叶子结点数。

（3）实现二叉树的前序、中序、后序和层次遍历。

（4）查找给定结点的双亲、祖先和左右孩子节点。

2 总体设计2.1 功能模块设计根据课程设计题目的功能要求，各个功能模块的组成框图如图1：图 1 功能组成框图2.2 所有功能模块流程图设计好功能模块后，各个模块的关系如下图2：图 2 流程图3 详细设计3.1程序中所采用的数据结构及存储结构的说明（1）整个程序采用结构体与顺序表相结合的编程方法一共完成了7个功能。

在你输入错误时有报错消息，这样使整个程序运行起来更加完整。

程序中有若干个子函数被主函数调用执行。

结构体定义如下：#define MAX 100 //定义100个节点typedef struct{char dat; //节点信息}node;typedef struct Tree //节点组成树{int length;node *r; //指向根节点}Tree;3.2 算法设计思想完全二叉树具有以下几个性质，由此可设计出相应算法。

平衡二叉树资料大全：算法、代码、动画演示、课程设计平衡二叉树资料大全：算法、代码、动画演示、课程设计二叉排序树（又叫二叉查找树）具有log(n)的执行效率，但是在极端情况下（构建的二叉树为单分支）查找的时间效率为n。

为避免极端情况的出现，需要对二叉排序树平衡化，即通过算法保证左右每一颗子树的左右子树的高度差的绝对值不超过1，这样的二叉树叫做平衡二叉树。

平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树、左偏树等。

数据结构的教材上讲的平衡二叉树是AVL树。

1、AVL的插入算法描述在平衡的二叉排序树T上插入一个关键码为kx的新元素，递归算法可描述如下：㈠若T为空树，则插入一个数据元素为kx的新结点作为T的根结点，树的深度增1；㈡若kx和T的根结点关键码相等，则不进行插入；㈢若kx小于T的根结点关键码，而且在T的左子树中不存在与kx有相同关键码的结点,则将新元素插入在T的左子树上，并且当插入之后的左子树深度增加1时，分别就下列情况进行处理：⑴ T的根结点平衡因子为-1(右子树的深度大于左子树的深度)，则将根结点的平衡因子更改为0，T的深度不变；⑵ T的根结点平衡因子为0(左、右子树的深度相等)，则将根结点的平衡因子更改为1，T 的深度增加1；⑶ T的根结点平衡因子为1(左子树的深度大于右子树的深度),则若T的左子树根结点的平衡因子为1,需进行单向右旋平衡处理并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变；若T的左子树根结点平衡因子为-1，需进行先左后右双向旋转平衡处理，并且在旋转处理之后，修改根结点和其左、右子树根结点的平衡因子，树的深度不变。

㈣若kx大于T的根结点关键码，而且在T的右子树中不存在与kx有相同关键码的结点，则将新元素插入在T的右子树上并且当插入之后的右子树深度增加1时，分别就不同情况处理之。

其处理操作和㈢中所述相对称。

音频讲解。

平衡的调整共有四种情况：分别为LL,LR,RR,RL。

实验四平衡二叉树演示1•问题定义及需求分析课题目的和任务问题描述：利用平衡二叉树设计动态查找表。

\/ 实验要求：\设计平衡二叉树的动态演示的模拟程序。

1）采用平衡二叉树存储结构。

2）完成平衡二叉树的创建、查找、插入和删除的演示操作。

3）可以考虑两棵平衡二叉树的合并。

数据形式输入数据形式：通过键盘输入数据输入值的范围：树中元素的值为float型，范围为至+38;树的名称为char类型数据，可以输入字母，数字和符号，但是长度必须在20位以内；对菜单进行操作时，输入数据长度必须在200以内，且有效的输入数据为0至7,其中0为退出程序，1至7为对应菜单的操作选项。

输出数据形式：输出到显示器。

程序功能\ 创建平衡二叉树存储结构，通过平衡因子，使二叉排序树达到平衡，提供平衡二叉树的创建、查找和删除，树中元素的查找、插入和删除等基本功能，可以实现创建多棵平衡二叉树，并且能够进行两棵树的合并。

通过平衡二叉树，能够使树时刻保持平衡，从而提高在树中遍历数据的速度，具有重要意义。

测试数据10 1 0 1 0 log n 0 log nO 2n［青输入你想要访冋的树名：t2t2树现在的形狀为(’〔)'里为平衛因子，7代表空儿3(-1)1(0) 7(0)咔+ 4(0 10(0)请按任意犍继续・・・.请输入你祖要访问的树名’12t2树现在的形状为('()'里为平術因子■ *代表空h 3M)1(0) 4(7* * * io to)***□!：****\z衡树"<<endl; 2. 在树中查找元素"<<endl;3. 在树中插入元素"<<endl;4. 在树中删除元素"<<endl;5. 输出二叉平衡树结构示意图"<<e ndl;6. 合并两个二叉平衡树"<<e ndl;7. 删除二叉平衡树"<<endl<<endl;0退出程序)："；建二叉平break;}}switch(a){case '1':{system("cls");cout<<"请输入需要创建的平衡树个数:";int j,k;cin> >k;for(j=0;j<k;j++){cout<<"请输入第"<<j+1<<"棵平衡树的树名(小于20个字符)："; char name[NAME_LENGTH]; /cin»n ame;cout<<"请输入元素个数:"<<endl;int m,n;cin>>n; \ /cout<<"请依次输入元素:"<<endl;Type e;AVL t=NULL;for(m=0;m <n ;m++){cin >>;int taller=O;<<e ndl;}else{cout<<"该树中不存在这个数！"<<e ndl;}system("pause");system("cls");break;}case 3:{system("cls");cout<<"请输入你想要访问的树名："<<e ndl;char n ame[NAME_LENGTH];cin»n ame;Li nk s;if(!SearchL(l, name,s)){cout<<"未找到该名字的平衡树！"<<e ndl;system("pause");system("cls");break;}cout<<"请输入插入元素个数"<<e ndl;int m,n;cin»n;cout<<"请依次输入插入元素"<<e ndl;Type e;for(m=0;m <n ;m++){cin >>;int taller=O;〃增高标识，1为增高，0为不增高In sertTree(s->t,e,taller);}\ cout<<"插入成功！"<<endl;system("pause");system("cls");break;}case '4':{system("cls");cout<<"请输入你想要访问的树名："<<e ndl;char n ame[NAME_LENGTH];cin»n ame; \ /Li nk s;if(!SearchL(l, name,s)){'*'代表空）:cout<<"未找到该名字的平衡树！ "<<e ndl; system("pause"); system("cls"); break;}cout<<"请输入删除元素个数 "<<e ndl; int m,n; cin»n;cout<<"请依次输入需要删除的元素 "<<e ndl; Type e;for(m=0;m <n ;m++){cin >>;int shorter=0;〃降低表示，1为降低，0为不降低 DeleteTree(s->t,e,shorter); }cout<<"删除成功！ "<<e ndl; system("pause"); system("cls"); break; }case '5':{system("cls");cout<<"请输入你想要访问的树名： "<<e ndl; char n ame[NAME_LENGTH]; cin»n ame; Li nk s;if(!SearchL(l, name,s)){cout<<"未找到该名字的平衡树！ "<<e ndl; system("pause"); system("cls"); break;\ }if(s->t!=NULL){cout<<s->tree_name<<"树现在的形状为('()'里为平衡因子, "<<e ndl;Prin tTreeStructure(s->t); cout<<e ndl; }system("pause"); system("cls"); break; }case '6':{system("cls");"<<e ndl;（会将后者合并到前者）: cout<<"请分别输入你想要合并的两个树的名字char n ame1[NAME_LENGTH]; cin»n amel;Li nk s1;if(!SearchL(l, name1,s1)){cout<<"未找到该名字的平衡树！"<<e ndl;system("pause");system("cls");break;}char n ame2[NAME_LENGTH];cin»n ame2;Li nk s2;if(!SearchL(l, name2,s2)){cout<<"未找到该名字的平衡树！"<<e ndl;system("pause");system("cls");break;}else{MergeTree(s1->t,s2->t);〃将t2 合并到t1 上DeleteL(s2);〃删除链表结点12 cout<<"合并树成功！"<<e ndl;system("pause"); system("cls");break;}}case '7':{system("cls");cout<<"请输入你想要删除的树的名字："<<e ndl;\ char name[NAME_LENGTH];cin»n ame;Li nk s;if(!SearchL(l, name,s)){cout<<"未找到该名字的平衡树！"<<e ndl;system("pause");system("cls");break;}else{ \ /DestroyTree(s->t);DeleteL(s);cout<<"删除树成功！"<<e ndl;system("pause");system("cls");break;}}}}}/**/#i nclude""void LeftBalance(AVL& t){〃左部平衡化处理AVL l,lr;l=t->lchild;switch(l->bf){//检查T的左子树平衡度，并作相应的平衡处理case，做单右旋处理t->bf=l->bf=EH;R_Rotate(t);break;case , insertAVL 用不着t->bf=LH;l->bf=RH;R_Rotate(t);break;case，做双旋处理lr=l->rchild;switch(lr->bf){case LH:t->bf=RH;l->bf=EH;break;case EH:t->bf=l->bf=EH;break;case RH:t->bf=EH;l->bf=LH;break;}lr->bf=EH; \ /L_Rotate(t->lchild);R_Rotate(t);}}void RightBalance(AVL& t){〃右部平衡化处理AVL r,rl;r=t->rchild;switch(r->bf){case，要做单左旋处理t->bf=r->bf=EH;L_Rotate(t);break;case , insertAVL 用不着t->bf=RH;r->bf=LH;L_Rotate(t);break;case，要做双旋处理rl=r->lchild;switch(rl->bf){case LH:t->bf=EH;r->bf=RH;break;case EH:t->bf=r->bf=EH;break;case RH:t->bf=LH;r->bf=EH;break;}rl->bf=EH;R_Rotate(t->rchild);L_Rotate(t); \}}/**/#i nclude""int InsertTree(AVL& t,Type e,int& taller){// 二叉平衡树的结点插入if(!t){t=(AVL)malloc(sizeof(AVLTree)); 、、t->=;t->lchild=t->rchild=NULL;0,结束t->bf=EH;taller=1;}else{if==t->{〃找到重复元素时，不插入，返回 0taller=0;return 0;}if<t->{〃应在T 的左子树中搜寻if(!l nsertTree(t->lchild,e,taller))return 0;// 找到重复元素，依次返回if(taller){〃插入左子树，且左子树变高switch(t->bf){case ，需要做左平衡处理LeftBala nce(t);taller=0;break;case ，现因左子树增高而树增高t->bf=LH;taller=1;break;case ，现在左右子树等高t->bf=EH;taller=0;break;"/switch}//if}//ifelse{//应在T 的右子树中搜寻if(!InsertTree(t->rchild,e,taller))returin 0; if(taller){//插入右子树，且右子树长高 switch(t->bf){case ，现在左右子树等高t->bf=EH;taller=0;break;case ，现在右子树变高t->bf=RH;taller=1;break;case ，现在需做右平衡处理RightBala nce(t);taller=0;break;}//switch即查找q}//if}//else}//elsereturn 1;}/**/#i nclude""int DeleteTree(AVL& t,Type e,int& shorter){〃 平衡二叉树的结点删除if(t==NULL){〃不存在该元素return 0;//删除失败}else if==t->{//找到元素结点 \AVL q=NULL;if(t->lchild==NULL){// 左子树为空q=t;t=t->rchild;delete q;shorter=1;}else if(t->rchild==NULL){// 右子树为空q=t;t=t->lchild;delete q;shorter=1;}else{//左右子树都存在q=t->lchild;\ while(q->rchild){//找到要删除结点t 的左孩子的最右孩子 qq=q->rchild;}t->=q->;//把q 的值给tDeleteTree(t->lchild,q->data,shorter);// 在左子树中递归删除前驱结点。

平衡⼆叉树——如何实现不平衡⼆叉树到平衡⼆叉树转⾃：/liuzhanchen1987/article/details/7325293平衡⼆叉树定义(AVL)：它或者是⼀颗空树，或者具有以下性质的⼆叉树：它的左⼦树和右⼦树的深度之差的绝对值不超过1，且它的左⼦树和右⼦树都是⼀颗平衡⼆叉树。

平衡因⼦(bf)：结点的左⼦树的深度减去右⼦树的深度，那么显然-1<=bf<=1;很显然，平衡⼆叉树是在⼆叉排序树(BST)上引⼊的，就是为了解决⼆叉排序树的不平衡性导致时间复杂度⼤⼤下降，那么AVL就保持住了(BST)的最好时间复杂度O(logn)，所以每次的插⼊和删除都要确保⼆叉树的平衡，那么怎么保持平衡呢？我努⼒看了看上的讲解，但是看的只晕+_+！我对他的讲解很⽆语，他所谓的“旋转”操作讲的不明不⽩，看的我⽓的蛋疼！你说你旋转，你得说清是如何旋转？以那个结点为中⼼，那些或者说那个结点转了，那些结点不动。

你就在哪⾥旋转来旋转去的，谁知道你是咋转的，你在哪慢慢转吧！哥转不过你，另找⾼明！于是在⽹上找啊找，只为想搞明⽩是到底怎么转的！让我对“旋转”有所领悟，表⽰感谢！插⼊时：那究竟是如何“转”的呢？⾸先必须明⽩⼀个核⼼操作，不让它叫“旋转”！⽽叫——>“两个结点的变换”如图：就拿第⼀个来说->点100和101的变换：点101占据点100的位置，点100换到了101的对⾯的位置，其他点的相对位置不变。

我们可以更直观的理解为：把101结点“上提”⼀下！分析：101>100，所以100可以作为101的左孩⼦；也就是在⼆叉排序树中，两个结点这样的变换操作是可⾏的，是符合⼆叉排序树的性质。

不仅这个简单的图，任何复杂的⼆叉排序树都可以，你可以试试，也许你会说如果点101左边有孩⼦怎么办？别着急~，当然有办法！下边正式说这个图的四种不平衡情况（插⼊时）及操作：⾸先还需要明⽩⼀个概念->最⼩不平衡⼦树的根结点：也就是当你进⾏插⼊操作时，找到该需要插⼊结点的位置并插⼊后，从该结点起向上寻找（回溯），第⼀个不平衡的结点即平衡因⼦bf变为-2或2。

平衡二叉树的实现及分析平衡二叉树（Balanced Binary Tree），也称为AVL树，是一种二叉树的特殊类型。

它的特点是树的所有节点的左子树和右子树的高度差不超过1，即任意节点的子树高度差的绝对值不超过1、通过保持树的平衡性，可以有效地提高树的查询效率。

```pythonclass Node:def __init__(self, val):self.val = valself.left = Noneself.right = Noneself.height = 1```接下来是平衡二叉树的实现：```pythonclass AVLTree:def __init__(self):self.root = None#获取节点高度def get_height(self, node):if not node:return 0return node.height#获取节点的平衡因子def get_balance_factor(self, node):if not node:return 0return self.get_height(node.left) -self.get_height(node.right)#左旋转def left_rotate(self, node):new_root = node.rightnode.right = new_root.leftnew_root.left = nodenode.height = 1 + max(self.get_height(node.left),self.get_height(node.right))new_root.height = 1 + max(self.get_height(new_root.left), self.get_height(new_root.right))return new_root#右旋转def right_rotate(self, node):new_root = node.leftnode.left = new_root.rightnew_root.right = nodenode.height = 1 + max(self.get_height(node.left),self.get_height(node.right))new_root.height = 1 + max(self.get_height(new_root.left), self.get_height(new_root.right))return new_root#插入节点def insert_node(self, root, val):if not root:return Node(val)elif val < root.val:root.left = self.insert_node(root.left, val)else:root.right = self.insert_node(root.right, val)root.height = 1 + max(self.get_height(root.left),self.get_height(root.right))balance_factor = self.get_balance_factor(root) if balance_factor > 1:if val < root.left.val:return self.right_rotate(root)else:root.left = self.left_rotate(root.left)return self.right_rotate(root)if balance_factor < -1:if val > root.right.val:return self.left_rotate(root)else:root.right = self.right_rotate(root.right) return self.left_rotate(root)return root#中序遍历def inorder_traversal(self, root):if root:self.inorder_traversal(root.left)print(root.val)self.inorder_traversal(root.right)```在上述代码中，`get_height`函数用于获取节点的高度，`get_balance_factor`函数用于计算节点的平衡因子，`left_rotate`函数实现了左旋转操作，`right_rotate`函数实现了右旋转操作。