平衡二叉樹的操作（高手進(jìn)）

以前做的。

成都創(chuàng)新互聯(lián)專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都做網(wǎng)站、成都網(wǎng)站制作、寬甸網(wǎng)絡(luò)推廣、小程序定制開發(fā)、寬甸網(wǎng)絡(luò)營銷、寬甸企業(yè)策劃、寬甸品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們最大的嘉獎；成都創(chuàng)新互聯(lián)為所有大學(xué)生創(chuàng)業(yè)者提供寬甸建站搭建服務(wù)，24小時服務(wù)熱線：13518219792，官方網(wǎng)址：www.cdcxhl.com

一、 需求分析

1． 本程序是是利用平衡二叉樹實現(xiàn)一個動態(tài)查找表，實現(xiàn)動態(tài)查找表的三種基本功能：查找、插入和刪除。

2． 初始，平衡二叉樹為空樹，可以按先序輸入平衡二叉樹，以輸入0結(jié)束，中間以回車隔開，創(chuàng)建好二叉樹后，可以對其查找，再對其插入，輸入0結(jié)束插入，再可以對其刪除，輸入0結(jié)束，每次插入或刪除一個結(jié)點后，更新平衡二叉樹的顯示。

3． 本程序以用戶和計算機(jī)的對話方式執(zhí)行，根據(jù)計算機(jī)終端顯示：“提示信息”下，用戶可由鍵盤輸入要執(zhí)行的操作。

4． 測試數(shù)據(jù)（附后）

二、 概要設(shè)計

1． 抽象數(shù)據(jù)類型動態(tài)查找表的定義如下：

ADT DynamicSearchTable{

數(shù)據(jù)結(jié)構(gòu)D：D是具有相同特性的數(shù)據(jù)元素的集合。各個數(shù)據(jù)元素含有類型相同，可惟一標(biāo)識數(shù)據(jù)元素的關(guān)鍵字。

數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個集合。

基本操作P：

InitDSTable(DT);

操作結(jié)果：構(gòu)造一個空的動態(tài)查找表DT。

DestroyDSTable(DT);

初試條件：動態(tài)查找表DT存在。

操作結(jié)果: 銷毀動態(tài)查找表DT。

SearchDSTable(DT,key);

初試條件：動態(tài)查找表DT存在，key為和關(guān)鍵字類型相同的給定值。

操作結(jié)果: 若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或表中的位置，否則為“空”。

InsertDSTable(DT,e);

初試條件：動態(tài)查找表DT存在，e為待插入的數(shù)據(jù)元素。

操作結(jié)果: 若DT中不存在其關(guān)鍵字等于e. key的數(shù)據(jù)元素，則插入e到DT。

DeleteDSTable(DT,key);

初試條件：動態(tài)查找表DT存在，key為和關(guān)鍵字類型相同的給定值。

操作結(jié)果: 若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除之。

TraverseDSTable(DT,Visit());

初試條件：動態(tài)查找表DT存在，Visit()是結(jié)點操作的應(yīng)用函數(shù)。

操作結(jié)果: 按某種次序?qū)T的每個結(jié)點調(diào)用函數(shù)Visit()一次且至多

一次。一但Visit()失敗，則操作失敗。

}ADT DynamicSearchTable

2． 本程序包含兩個模塊：

Void main(){

Do{

接受命令（根據(jù)提示輸入終點城市和起點城市的序號）；

處理命令；

}while(“命令”=“退出”)；

}

3．本程序只有兩個模塊，調(diào)用關(guān)系簡單

主程序模塊

平衡二叉樹的模塊

三、 詳細(xì)設(shè)計

1． 根據(jù)題目要求和查找的基本特點，其結(jié)點類型

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)；

////////在平衡二叉樹中插入結(jié)點。

int FindAVL(bstree p,int e)；

////////查找平衡二叉樹中是否有結(jié)點e。

bstree DeleteAVL(bstree T,int e)

////////刪除平衡平衡二叉樹的結(jié)點e，并保持平衡二叉樹的性質(zhì)。

int Preordertraverse(bstree T)

////////按先序遍歷平衡二叉樹。

/------------------------************平衡二叉樹的操作的詳細(xì)算法

bstree InsertAVL(bstree T, int e)

{

bstree p;

//插入新結(jié)點，樹長高置taller為TRUE

if(!T) {

T=(bstree)malloc(sizeof(BSTnode));

T-data=e;

T-lchild=T-rchild=NULL;

T-bf=EH;

taller=TRUE;

}

else {

//樹中存在和e有相同關(guān)鍵字的結(jié)點則不再插入

if(e==T-data){

taller=FALSE;

return NULL;

}

//值小于則繼續(xù)在樹的左子樹中搜索

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: //原本左子樹和右子樹同高，現(xiàn)因左子樹爭高而使樹增高

T-bf=LH;

taller=TRUE;

break;

case RH: //原本右子樹比左子樹高，現(xiàn)在左右子樹等高

T-bf=EH;

taller=FALSE;

break;

}///////switch(T-bf)

}///////if(taller)

}/////if(p)

}///////if(e T-data)

//繼續(xù)在*T的右子樹中搜索

else{

//插入到右子樹且使右子樹長高

p=InsertAVL(T-rchild,e);

if (p){

T-rchild=p;

if(taller) {

switch(T-bf){ //檢查*T的平衡度

case LH: //原本左子樹比右子樹高，現(xiàn)在左右子樹等高

T-bf=EH;

taller=FALSE;

break;

case EH: //原本左子樹和右子樹同高，現(xiàn)因右子樹增高而使樹增高

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;/////標(biāo)記

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)

}////////在右子數(shù)上尋找完

}////////在左右子上完

}///////////刪除完

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("有要查找的節(jié)點\n");

else printf("無要查找的節(jié)點\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的左子樹根結(jié)點

switch(lc-bf) { //檢查*T的左子樹平衡度，并做相應(yīng)的平衡處理

case LH: //新結(jié)點插入在*T的左孩子的左子樹上，要做單右旋處理

T-bf=lc-bf=EH;

T=R_Rotate(T);

break;

case RH: //新結(jié)點插入在*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的右子樹根結(jié)點

switch(rc-bf) { //檢查*T的右子樹平衡度，并做相應(yīng)的平衡處理

case RH: //新結(jié)點插入在*T的右孩子的右子樹上，要做單右旋處理

T-bf=rc-bf=EH;

T=L_Rotate(T);

break;

case LH: //新結(jié)點插入在*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){

//刪除結(jié)點

bstree p,q;

e=0;

p=T;

if(!T-rchild) {//右子數(shù)為空需要重接它的左子數(shù)

T=T-lchild;

free(p);

shorter=true;

}

else if(!T-lchild) {//重接它的右子數(shù)

T=T-rchild;

free(p);

shorter=true;

}

else{ //左右子數(shù)均不空

q=T-lchild;

while(q-rchild!=NULL){//轉(zhuǎn)左，然后向右到盡頭

q=q-rchild;

}

e=q-data;

}

return e;

}

void Delete_Rightbalance(bstree T){

///////////刪除在左子樹上的，相當(dāng)于插入在右子樹

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:///////刪除在左子樹，相當(dāng)于插入在右子樹，左單旋

T-rchild=rc-lchild;

rc-lchild=T;

rc-bf=LH;

T-bf=RH;

T=rc;

shorter=EH;break;

case RH:///////刪除在左子樹，相當(dāng)于插入在右子樹，左單旋

T-rchild=rc-lchild;

rc-lchild=T;

rc-bf=T-bf=EH;

T=rc;

shorter=true;break;

}

}

void Delete_Leftbalance(bstree T)/////刪除右子樹上的，相當(dāng)于插入在左子樹上

{

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． 函數(shù)的調(diào)用關(guān)系圖

Main

InsertAVL Preordertraverse FindAVL DeleteAVL

四、 調(diào)試分析

1． 在開始對平衡二叉樹的插入后，再做平衡處理時，特別是在做雙向旋轉(zhuǎn)平衡處理后的更新時，費了一些時間；

2． 在做平衡二叉樹的刪除時，當(dāng)刪除結(jié)點左右孩子均在時，開始直接用左子樹的最大數(shù)代替，然后直接刪除結(jié)點，結(jié)果導(dǎo)致刪除了將要刪除的結(jié)點及其孩子均刪除了，后來將要刪除的結(jié)點用左子樹的最大樹代替后，對左子樹的最大結(jié)點做好標(biāo)記，然后再做對其做刪除處理。

3． 本程序算法基本簡單，沒有多大困難，就是在分析做雙旋平衡處理的更新時，開始思路有些混亂，后來就好了；

五、 用戶手冊

1. 本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為Balanced Tree.exe。

2. 進(jìn)入演示程序后，按廣度遍歷輸入平衡二叉樹，中間以回車鍵隔開，輸入0為結(jié)束；再輸入要插入的結(jié)點，輸入0結(jié)束，再輸入要查找的結(jié)點，最后可以輸入要刪除的結(jié)點，輸入0結(jié)束

六、 測試結(jié)果

先按廣度遍歷創(chuàng)建平衡二叉樹（亦可一個一個的插入二叉樹的結(jié)點）（50 20 60 10 30 55 70 5 15 25 58 90） ，輸入0結(jié)束，然后可插入結(jié)點（39），其會顯示插入后的二叉樹，輸入0，不再插入；輸入要查找結(jié)點（6），輸入要刪除的結(jié)點（20），其顯示如下：

七、 附錄

Balance Tree.cpp

java 構(gòu)建二叉樹

首先我想問為什么要用LinkedList 來建立二叉樹呢? LinkedList 是線性表,

樹是樹形的, 似乎不太合適。

其實也可以用數(shù)組完成，而且效率更高.

關(guān)鍵是我覺得你這個輸入本身就是一個二叉樹啊，

String input = "ABCDE F G";

節(jié)點編號從0到8. 層次遍歷的話:

對于節(jié)點i.

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

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

如果你要將帶有節(jié)點信息的樹存到LinkedList里面, 先建立一個節(jié)點類:

class Node{

public char cValue;

public Node leftChild;

public Node rightChild;

public Node(v){

this.cValue = v;

}

}

然后遍歷input,建立各個節(jié)點對象.

LinkedList tree = new LinkedList();

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

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

然后為各個節(jié)點設(shè)置左右子樹:

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二叉樹的順序表實現(xiàn)

做了很多年的程序員，覺得什么樹的設(shè)計并不是非常實用。二叉樹有順序存儲，當(dāng)一個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;

}

}

// 創(chuàng)建二叉樹

public void createBintree() {

nodeList = new LinkedListNode();

// 將數(shù)組的值轉(zhuǎn)換為node

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

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

}

// 對除最后一個父節(jié)點按照父節(jié)點和孩子節(jié)點的數(shù)字關(guān)系建立二叉樹

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);

}

// 最后一個父節(jié)點

int lastParentIndex = array.length / 2 - 1;

// 左孩子

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

// 如果為奇數(shù)，建立右孩子

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) {

//若節(jié)點存在則向bef中添加該節(jié)點,繼續(xù)查詢該節(jié)點的左子樹和右子樹

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);

}

//所有節(jié)點查詢完畢,返回前序遍歷值

return bef.toString();

}

//從中序遍歷中根據(jù)后序遍歷查找節(jié)點索引值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));

}

}

樹結(jié)構(gòu)如圖:

1

|-------|

2 3

|---| |---|

4 5 6 7

|-| |-|

8 9 A B

用Java怎么實現(xiàn)平衡樹動態(tài)演示

public?class?treenode1?{?????????//二叉樹的結(jié)點類

public?string?data;??????????//數(shù)據(jù)元數(shù)

public?treenode1?left,right;?//指向左,右孩子結(jié)點的鏈

public?treenode1(){

this("?");

}

public?treenode1(string?d){??//構(gòu)造有值結(jié)點

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實現(xiàn)二叉樹

我有很多個(假設(shè)10萬個)數(shù)據(jù)要保存起來，以后還需要從保存的這些數(shù)據(jù)中檢索是否存在某

個數(shù)據(jù)，（我想說出二叉樹的好處，該怎么說呢？那就是說別人的缺點），假如存在數(shù)組中，

那么，碰巧要找的數(shù)字位于99999那個地方，那查找的速度將很慢，因為要從第1個依次往

后取，取出來后進(jìn)行比較。平衡二叉樹（構(gòu)建平衡二叉樹需要先排序，我們這里就不作考慮

了）可以很好地解決這個問題，但二叉樹的遍歷（前序，中序，后序）效率要比數(shù)組低很多，

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();

}

}