正文
平衡二叉树java源代码 平衡二叉树建树
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
平衡二叉树的操作（高手进）
以前做的。
一、 需求分析
1． 本程序是是利用平衡二叉树实现一个动态查找表平衡二叉树java源代码，实现动态查找表的三种基本功能：查找、插入和删除。
2． 初始，平衡二叉树为空树，可以按先序输入平衡二叉树，以输入0结束，中间以回车隔开，创建好二叉树后，可以对其查找，再对其插入，输入0结束插入，再可以对其删除，输入0结束，每次插入或删除一个结点后，更新平衡二叉树的显示。
3． 本程序以用户和计算机的对话方式执行，根据计算机终端显示：“提示信息”下，用户可由键盘输入要执行的操作。
4． 测试数据（附后）
二、 概要设计
1． 抽象数据类型动态查找表的定义如下：
ADT DynamicSearchTable{
数据结构D：D是具有相同特性的数据元素的集合。各个数据元素含有类型相同，可惟一标识数据元素的关键字。
数据关系R：数据元素同属一个集合。
基本操作P：
InitDSTable(DT);
操作结果：构造一个空的动态查找表DT。
DestroyDSTable(DT);
初试条件：动态查找表DT存在。
操作结果: 销毁动态查找表DT。
SearchDSTable(DT,key);
初试条件：动态查找表DT存在，key为和关键字类型相同的给定值。
操作结果: 若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或表中的位置，否则为“空”。
InsertDSTable(DT,e);
初试条件：动态查找表DT存在，e为待插入的数据元素。
操作结果: 若DT中不存在其关键字等于e. key的数据元素，则插入e到DT。
DeleteDSTable(DT,key);
初试条件：动态查找表DT存在，key为和关键字类型相同的给定值。
操作结果: 若DT中存在其关键字等于key的数据元素，则删除之。
TraverseDSTable(DT,Visit());
初试条件：动态查找表DT存在，Visit()是结点操作的应用函数。
操作结果: 按某种次序对DT的每个结点调用函数Visit()一次且至多
一次。一但Visit()失败，则操作失败。
}ADT DynamicSearchTable
2． 本程序包含两个模块：
Void main(){
Do{
接受命令（根据提示输入终点城市和起点城市的序号）平衡二叉树java源代码；
处理命令；
}while(“命令”=“退出”)；
}
3．本程序只有两个模块，调用关系简单
主程序模块
平衡二叉树的模块
三、 详细设计
1． 根据题目要求和查找的基本特点，其结点类型
typedef struct BSTnode{
int data;
int bf;
struct BSTnode *lchild,*rchild;
}BSTnode,*bstree;
#define LH +1
#define EH 0
#define RH -1
/-----------------------------************对平衡二叉树的操作
bstree InsertAVL(bstree T, int e)；
////////在平衡二叉树中插入结点。
int FindAVL(bstree p,int e)；
////////查找平衡二叉树中是否有结点e。
bstree DeleteAVL(bstree T,int e)
////////删除平衡平衡二叉树的结点e，并保持平衡二叉树的性质。
int Preordertraverse(bstree T)
////////按先序遍历平衡二叉树。
/------------------------************平衡二叉树的操作的详细算法
bstree InsertAVL(bstree T, int e)
{
bstree p;
//插入新结点，树长高置taller为TRUE
if(!T) {
T=(bstree)malloc(sizeof(BSTnode));
T-data=e;
T-lchild=T-rchild=NULL;
T-bf=EH;
taller=TRUE;
}
else {
//树中存在和e有相同关键字的结点则不再插入
if(e==T-data){
taller=FALSE;
return NULL;
}
//值小于则继续在树的左子树中搜索
if(e T-data){
//插入到左子树且左子树长高
p=InsertAVL(T-lchild,e);
if(p){
T-lchild=p;
if(taller) {
switch(T-bf){ //检查*T的平衡度
case LH: //原本左子树比右子树高，需要做左平衡处理
T=LeftBalance(T);
taller=FALSE;
break;
case EH: //原本左子树和右子树同高，现因左子树争高而使树增高
T-bf=LH;
taller=TRUE;
break;
case RH: //原本右子树比左子树高，现在左右子树等高
T-bf=EH;
taller=FALSE;
break;
}///////switch(T-bf)
}///////if(taller)
}/////if(p)
}///////if(e T-data)
//继续在*T的右子树中搜索
else{
//插入到右子树且使右子树长高
p=InsertAVL(T-rchild,e);
if (p){
T-rchild=p;
if(taller) {
switch(T-bf){ //检查*T的平衡度
case LH: //原本左子树比右子树高，现在左右子树等高
T-bf=EH;
taller=FALSE;
break;
case EH: //原本左子树和右子树同高，现因右子树增高而使树增高
T-bf=RH;
taller=TRUE;
break;
case RH: //原本右子树比左子树高，需要做右平衡处理
T=RightBalance(T);
taller=FALSE;
break;
}//////switch(T-bf)
}/////if(taller)
}/////if (p)
}//////if(e T-data)
}///////else
return T;
}
int Preordertraverse(bstree T){
if(T){
printf(" %d %d\n",T-data,T-bf);
Preordertraverse(T-lchild);
Preordertraverse(T-rchild);
}
return 1;
}
int FindAVL(bstree p,int e){
if(p==NULL)return NULL;
else if(e==p-data) return true;
else if(ep-data){
p=p-lchild;
return FindAVL(p, e);
}////左子树上查找
else {
p=p-rchild;
return FindAVL( p, e);
}////右子树上查找
}
bstree DeleteAVL(bstree T,int e){
//删除后要保证该二叉树还是平衡的
int n,m=0;/////标记
bstree q;
if(!T)return NULL;
else {
if(e==T-data) {////直接删除
n=Delete(T,e);
m=n;
if(m!=0) {
q=T;
DeleteAVL(T,m);
q-data=m;}
}
else {
if(eT-data){////在左子树上寻找
DeleteAVL(T-lchild,e);
if(shorter){
switch(T-bf){
case LH:T-bf=EH;shorter=true;break;
case EH:T-bf=RH;shorter=false;break;
case RH:Delete_Rightbalance(T);shorter=true;break;
}////switch(T-bf)
}/////if(shorter)
}/////if(eT-data)
else{ /////////在右子树上寻找
DeleteAVL(T-rchild,e);
if(shorter)
switch(T-bf){
case LH:Delete_Leftbalance(T);shorter=true;break;
case EH:T-bf=LH;shorter=false;break;
case RH:T-bf=EH;shorter=true;break;
}////////switch(T-bf)
}////////在右子数上寻找完
}////////在左右子上完
}///////////删除完
return T;
}
2． 主程序和其平衡二叉树java源代码他伪码算法
void main(){
while(e!=0){
if(e!=0) InsertAVL(T,e);
}
while(d!=0){
if(d!=0) InsertAVL(T,d);
Preordertraverse(T);
}
c=FindAVL(T,t);
if(c==1)printf("有要查找的节点\n");
else printf("无要查找的节点\n");
do{
DeleteAVL(T,b);
Preordertraverse(T);
}while(b==1);
}
///右旋
bstree R_Rotate(bstree p){
bstree lc;
lc=p-lchild;
p-lchild=lc-rchild;
lc-rchild=p;
p=lc;
return p;
}
////左旋
bstree L_Rotate(bstree p){
bstree rc;
rc=p-rchild;
p-rchild=rc-lchild;
rc-lchild=p;
p=rc;
return p;
}
/////左平衡处理
bstree LeftBalance(bstree T){
bstree lc,rd;
lc=T-lchild; //lc指向*T的左子树根结点
switch(lc-bf) { //检查*T的左子树平衡度，并做相应的平衡处理
case LH: //新结点插入在*T的左孩子的左子树上，要做单右旋处理
T-bf=lc-bf=EH;
T=R_Rotate(T);
break;
case RH: //新结点插入在*T的左孩子的右子树上，要做双旋处理
rd=lc-rchild; //rd指向*T的左孩子的右子树根
switch(rd-bf){ //修改*T及其左孩子的平衡因子
case LH:
T-bf=RH;
lc-bf=EH;
break;
case EH:
T-bf=lc-bf=EH;
break;
case RH:
T-bf=EH;
lc-bf=LH;
break;
}//////////switch(rd-bf)
rd-bf=EH;
T-lchild=L_Rotate(T-lchild); //对*T的左孩子做左旋平衡处理
T=R_Rotate(T); //对*T做右旋处理
}////////switch(lc-bf)
return T;
}
////右平衡处理
bstree RightBalance(bstree T)
{
bstree rc,ld;
rc=T-rchild; //rc指向*T的右子树根结点
switch(rc-bf) { //检查*T的右子树平衡度，并做相应的平衡处理
case RH: //新结点插入在*T的右孩子的右子树上，要做单右旋处理
T-bf=rc-bf=EH;
T=L_Rotate(T);
break;
case LH: //新结点插入在*T的右孩子的左子树上，要做双旋处理
ld=rc-lchild; //ld指向*T的右孩子的左子树根
switch(ld-bf){ //修改*T及其右孩子的平衡因子
case LH:
T-bf=EH;
rc-bf=RH;
break;
case EH:
T-bf=rc-bf=EH;
break;
case RH:
T-bf=LH;
rc-bf=EH;
break;
}///switch(ld-bf)
ld-bf=EH;
T-rchild=R_Rotate(T-rchild); //对*T的右孩子做右旋平衡处理
T=L_Rotate(T); //对*T做左旋处理
}/////switch(rc-bf)
return T;
}
int Delete(bstree T,int e){
//删除结点
bstree p,q;
e=0;
p=T;
if(!T-rchild) {//右子数为空需要重接它的左子数
T=T-lchild;
free(p);
shorter=true;
}
else if(!T-lchild) {//重接它的右子数
T=T-rchild;
free(p);
shorter=true;
}
else{ //左右子数均不空
q=T-lchild;
while(q-rchild!=NULL){//转左，然后向右到尽头
q=q-rchild;
}
e=q-data;
}
return e;
}
void Delete_Rightbalance(bstree T){
///////////删除在左子树上的，相当于插入在右子树
bstree rc=T-rchild,ld;
switch(rc-bf){
case LH://///////双旋 ，先右旋后左旋
ld=rc-lchild;
rc-lchild=ld-rchild;
ld-rchild=rc;
T-rchild=rc-lchild;
rc-lchild=T;
switch(ld-bf) {
case LH:T-bf=EH;
rc-bf=RH;
break;
case EH:T-bf=rc-bf=EH;
break;
case RH:T-bf=LH;
rc-bf=EH;
break;
}
ld-bf=EH;
T=rc;
shorter=true;break;
case EH:///////删除在左子树，相当于插入在右子树，左单旋
T-rchild=rc-lchild;
rc-lchild=T;
rc-bf=LH;
T-bf=RH;
T=rc;
shorter=EH;break;
case RH:///////删除在左子树，相当于插入在右子树，左单旋
T-rchild=rc-lchild;
rc-lchild=T;
rc-bf=T-bf=EH;
T=rc;
shorter=true;break;
}
}
void Delete_Leftbalance(bstree T)/////删除右子树上的，相当于插入在左子树上
{
bstree p1,p2;
p1=T-lchild;
switch(p1-bf) {
case LH:T-lchild=p1-rchild;//////右旋
p1-rchild=T;
p1-bf=T-bf=EH;
T=p1;
shorter=true;
break;
case EH:T-lchild=p1-rchild;///////右旋
p1-rchild=T;
p1-bf=RH;
T-bf=LH;
T=p1;
shorter=false;
break;
case RH:p2=p1-rchild;//////////右双旋
p1-rchild=p2-lchild;
p2-lchild=p1;
T-lchild=p2-rchild;
p2-rchild=T;
switch(p2-bf){
case LH:T-bf=RH;p1-bf=EH;break;
case EH:T-bf=EH;p1-bf=EH;break;
case RH:T-bf=EH;p1-bf=LH;break;
}
p2-bf=EH;
T=p2;
shorter=true;break;
}
}
3． 函数的调用关系图
Main
InsertAVL Preordertraverse FindAVL DeleteAVL
四、 调试分析
1． 在开始对平衡二叉树的插入后，再做平衡处理时，特别是在做双向旋转平衡处理后的更新时，费了一些时间；
2． 在做平衡二叉树的删除时，当删除结点左右孩子均在时，开始直接用左子树的最大数代替，然后直接删除结点，结果导致删除了将要删除的结点及其孩子均删除了，后来将要删除的结点用左子树的最大树代替后，对左子树的最大结点做好标记，然后再做对其做删除处理。
3． 本程序算法基本简单，没有多大困难，就是在分析做双旋平衡处理的更新时，开始思路有些混乱，后来就好了；
五、 用户手册
1. 本程序的运行环境为DOS操作系统，执行文件为Balanced Tree.exe。
2. 进入演示程序后，按广度遍历输入平衡二叉树，中间以回车键隔开，输入0为结束；再输入要插入的结点，输入0结束，再输入要查找的结点，最后可以输入要删除的结点，输入0结束
六、 测试结果
先按广度遍历创建平衡二叉树（亦可一个一个的插入二叉树的结点）（50 20 60 10 30 55 70 5 15 25 58 90） ，输入0结束，然后可插入结点（39），其会显示插入后的二叉树，输入0，不再插入；输入要查找结点（6），输入要删除的结点（20），其显示如下：
七、 附录
Balance Tree.cpp
相关问答
Q1: 用Java怎么实现平衡树动态演示
public class treenode1 { //二叉树的结点类
public string data; //数据元数
public treenode1 left,right; //指向左,右孩子结点的链
public treenode1(){
this("?");
}
public treenode1(string d){ //构造有值结点
data = d;
left = right = null;
}
public void preorder(treenode1 p){ //先根次序遍历二叉树
if(p!=null){
system.out.print(p.data+" ");
preorder(p.left);
preorder(p.right);
}
}
public void inorder(treenode1 p){ //中根次序遍历二叉树
if(p!=null){ inorder(p.left);
system.out.print(p.data+" ");
inorder(p.right);
}
}
public void postorder(treenode1 p){ //后根次序遍历二叉树
if(p!=null){ postorder(p.left);
postorder(p.right);
system.out.print(p.data+" ");
}
}
}
Q2: 用java实现二叉树
我有很多个(假设10万个)数据要保存起来，以后还需要从保存平衡二叉树java源代码的这些数据中检索是否存在某
个数据，（我想说出二叉树平衡二叉树java源代码的好处，该怎么说呢？那就是说别人的缺点），假如存在数组中，
那么，碰巧要找的数字位于99999那个地方，那查找的速度将很慢，因为要从第1个依次往
后取，取出来后进行比较。平衡二叉树（构建平衡二叉树需要先排序，我们这里就不作考虑
了）可以很好地解决这个问题，但二叉树的遍历（前序，中序，后序）效率要比数组低很多，
public class Node {
public int value;
public Node left;
public Node right;
public void store(intvalue)
right.value=value;
}
else
{
right.store(value);
}
}
}
public boolean find(intvalue)
{
System.out.println("happen" +this.value);
if(value ==this.value)
{
return true;
}
else if(valuethis.value)
{
if(right ==null)returnfalse;
return right.find(value);
}else
{
if(left ==null)returnfalse;
return left.find(value);
}
}
public void preList()
{
System.out.print(this.value+ ",");
if(left!=null)left.preList();
if(right!=null) right.preList();
}
public void middleList()
{
if(left!=null)left.preList();
System.out.print(this.value+ ",");
if(right!=null)right.preList();
}
public void afterList()
{
if(left!=null)left.preList();
if(right!=null)right.preList();
System.out.print(this.value+ ",");
}
public static voidmain(String [] args)
{
int [] data =new int[20];
for(inti=0;idata.length;i++)
{
data[i] = (int)(Math.random()*100)+ 1;
System.out.print(data[i] +",");
}
System.out.println();
Node root = new Node();
root.value = data[0];
for(inti=1;idata.length;i++)
{
root.store(data[i]);
}
root.find(data[19]);
root.preList();
System.out.println();
root.middleList();
System.out.println();
root.afterList();
}
}
Q3: 数据结构：二叉排序树和平衡二叉树的判别
平衡二叉树（AVL）
那对图 1 进行下改造，把数据重新节点重新连接下，图 2 如下：
图 2 可以看到以下特性：
1. 所有左子树的节点都小于其对应的父节点（4，5，6）（7）；（4）（5）；（8） （9）；
2. 所有右子树上的节点都大于其对应的父节点（8，9，10）（7）；（6）（5）；（10）（9）；
3. 每个节点的平衡因子差值绝对值 =1；
4. 每个节点都符合以上三个特征。
满足这样条件的树叫平衡二叉树（AVL）树。
问：那再次查找节点 5，需要遍历多少次呢？
由于数据是按照顺序组织的，那查找起来非常快，从上往下找：7-5，只需要在左子树上查找，也就是遍历 2 次就找到了 5。假设要找到叶子节点 10，只需要在右子树上查找，那也最多需要 3 次，7-9-10。也就说 AVL 树在查找方面性能很好，最坏的情况是找到一个节点需要消耗的次数也就是树的层数， 复杂度为 O(logN)
如果节点非常多呢？假设现在有 31 个节点，用 AVL 树表示如图 3：
图 3 是一棵高度为 4 的 AVL 树，有 5 层共 31 个节点，橙色是 ROOT 节点，蓝色是叶子节点。对 AVL 树的查找来看起来已经很完美了，能不能再优化下？比如，能否把这个节点里存放的 KEY 增加？能否减少树的总层数？那减少纵深只能从横向来想办法，这时候可以考虑用多叉树。
Q4: java构建二叉树算法
//******************************************************************************************************//
//*****本程序包括简单的二叉树类的实现和前序,中序,后序,层次遍历二叉树算法,*******//
//******以及确定二叉树的高度,制定对象在树中的所处层次以及将树中的左右***********//
//******孩子节点对换位置,返回叶子节点个数删除叶子节点,并输出所删除的叶子节点**//
//*******************************CopyRight By phoenix*******************************************//
//************************************Jan 12,2008*************************************************//
//****************************************************************************************************//
public class BinTree {
public final static int MAX=40;
private Object data; //数据元数
private BinTree left,right; //指向左,右孩子结点的链
BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点
int front;//层次遍历时队首
int rear;//层次遍历时队尾
public BinTree()
{
}
public BinTree(Object data)
{ //构造有值结点
this.data = data;
left = right = null;
}
public BinTree(Object data,BinTree left,BinTree right)
{ //构造有值结点
this.data = data;
this.left = left;
this.right = right;
}
public String toString()
{
return data.toString();
}//前序遍历二叉树
public static void preOrder(BinTree parent){
if(parent == null)
return;
System.out.print(parent.data+" ");
preOrder(parent.left);
preOrder(parent.right);
}//中序遍历二叉树
public void inOrder(BinTree parent){
if(parent == null)
return;
inOrder(parent.left);
System.out.print(parent.data+" ");
inOrder(parent.right);
}//后序遍历二叉树
public void postOrder(BinTree parent){
if(parent == null)
return;
postOrder(parent.left);
postOrder(parent.right);
System.out.print(parent.data+" ");
}// 层次遍历二叉树
public void LayerOrder(BinTree parent)
{
elements[0]=parent;
front=0;rear=1;
while(frontrear)
{
try
{
if(elements[front].data!=null)
{
System.out.print(elements[front].data + " ");
if(elements[front].left!=null)
elements[rear++]=elements[front].left;
if(elements[front].right!=null)
elements[rear++]=elements[front].right;
front++;
}
}catch(Exception e){break;}
}
}//返回树的叶节点个数
public int leaves()
{
if(this == null)
return 0;
if(left == nullright == null)
return 1;
return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());
}//结果返回树的高度
public int height()
{
int heightOfTree;
if(this == null)
return -1;
int leftHeight = (left == null ? 0 : left.height());
int rightHeight = (right == null ? 0 : right.height());
heightOfTree = leftHeightrightHeight?rightHeight:leftHeight;
return 1 + heightOfTree;
}
//如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层
public int level(Object object)
{
int levelInTree;
if(this == null)
return -1;
if(object == data)
return 1;//规定根节点为第一层
int leftLevel = (left == null?-1:left.level(object));
int rightLevel = (right == null?-1:right.level(object));
if(leftLevel0rightLevel0)
return -1;
levelInTree = leftLevelrightLevel?rightLevel:leftLevel;
return 1+levelInTree;
}
//将树中的每个节点的孩子对换位置
public void reflect()
{
if(this == null)
return;
if(left != null)
left.reflect();
if(right != null)
right.reflect();
BinTree temp = left;
left = right;
right = temp;
}// 将树中的所有节点移走,并输出移走的节点
public void defoliate()
{
String innerNode = "";
if(this == null)
return;
//若本节点是叶节点，则将其移走
if(left==nullright == null)
{
System.out.print(this + " ");
data = null;
return;
}
//移走左子树若其存在
if(left!=null){
left.defoliate();
left = null;
}
//移走本节点，放在中间表示中跟移走...
innerNode += this + " ";
data = null;
//移走右子树若其存在
if(right!=null){
right.defoliate();
right = null;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinTree e = new BinTree("E");
BinTree g = new BinTree("G");
BinTree h = new BinTree("H");
BinTree i = new BinTree("I");
BinTree d = new BinTree("D",null,g);
BinTree f = new BinTree("F",h,i);
BinTree b = new BinTree("B",d,e);
BinTree c = new BinTree("C",f,null);
BinTree tree = new BinTree("A",b,c);
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
System.out.println("--------------------------------------");
tree.reflect();
System.out.println("交换每个节点的孩子节点后......");
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
}
平衡二叉树java源代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于平衡二叉树建树、平衡二叉树java源代码的信息别忘了在本站进行查找喔。
