平衡二叉树代码java 判断平衡二叉树代码

平衡二叉树的操作（高手进）

以前做的。

成都创新互联专注为客户提供全方位的互联网综合服务，包含不限于成都做网站、成都网站制作、宽甸网络推广、小程序定制开发、宽甸网络营销、宽甸企业策划、宽甸品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；成都创新互联为所有大学生创业者提供宽甸建站搭建服务，24小时服务热线：13518219792，官方网址：www.cdcxhl.com

一、 需求分析

1． 本程序是是利用平衡二叉树实现一个动态查找表，实现动态查找表的三种基本功能：查找、插入和删除。

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{

接受命令（根据提示输入终点城市和起点城市的序号）；

处理命令；

}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． 主程序和其他伪码算法

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

java 构建二叉树

首先我想问为什么要用LinkedList 来建立二叉树呢? LinkedList 是线性表,

树是树形的, 似乎不太合适。

其实也可以用数组完成，而且效率更高.

关键是我觉得你这个输入本身就是一个二叉树啊，

String input = "ABCDE F G";

节点编号从0到8. 层次遍历的话:

对于节点i.

leftChild = input.charAt(2*i+1); //做子树

rightChild = input.charAt(2*i+2);//右子树

如果你要将带有节点信息的树存到LinkedList里面, 先建立一个节点类:

class Node{

public char cValue;

public Node leftChild;

public Node rightChild;

public Node(v){

this.cValue = v;

}

}

然后遍历input,建立各个节点对象.

LinkedList tree = new LinkedList();

for(int i=0;i input.length;i++)

LinkedList.add(new Node(input.charAt(i)));

然后为各个节点设置左右子树:

for(int i=0;iinput.length;i++){

((Node)tree.get(i)).leftChild = (Node)tree.get(2*i+1);

((Node)tree.get(i)).rightChild = (Node)tree.get(2*i+2);

}

这样LinkedList 就存储了整个二叉树. 而第0个元素就是树根，思路大体是这样吧。

java二叉树的顺序表实现

做了很多年的程序员，觉得什么树的设计并不是非常实用。二叉树有顺序存储，当一个insert大量同时顺序自增插入的时候，树就会失去平衡。树的一方为了不让塌陷，会增大树的高度。性能会非常不好。以上是题外话。分析需求在写代码。

import java.util.List;

import java.util.LinkedList;

public class Bintrees {

private int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};

private static ListNode nodeList = null;

private static class Node {

Node leftChild;

Node rightChild;

int data;

Node(int newData) {

leftChild = null;

rightChild = null;

data = newData;

}

}

// 创建二叉树

public void createBintree() {

nodeList = new LinkedListNode();

// 将数组的值转换为node

for (int nodeIndex = 0; nodeIndex array.length; nodeIndex++) {

nodeList.add(new Node(array[nodeIndex]));

}

// 对除最后一个父节点按照父节点和孩子节点的数字关系建立二叉树

for (int parentIndex = 0; parentIndex array.length / 2 - 1; parentIndex++) {

nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex * 2 + 1);

nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex * 2 + 2);

}

// 最后一个父节点

int lastParentIndex = array.length / 2 - 1;

// 左孩子

nodeList.get(lastParentIndex).leftChild = nodeList.get(lastParentIndex * 2 + 1);

// 如果为奇数，建立右孩子

if (array.length % 2 == 1) {

nodeList.get(lastParentIndex).rightChild = nodeList.get(lastParentIndex * 2 + 2);

}

}

// 前序遍历

public static void preOrderTraverse(Node node) {

if (node == null) {

return;

}

System.out.print(node.data + " ");

preOrderTraverse(node.leftChild);

preOrderTraverse(node.rightChild);

}

// 中序遍历

public static void inOrderTraverse(Node node) {

if (node == null) {

return;

}

inOrderTraverse(node.leftChild);

System.out.print(node.data + " ");

inOrderTraverse(node.rightChild);

}

// 后序遍历

public static void postOrderTraverse(Node node) {

if (node == null) {

return;

}

postOrderTraverse(node.leftChild);

postOrderTraverse(node.rightChild);

System.out.print(node.data + " ");

}

public static void main(String[] args) {

Bintrees binTree = new Bintrees();

binTree.createBintree();

Node root = nodeList.get(0);

System.out.println("前序遍历：");

preOrderTraverse(root);

System.out.println();

System.out.println("中序遍历：");

inOrderTraverse(root);

System.out.println();

System.out.println("后序遍历：");

postOrderTraverse(root);

}

}

用JAVA写二叉树

/**

* [Tree2.java] Create on 2008-10-20 下午03:03:24

* Copyright (c) 2008 by iTrusChina.

*/

/**

* @author WangXuanmin

* @version 0.10

*/

public class Tree2Bef {

private StringBuffer bef=new StringBuffer();

//传入中序遍历和后序遍历,返回前序遍历字串

public String getBef(String mid, String beh) {

//若节点存在则向bef中添加该节点,继续查询该节点的左子树和右子树

if (root(mid, beh) != -1) {

int rootindex=root(mid, beh);

char root=mid.charAt(rootindex);

bef.append(root);

System.out.println(bef.toString());

String mleft, mright;

mleft = mid.substring(0,rootindex);

mright = mid.substring(rootindex+1);

getBef(mleft,beh);

getBef(mright,beh);

}

//所有节点查询完毕,返回前序遍历值

return bef.toString();

}

//从中序遍历中根据后序遍历查找节点索引值index

private int root(String mid, String beh) {

char[] midc = mid.toCharArray();

char[] behc = beh.toCharArray();

for (int i = behc.length-1; i -1; i--) {

for (int j = 0; j midc.length; j++) {

if (behc[i] == midc[j])

return j;

}

}

return -1;

}

public static void main(String[] args) {

Tree2Bef tree=new Tree2Bef();

String mid="84925163A7B";

String bef="894526AB731";

System.out.println(tree.getBef(mid,bef));

}

}

树结构如图:

1

|-------|

2 3

|---| |---|

4 5 6 7

|-| |-|

8 9 A B

用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+" ");

}

}

}

用java实现二叉树

我有很多个(假设10万个)数据要保存起来，以后还需要从保存的这些数据中检索是否存在某

个数据，（我想说出二叉树的好处，该怎么说呢？那就是说别人的缺点），假如存在数组中，

那么，碰巧要找的数字位于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();

}

}