java構(gòu)建二叉樹算法

//******************************************************************************************************//

為揭陽等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計(jì)制作服務(wù)，及揭陽網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為網(wǎng)站設(shè)計(jì)制作、成都做網(wǎng)站、揭陽網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會得到認(rèn)可，從而選擇與我們長期合作。這樣，我們也可以走得更遠(yuǎn)！

//*****本程序包括簡單的二叉樹類的實(shí)現(xiàn)和前序,中序,后序,層次遍歷二叉樹算法,*******//

//******以及確定二叉樹的高度,制定對象在樹中的所處層次以及將樹中的左右***********//

//******孩子節(jié)點(diǎn)對換位置,返回葉子節(jié)點(diǎn)個數(shù)刪除葉子節(jié)點(diǎn),并輸出所刪除的葉子節(jié)點(diǎn)**//

//*******************************CopyRight By phoenix*******************************************//

//************************************Jan 12,2008*************************************************//

//****************************************************************************************************//

public class BinTree {

public final static int MAX=40;

private Object data; //數(shù)據(jù)元數(shù)

private BinTree left,right; //指向左,右孩子結(jié)點(diǎn)的鏈

BinTree []elements = new BinTree[MAX];//層次遍歷時保存各個節(jié)點(diǎn)

int front;//層次遍歷時隊(duì)首

int rear;//層次遍歷時隊(duì)尾

public BinTree()

{

}

public BinTree(Object data)

{ //構(gòu)造有值結(jié)點(diǎn)

this.data = data;

left = right = null;

}

public BinTree(Object data,BinTree left,BinTree right)

{ //構(gòu)造有值結(jié)點(diǎn)

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

}

}//返回樹的葉節(jié)點(diǎn)個數(shù)

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

}//結(jié)果返回樹的高度

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;

}

//如果對象不在樹中,結(jié)果返回-1;否則結(jié)果返回該對象在樹中所處的層次,規(guī)定根節(jié)點(diǎn)為第一層

public int level(Object object)

{

int levelInTree;

if(this == null)

return -1;

if(object == data)

return 1;//規(guī)定根節(jié)點(diǎn)為第一層

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;

}

//將樹中的每個節(jié)點(diǎn)的孩子對換位置

public void reflect()

{

if(this == null)

return;

if(left != null)

left.reflect();

if(right != null)

right.reflect();

BinTree temp = left;

left = right;

right = temp;

}// 將樹中的所有節(jié)點(diǎn)移走,并輸出移走的節(jié)點(diǎn)

public void defoliate()

{

String innerNode = "";

if(this == null)

return;

//若本節(jié)點(diǎn)是葉節(jié)點(diǎn)，則將其移走

if(left==nullright == null)

{

System.out.print(this + " ");

data = null;

return;

}

//移走左子樹若其存在

if(left!=null){

left.defoliate();

left = null;

}

//移走本節(jié)點(diǎn)，放在中間表示中跟移走...

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("前序遍歷二叉樹結(jié)果: ");

tree.preOrder(tree);

System.out.println();

System.out.println("中序遍歷二叉樹結(jié)果: ");

tree.inOrder(tree);

System.out.println();

System.out.println("后序遍歷二叉樹結(jié)果: ");

tree.postOrder(tree);

System.out.println();

System.out.println("層次遍歷二叉樹結(jié)果: ");

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("交換每個節(jié)點(diǎn)的孩子節(jié)點(diǎn)后......");

System.out.println("前序遍歷二叉樹結(jié)果: ");

tree.preOrder(tree);

System.out.println();

System.out.println("中序遍歷二叉樹結(jié)果: ");

tree.inOrder(tree);

System.out.println();

System.out.println("后序遍歷二叉樹結(jié)果: ");

tree.postOrder(tree);

System.out.println();

System.out.println("層次遍歷二叉樹結(jié)果: ");

tree.LayerOrder(tree);

System.out.println();

System.out.println("F所在的層次: "+tree.level("F"));

System.out.println("這棵二叉樹的高度: "+tree.height());

}

用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é)點(diǎn)存在則向bef中添加該節(jié)點(diǎn),繼續(xù)查詢該節(jié)點(diǎn)的左子樹和右子樹

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é)點(diǎn)查詢完畢,返回前序遍歷值

return bef.toString();

}

//從中序遍歷中根據(jù)后序遍歷查找節(jié)點(diǎn)索引值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如何創(chuàng)建一顆二叉樹

計(jì)算機(jī)科學(xué)中，二叉樹是每個結(jié)點(diǎn)最多有兩個子樹的有序樹。通常子樹的根被稱作“左子樹”（left

subtree）和“右子樹”（right

subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。

二叉樹的每個結(jié)點(diǎn)至多只有二棵子樹(不存在度大于2的結(jié)點(diǎn))，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的

i

-1次方個結(jié)點(diǎn)；深度為k的二叉樹至多有2^(k)

-1個結(jié)點(diǎn)；對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)(即葉子結(jié)點(diǎn)數(shù))為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0

=

n2

+

1。

樹是由一個或多個結(jié)點(diǎn)組成的有限集合，其中：

⒈必有一個特定的稱為根(ROOT)的結(jié)點(diǎn)；

二叉樹

⒉剩下的結(jié)點(diǎn)被分成n=0個互不相交的集合T1、T2、......Tn，而且，

這些集合的每一個又都是樹。樹T1、T2、......Tn被稱作根的子樹(Subtree)。

樹的遞歸定義如下：（1）至少有一個結(jié)點(diǎn)（稱為根）（2）其它是互不相交的子樹

1.樹的度——也即是寬度，簡單地說，就是結(jié)點(diǎn)的分支數(shù)。以組成該樹各結(jié)點(diǎn)中最大的度作為該樹的度，如上圖的樹，其度為2;樹中度為零的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。樹中度不為零的結(jié)點(diǎn)稱為分枝結(jié)點(diǎn)或非終端結(jié)點(diǎn)。除根結(jié)點(diǎn)外的分枝結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)。

2.樹的深度——組成該樹各結(jié)點(diǎn)的最大層次。

3.森林——指若干棵互不相交的樹的集合，如上圖，去掉根結(jié)點(diǎn)A，其原來的二棵子樹T1、T2、T3的集合{T1,T2,T3}就為森林；

4.有序樹——指樹中同層結(jié)點(diǎn)從左到右有次序排列，它們之間的次序不能互換，這樣的樹稱為有序樹，否則稱為無序樹。

樹的表示

樹的表示方法有許多，常用的方法是用括號：先將根結(jié)點(diǎn)放入一對圓括號中，然后把它的子樹由左至右的順序放入括號中，而對子樹也采用同樣的方法處理；同層子樹與它的根結(jié)點(diǎn)用圓括號括起來，同層子樹之間用逗號隔開，最后用閉括號括起來。如右圖可寫成如下形式：

二叉樹

(a(

b(d,e),

c(

f(

,g(h,i)

),

)))

java 構(gòu)建二叉樹

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

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

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

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

String input = "ABCDE F G";

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

對于節(jié)點(diǎn)i.

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

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

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

class Node{

public char cValue;

public Node leftChild;

public Node rightChild;

public Node(v){

this.cValue = v;

}

}

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

LinkedList tree = new LinkedList();

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

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

然后為各個節(jié)點(diǎn)設(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代碼,java建立二叉樹的代碼
本文路徑：http://chinadenli.net/article30/dsgdjpo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供動態(tài)網(wǎng)站、外貿(mào)建站、網(wǎng)站維護(hù)、ChatGPT、關(guān)鍵詞優(yōu)化、企業(yè)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)