java二叉樹的建立二叉樹
『壹』 java實現二叉樹的問題
/**
* 二叉樹測試二叉樹順序存儲在treeLine中，遞歸前序創建二叉樹。另外還有能
* 夠前序、中序、後序、按層遍歷二叉樹的方法以及一個返回遍歷結果asString的
* 方法。
*/
public class BitTree {
public static Node2 root;
public static String asString;
//事先存入的數組,符號#表示二叉樹結束。
public static final char[] treeLine = {'a','b','c','d','e','f','g',' ',' ','j',' ',' ','i','#'};
//用於標志二叉樹節點在數組中的存儲位置，以便在創建二叉樹時能夠找到節點對應的數據。
static int index;
//構造函數
public BitTree() {
System.out.print("測試二叉樹的順序表示為：");
System.out.println(treeLine);
this.index = 0;
root = this.setup(root);
}
//創建二叉樹的遞歸程序
private Node2 setup(Node2 current) {
if (index >= treeLine.length) return current;
if (treeLine[index] == '#') return current;
if (treeLine[index] == ' ') return current;
current = new Node2(treeLine[index]);
index = index * 2 + 1;
current.left = setup(current.left);
index ++;
current.right = setup(current.right);
index = index / 2 - 1;
return current;
}
//二叉樹是否為空。
public boolean isEmpty() {
if (root == null) return true;
return false;
}
//返回遍歷二叉樹所得到的字元串。
public String toString(int type) {
if (type == 0) {
asString = "前序遍歷：\t";
this.front(root);
}
if (type == 1) {
asString = "中序遍歷：\t";
this.middle(root);
}
if (type == 2) {
asString = "後序遍歷：\t";
this.rear(root);
}
if (type == 3) {
asString = "按層遍歷：\t";
this.level(root);
}
return asString;
}
//前序遍歷二叉樹的循環演算法，每到一個結點先輸出，再壓棧，然後訪問它的左子樹，
//出棧，訪問其右子樹，然後該次循環結束。
private void front(Node2 current) {
StackL stack = new StackL((Object)current);
do {
if (current == null) {
current = (Node2)stack.pop();
current = current.right;
} else {
asString += current.ch;
current = current.left;
}
if (!(current == null)) stack.push((Object)current);
} while (!(stack.isEmpty()));
}
//中序遍歷二叉樹
private void middle(Node2 current) {
if (current == null) return;
middle(current.left);
asString += current.ch;
middle(current.right);
}
//後序遍歷二叉樹的遞歸演算法
private void rear(Node2 current) {
if (current == null) return;
rear(current.left);
rear(current.right);
asString += current.ch;
}
}
/**
* 二叉樹所使用的節點類。包括一個值域兩個鏈域
*/
public class Node2 {
char ch;
Node2 left;
Node2 right;
//構造函數
public Node2(char c) {
this.ch = c;
this.left = null;
this.right = null;
}
//設置節點的值
public void setChar(char c) {
this.ch = c;
}
//返回節點的值
public char getChar() {
return ch;
}
//設置節點的左孩子
public void setLeft(Node2 left) {
this.left = left;
}
//設置節點的右孩子
public void setRight (Node2 right) {
this.right = right;
}
//如果是葉節點返回true
public boolean isLeaf() {
if ((this.left == null) && (this.right == null)) return true;
return false;
}
}
一個作業題，裡面有你要的東西。
主函數自己寫吧。當然其它地方也有要改的。
『貳』 用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 由字元串構成的二叉樹
java構造二叉樹，可以通過鏈表來構造，如下代碼：
public class BinTree {public final static int MAX=40;BinTree []elements = new BinTree[MAX];//層次遍歷時保存各個節點 int front;//層次遍歷時隊首 int rear;//層次遍歷時隊尾private Object data; //數據元數private BinTree left,right; //指向左,右孩子結點的鏈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(front<rear) { 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 == null&&right == 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 = leftHeight<rightHeight?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(leftLevel<0&&rightLevel<0) return -1; levelInTree = leftLevel<rightLevel?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(){ if(this == null) return; //若本節點是葉節點，則將其移走 if(left==null&&right == null) { System.out.print(this + " "); data = null; return; } //移走左子樹若其存在 if(left!=null){ left.defoliate(); left = null; } //移走本節點，放在中間表示中跟移走... String 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 構建二叉樹
首先我想問為什麼要用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;i<input.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如何創建一顆二叉樹
計算機科學中，二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。
二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的 i -1次方個結點；深度為k的二叉樹至多有2^(k) -1個結點；對任何一棵二叉樹T，如果其終端結點數(即葉子結點數)為n0，度為2的結點數為n2，則n0 = n2 + 1。
樹是由一個或多個結點組成的有限集合，其中：
⒈必有一個特定的稱為根(ROOT)的結點；
二叉樹
⒉剩下的結點被分成n>=0個互不相交的集合T1、T2、......Tn，而且， 這些集合的每一個又都是樹。樹T1、T2、......Tn被稱作根的子樹(Subtree)。
樹的遞歸定義如下：（1）至少有一個結點（稱為根）（2）其它是互不相交的子樹
1.樹的度——也即是寬度，簡單地說，就是結點的分支數。以組成該樹各結點中最大的度作為該樹的度，如上圖的樹，其度為2;樹中度為零的結點稱為葉結點或終端結點。樹中度不為零的結點稱為分枝結點或非終端結點。除根結點外的分枝結點統稱為內部結點。
2.樹的深度——組成該樹各結點的最大層次。
3.森林——指若干棵互不相交的樹的集合，如上圖，去掉根結點A，其原來的二棵子樹T1、T2、T3的集合{T1,T2,T3}就為森林；
4.有序樹——指樹中同層結點從左到右有次序排列，它們之間的次序不能互換，這樣的樹稱為有序樹，否則稱為無序樹。
樹的表示
樹的表示方法有許多，常用的方法是用括弧：先將根結點放入一對圓括弧中，然後把它的子樹由左至右的順序放入括弧中，而對子樹也採用同樣的方法處理；同層子樹與它的根結點用圓括弧括起來，同層子樹之間用逗號隔開，最後用閉括弧括起來。如右圖可寫成如下形式：
二叉樹
(a( b(d,e), c( f( ,g(h,i) ), )))
『陸』 二叉樹的java實現與幾種遍歷
二叉樹的定義
二叉樹(binary tree)是結點的有限集合，這個集合或者空，或者由一個根及兩個互不相交的稱為這個根的左子樹或右子樹構成.
從定義可以看出，二叉樹包括：1.空樹 2.只有一個根節點 3.只有左子樹 4.只有右子樹 5.左右子樹都存在 有且僅有這5種表現形式
二叉樹的遍歷分為三種：前序遍歷 中序遍歷 後序遍歷
前序遍歷：按照「根左右」,先遍歷根節點，再遍歷左子樹 ，再遍歷右子樹
中序遍歷：按照「左根右「,先遍歷左子樹，再遍歷根節點，最後遍歷右子樹
後續遍歷：按照「左右根」，先遍歷左子樹，再遍歷右子樹，最後遍歷根節點
其中前，後，中指的是每次遍歷時候的根節點被遍歷的順序
具體實現看下圖：
『柒』 如何用Java的方式設計一個後序線索二叉樹的方法
在Java中，你可以定義一哪激弊個類來表示後序線索二叉樹，其中包含有頭節點、尾節點和當前節點指針。你可以使用遞歸或迭代方法遍歷整棵樹，並創建線索，即存儲前驅和後繼節點的指針。當訪問到葉子節點時，需要將尾節點的指針指向它，尾節點鉛隱的指李族針則指向頭節點
// 定
『捌』 用java怎麼構造一個二叉樹
定義一個結點類：x0dx0apublic class Node {x0dx0a private int value;x0dx0a private Node leftNode;x0dx0a private Node rightNode;x0dx0a x0dx0a public Node getRightNode() {x0dx0a return rightNode;x0dx0a }x0dx0a public void setRightNode(Node rightNode) {x0dx0a this.rightNode = rightNode;x0dx0a }x0dx0a public int getValue() {x0dx0a return value;x0dx0a }x0dx0a public void setValue(int value) {x0dx0a this.value = value;x0dx0a }x0dx0a public Node getLeftNode() {x0dx0a return leftNode;x0dx0a }x0dx0a public void setLeftNode(Node leftNode) {x0dx0a this.leftNode = leftNode;x0dx0a }x0dx0a x0dx0a}x0dx0a x0dx0a初始化結點樹：x0dx0apublic void initNodeTree()x0dx0a {x0dx0a int nodeNumber;x0dx0a HashMap