一、平衡二叉树
定义特点是1.满足二叉查找树的特点
=》左子树小于根节点
=》右子树大于根节点
2.它的|左子树、与右子树的深度差|<2
=>目的是要充分的利用二叉查找树的特性，维护深度
二、实现
为了维护它的特性，在插入添加的过程中会变得很复杂。参考
1.首先来看下旋转
=》对于树中的元素，还按照这个规则来重新实现
例如：
2.那么在平衡二叉树的插入过程当中会遇到哪些情况？
（1）LL
解决办法=》找到最根的左、右子树深度不平衡的节点
=》然后根的左子树变根节点
=》然后根可以变成右子树
=》如果根的左子树有右子树，则变为此根的左子树
（2）RR
解决办法：同上相反
（3）LR
解决办法：首先调整成LL情况如何调整？
（4）RL
解决办法：首先调整成RR如何调整那？
三、代码实现
=》节点结构
=》查询
=》添加
=》实例化
=》中序遍历
=》效果图
=》删除节点（实现了在）
//节点结构
class TreeNode{
private int num;
private int diff; //平衡因子
private TreeNode leftChild;
private TreeNode rightChild;
//get /set method
}
//得到当前节点的深度
/*
* This will through recursion to get the deep
* but the deep does not contain the current node
* =>judge is null
* =>null return
* =>is not
* =>get the left and right
* =>judge the left right return the max
* */
public static int getDeep(TreeNode t){
if(t==null)return 0;
int leftDeep=0;
int rightDeep=0;
leftDeep+=getDeep(t.getLeftChild());
rightDeep+=getDeep(t.getRightChild());
return leftDeep>=rightDeep?leftDeep+1:rightDeep+1;
}
//实例化当前的节点的平衡因子
/*
* initialization the node attribute diff
* */
public static void initDiff(TreeNode t){
if(t==null)return;
int leftDeep=getDeep(t.getLeftChild());
int rightDeep=getDeep(t.getRightChild());
t.setDiff(leftDeep-rightDeep);
}
//递归实现插入操作
//解决了插入后平衡因子改变的记录
/*
*How to insert a number
*There have two method to input it
*
*if just insert the BST you can not user the recursion
*you can just get the insert node position
*
*use the recursion can get the path
*that after insert the balance is interrupted
* */
public static TreeNode insertBST(TreeNode t,int num){
//if(searchBST(num))return false;
if(t==null){
t=new TreeNode();
t.setNum(num);
t.setLeftChild(null);
t.setRightChild(null);
t.setDiff(0);
}else{
// if(t.getNum()==num){
// return null;
// }
//there have the recursion
//insert left
if(t.getNum()>num){
t.setLeftChild(insertBST(t.getLeftChild(), num));
initDiff(t);
//left-right=2;
if(t.getDiff()==2){
if(num<t.getLeftChild().getNum())
t=LL(t);
else
t=LR(t);
}
}else if(t.getNum()<num){
t.setRightChild(insertBST(t.getRightChild(),num));
initDiff(t);
if(t.getDiff()==-2){
if(num>t.getRightChild().getNum())
t=RR(t);
else
t=RL(t);
}
}
}
return t;
}
//四个旋转情况
//LL
/*
* c b |
* / /\ |
* b => a c |
* / |
* a |
* */
public static TreeNode LL(TreeNode t){
TreeNode tn=t.getLeftChild();
t.setLeftChild(tn.getRightChild());
tn.setRightChild(t);
initDiff(tn);
initDiff(t);
return tn;
}
//RR
/*
* c d |
* \ /\ |
* d => c e |
* \ |
* e |
*
* */
public static TreeNode RR(TreeNode t){
TreeNode tn=t.getRightChild();
t.setRightChild(tn.getLeftChild());
tn.setLeftChild(t);
initDiff(tn);
initDiff(t);
return tn;
}
//LR
/*
* d d
* / /
* a => b =>
* \ /
* b a
* */
public static TreeNode LR(TreeNode t){
t.setLeftChild(RR(t.getLeftChild()));
return LL(t);
}
//RL
public static TreeNode RL(TreeNode t){
t.setRightChild(LL(t.getRightChild()));
return RR(t);
}
//删除操作
//当时在查询树的时候处理思路是这样的
//获得删除的节点，如果是叶子节点，那么它的父节点直接指向null
//如果只有左子树，则左子树替代位置
//如果只有右子树，右子树替代位置
//如果都有则，要么从最左边找到最大的代替然后，删除它
//或者从最右边找到最小的代替然后删除
//此处的思路是这样的
//如果没有右子树那么 左子树代替了
//如果有右子树，那么找到最小的右子树值，替换，删除
public static TreeNode deleteAVL(TreeNode t,int num){
if(t==null)return null;
else{
if(t.getNum()==num){
//在查询二叉树的时候删除分为了
//叶子节点、只有左子树、只有右子树、有左右子树
//
if(t.getRightChild()==null)t=t.getLeftChild();
else{
TreeNode tn=t.getRightChild();
while(tn.getLeftChild()!=null)
tn=tn.getLeftChild();
t.setNum(tn.getNum());
t.setRightChild(deleteAVL(t.getRightChild(),t.getNum()));
initDiff(t);
t.setDiff(t.getDiff()+1);
}
return t;
}else if(t.getNum()>num){
t.setLeftChild(deleteAVL(t.getLeftChild(),num));
}else{
t.setRightChild(deleteAVL(t.getRightChild(),num));
}
}
initDiff(t);
//删除一个节点结果只有+1 -1
if(t.getDiff()==2){
//必定是+1所致
//删除的是右节点
//判断是LL 偶然LR
if(t.getLeftChild().getDiff()==1)
t=LL(t);
else if(t.getLeftChild().getDiff()==-1)
t=LR(t);
}else if(t.getDiff()==-2){
if(t.getRightChild().getDiff()==-1||t.getRightChild().getDiff()==0)
t=RR(t);
else if(t.getRightChild().getDiff()==1)
t=RL(t);
}
return t;
}
相关推荐
2015广工数据结构实验--平衡二叉树(包含源码和实验报告
（2）初始时，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。在查找时，如果查找的关键字不存在，则把其插入到平衡二叉树中。每次插入或删除一个结点后，应更新平衡...
广工数据结构课程设计——平衡二叉树操作的演示 内含源代码、可执行程序以及相应的说明文档 实验的功能包括： [实现提示] (1) 初始，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要...
C语言编写的 数据结构 平衡二叉树 演示、含课程设计报告 多种输出平衡二叉树格式
实现了二叉查找树的查找、插入...实现了平衡二叉树（AVL树）的查找、插入、删除和迭代遍历的完整功能，插入时的各种旋转操作按照经典数据结构教材实现，并有详细的注释和说明。删除操作和相关旋转方法有单独描述文档。
广工数据结构课程设计——平衡二叉树操作的演示 内含源代码、可执行程序以及相应的说明文档 实验的功能包括： [实现提示] (1) 初始，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要...
查找算法，平衡二叉树，大话数据结构里面的。
1， 利用平衡二叉树实现一个动态查找表，实现动态查找表的三种基本功能：查找，插入、删除和附加的两种功能：合并、分裂平衡二叉树。 2， 操作界面要给创建、查找、插入、删除、合并和分裂六种操作供选择。每种操作...
（1） 构建一个平衡二叉树并实现创建、插入、查找、删除、销毁等操作。每种操作均提示输入关键字。每次插入或删除一个结点后，更新平衡二叉树的显示。 （2） 平衡二叉树的显示采用凹入表现形式。 （3）输入的...
用函数实现如下平衡二叉排序树算法： （1） 插入新结点 ...（5） 在二叉树中查找给定关键字(函数返回值为成功1,失败0) （6） 交换各结点的左右子树 （7） 求二叉树的深度 （8） 叶子结点数 （9） 删除某结点
平衡二叉树结构的动态查找表 bool InitDSTable(BSTree * DT); bool DestoryDSTable(BSTree * DT); bool SearchDSTable(const BSTree DT,const KeyTypekey,ValueType * value); bool InsertDSTable(BSTree * DT,const...
数据结构C++版，平衡二叉树，实验，纯代码
平衡二叉树数据结构 平衡二叉树 = 二叉树 查找树 + 左右子树深度差不超过1： 为了解决不平衡导致的线性查询效率问题 二叉查找树 = 二叉树 + 左中右 大小顺序： 二分查找 二叉树 是链表结构 平衡二叉树...
自己曾想上网搜建立平衡二叉树的代码，结果都不太满意，所以自己写了一个建树的程序，用户输入数据，程序根据数据的大小建立平衡二叉树，每输入一次数据则进行平衡操作，直到输入0结束，程序最后还会中序输出此平衡...
本设计综合运用课本第六章和第九章的平衡二叉树和静态、动态查找表知识，设计程序来实现对平衡二叉树的插入、查找、删除等操作。
利用二叉顺序树实现一个动态查找表，实现动态查找表的三项基本功能：查找，插入，删除操作。开始进行顺序二叉树的建立，输入元素的个数以及元素，动态创建一个二叉树，然后进行选择对二叉顺序树进行的操作，即选择，...
包含AVL树的创建，删除，查找等等功能，我使用的是VS2010的编译器，可能用版本低的编译器无法打开
system("title 平衡二叉树操作演示"); Print(); scanf("%d",&s); while(s!=8){ switch(s) { case1: //显示 printf("\t>>-显示-); printf("T:\n"); ViewTree(T,5); printf("t:\n"); ViewTree(t,5); ...
平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各...