二叉樹java

1. 用java怎麼構造一個二叉樹呢

二叉樹的相關操作，包括創建，中序、先序、後序（遞歸和非遞歸），其中重點的是java在先序創建二叉樹和後序非遞歸遍歷的的實現。
package com.algorithm.tree;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

public class Tree<T> {

private Node<T> root;

public Tree() {
}

public Tree(Node<T> root) {
this.root = root;
}

//創建二叉樹
public void buildTree() {

Scanner scn = null;
try {
scn = new Scanner(new File("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
root = createTree(root,scn);
}
//先序遍歷創建二叉樹
private Node<T> createTree(Node<T> node,Scanner scn) {

String temp = scn.next();

if (temp.trim().equals("#")) {
return null;
} else {
node = new Node<T>((T)temp);
node.setLeft(createTree(node.getLeft(), scn));
node.setRight(createTree(node.getRight(), scn));
return node;
}

}

//中序遍歷(遞歸)
public void inOrderTraverse() {
inOrderTraverse(root);
}

public void inOrderTraverse(Node<T> node) {
if (node != null) {
inOrderTraverse(node.getLeft());
System.out.println(node.getValue());
inOrderTraverse(node.getRight());
}
}

//中序遍歷(非遞歸)
public void nrInOrderTraverse() {

Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
System.out.println(node.getValue());
node = node.getRight();

}

}
//先序遍歷(遞歸)
public void preOrderTraverse() {
preOrderTraverse(root);
}

public void preOrderTraverse(Node<T> node) {
if (node != null) {
System.out.println(node.getValue());
preOrderTraverse(node.getLeft());
preOrderTraverse(node.getRight());
}
}

//先序遍歷（非遞歸）
public void nrPreOrderTraverse() {

Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;

while (node != null || !stack.isEmpty()) {

while (node != null) {
System.out.println(node.getValue());
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
node = node.getRight();
}

}

//後序遍歷(遞歸)
public void postOrderTraverse() {
postOrderTraverse(root);
}

public void postOrderTraverse(Node<T> node) {
if (node != null) {
postOrderTraverse(node.getLeft());
postOrderTraverse(node.getRight());
System.out.println(node.getValue());
}
}

//後續遍歷(非遞歸)
public void nrPostOrderTraverse() {

Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
Node<T> preNode = null;//表示最近一次訪問的節點

while (node != null || !stack.isEmpty()) {

while (node != null) {
stack.push(node);
node = node.getLeft();
}

node = stack.peek();

if (node.getRight() == null || node.getRight() == preNode) {
System.out.println(node.getValue());
node = stack.pop();
preNode = node;
node = null;
} else {
node = node.getRight();
}

}

}

//按層次遍歷
public void levelTraverse() {
levelTraverse(root);
}

public void levelTraverse(Node<T> node) {

Queue<Node<T>> queue = new LinkedBlockingQueue<Node<T>>();
queue.add(node);
while (!queue.isEmpty()) {

Node<T> temp = queue.poll();
if (temp != null) {
System.out.println(temp.getValue());
queue.add(temp.getLeft());
queue.add(temp.getRight());
}

}

}

}

//樹的節點

class Node<T> {

private Node<T> left;
private Node<T> right;
private T value;

public Node() {
}
public Node(Node<T> left,Node<T> right,T value) {
this.left = left;
this.right = right;
this.value = value;
}

public Node(T value) {
this(null,null,value);
}
public Node<T> getLeft() {
return left;
}
public void setLeft(Node<T> left) {
this.left = left;
}
public Node<T> getRight() {
return right;
}
public void setRight(Node<T> right) {
this.right = right;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}

}
測試代碼：
package com.algorithm.tree;

public class TreeTest {

/**
* @param args
*/
public static void main(String[] args) {
Tree<Integer> tree = new Tree<Integer>();
tree.buildTree();
System.out.println("中序遍歷");
tree.inOrderTraverse();
tree.nrInOrderTraverse();
System.out.println("後續遍歷");
//tree.nrPostOrderTraverse();
tree.postOrderTraverse();
tree.nrPostOrderTraverse();
System.out.println("先序遍歷");
tree.preOrderTraverse();
tree.nrPreOrderTraverse();

//
}

}

2. 用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(value>this.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;i<data.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;i<data.length;i++)
{
root.store(data[i]);
}
root.find(data[19]);
root.preList();
System.out.println();
root.middleList();
System.out.println();
root.afterList();
}
}

3. 如何用java實現二叉樹

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 List<Node> 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 LinkedList<Node>();

// 將數組的值轉換為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);
}
}

輸出結果：
前序遍歷：
1 2 4 8 9 5 3 6 7
中序遍歷：
8 4 9 2 5 1 6 3 7
後序遍歷：
8 9 4 5 2 6 7 3 1

4. 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) ), )))

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

6. 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個元素就是樹根，思路大體是這樣吧。

7. 二叉樹的java實現與幾種遍歷

二叉樹的定義

二叉樹(binary tree)是結點的有限集合，這個集合或者空，或者由一個根及兩個互不相交的稱為這個根的左子樹或右子樹構成.

從定義可以看出，二叉樹包括：1.空樹 2.只有一個根節點 3.只有左子樹 4.只有右子樹 5.左右子樹都存在 有且僅有這5種表現形式

二叉樹的遍歷分為三種：前序遍歷 中序遍歷 後序遍歷

• 前序遍歷：按照「根左右」,先遍歷根節點，再遍歷左子樹 ，再遍歷右子樹

• 中序遍歷：按照「左根右「,先遍歷左子樹，再遍歷根節點，最後遍歷右子樹

• 後續遍歷：按照「左右根」，先遍歷左子樹，再遍歷右子樹，最後遍歷根節點

其中前，後，中指的是每次遍歷時候的根節點被遍歷的順序

具體實現看下圖：

8. java的二叉樹

你的節點類：TreeNode，裡面有 int data;TreeNode Lchild;TreeNode Rchild;這三個屬性，那麼根據該節點結構可知該二叉樹的存儲結構為：鏈式存儲結構中的二叉鏈表 形式。

9. java中的二叉樹是什麼意思

二叉樹的相關操作，包括創建，中序、先序、後序（遞歸和非遞歸），其中重點的是java在先序創建二叉樹和後序非遞歸遍歷的的實現。

10. 關於java中的二叉樹

感覺你的問題好奇怪

你是怎麼知道node是指向誰的？

既然你知道node指向誰了，那它就可以訪問它裡面的成員變數，leftChild不是它的成員變數嗎？它只要知道它的leftChild存在就行了，leftChild指向誰它不管

////////////////////////////
你的意思是再往下一層？