首先我想問為什么要用LinkedList 來建立二叉樹呢? LinkedList 是線性表,
創(chuàng)新互聯(lián)公司服務(wù)項目包括茌平網(wǎng)站建設(shè)、茌平網(wǎng)站制作、茌平網(wǎng)頁制作以及茌平網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，茌平網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到茌平省份的部分城市，未來相信會繼續(xù)擴大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！
樹是樹形的, 似乎不太合適。
其實也可以用數(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個元素就是樹根，思路大體是這樣吧。
public class BinaryNode {
Object element;
BinaryNode left;
BinaryNode right;
}
import java.util.*;
public class Queue {
protected LinkedList list;
// Postcondition: this Queue object has been initialized.
public Queue() {
list = new LinkedList();
} // default constructor
// Postcondition: the number of elements in this Queue object has been
// returned.
public int size() {
return list.size();
} // method size
// Postcondition: true has been returned if this Queue object has no
// elements. Otherwise, false has been returned.
public boolean isEmpty() {
return list.isEmpty();
} // method isEmpty
// Postconditon: A copy of element has been inserted at the back of this
// Queue object. The averageTime (n) is constant and
// worstTime (n) is O (n).
public void enqueue(Object element) {
list.addLast(element);
} // method enqueue
// Precondition: this Queue object is not empty. Otherwise,
// NoSuchElementException will be thrown.
// Postcondition: The element that was at the front of this Queue object -
// just before this method was called -- has been removed
// from this Queue object and returned.
public Object dequeue() {
return list.removeFirst();
} // method dequeue
// Precondition: this Queue object is not empty. Otherwise,
// NoSuchElementException will be thrown.
// Postcondition: the element at index 0 in this Queue object has been
// returned.
public Object front() {
return list.getFirst();
} // method front
} // Queue class
import java.io.IOException;
public class BinaryTree {
BinaryNode root;
public BinaryTree() {
super();
// TODO 自動生成構(gòu)造函數(shù)存根
root=this.createPre();
}
public BinaryNode createPre()
//按照先序遍歷的輸入方法，建立二叉樹
{
BinaryNode t=null;
char ch;
try {
ch = (char)System.in.read();
if(ch==' ')
t=null;
else
{
t=new BinaryNode();
t.element=(Object)ch;
t.left=createPre();
t.right=createPre();
}
} catch (IOException e) {
// TODO 自動生成 catch 塊
e.printStackTrace();
}
return t;
}
public void inOrder()
{
this.inOrder(root);
}
public void inOrder(BinaryNode t)
//中序遍歷二叉樹
{
if(t!=null)
{
inOrder(t.left);
System.out.print(t.element);
inOrder(t.right);
}
}
public void postOrder()
{
this.postOrder(root);
}
public void postOrder(BinaryNode t)
//后序遍歷二叉樹
{
if(t!=null)
{
postOrder(t.left);
System.out.print(t.element);
postOrder(t.right);
}
}
public void preOrder()
{
this.preOrder(root);
}
public void preOrder(BinaryNode t)
//前序遍歷二叉樹
{
if(t!=null)
{
System.out.print(t.element);
preOrder(t.left);
preOrder(t.right);
}
}
public void breadthFirst()
{
Queue treeQueue=new Queue();
BinaryNode p;
if(root!=null)
treeQueue.enqueue(root);
while(!treeQueue.isEmpty())
{
System.out.print(((BinaryNode)(treeQueue.front())).element);
p=(BinaryNode)treeQueue.dequeue();
if(p.left!=null)
treeQueue.enqueue(p.left);
if(p.right!=null)
treeQueue.enqueue(p.right);
}
}
}
public class BinaryTreeTest {
/**
* @param args
*/
public static void main(String[] args) {
// TODO 自動生成方法存根
BinaryTree tree = new BinaryTree();
System.out.println("先序遍歷：");
tree.preOrder();
System.out.println();
System.out.println("中序遍歷：");
tree.inOrder();
System.out.println();
System.out.println("后序遍歷：");
tree.postOrder();
System.out.println();
System.out.println("層次遍歷：");
tree.breadthFirst();
System.out.println();
}
}
定義一個結(jié)點類：
public class Node {
private int value;
private Node leftNode;
private Node rightNode;
public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
}
初始化結(jié)點樹：
public void initNodeTree()
{
int nodeNumber;
HashMapString, Integer map = new HashMapString, Integer();
Node nodeTree = new Node();
Scanner reader = new Scanner(System.in);
nodeNumber = reader.nextInt();
for(int i = 0; i nodeNumber; i++) {
int value = reader.nextInt();
String str = reader.next();
map.put(str, value);
}
if (map.containsKey("#")) {
int value = map.get("#");
nodeTree.setValue(value);
setChildNode(map, value, nodeTree);
}
preTraversal(nodeTree);
}
private void setChildNode(HashMapString, Integer map, int nodeValue, Node parentNode) {
int value = 0;
if (map.containsKey("L" + nodeValue)) {
value = map.get("L" + nodeValue);
Node leftNode = new Node();
leftNode.setValue(value);
parentNode.setLeftNode(leftNode);
setChildNode(map, value, leftNode);
}
if (map.containsKey("R" + nodeValue)) {
value = map.get("R" + nodeValue);
Node rightNode = new Node();
rightNode.setValue(value);
parentNode.setRightNode(rightNode);
setChildNode(map, value, rightNode);
}
}
前序遍歷該結(jié)點樹：
public void preTraversal(Node nodeTree) {
if (nodeTree != null) {
System.out.print(nodeTree.getValue() + "\t");
preTraversal(nodeTree.getLeftNode());
preTraversal(nodeTree.getRightNode());
}
}
/**
* [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構(gòu)造二叉樹，可以通過鏈表來構(gòu)造，如下代碼：
public class BinTree {public final static int MAX=40;BinTree []elements = new BinTree[MAX];//層次遍歷時保存各個節(jié)點 int front;//層次遍歷時隊首 int rear;//層次遍歷時隊尾private Object data; //數(shù)據(jù)元數(shù)private BinTree left,right; //指向左,右孩子結(jié)點的鏈public BinTree(){}public BinTree(Object data){ //構(gòu)造有值結(jié)點 this.data = data; left = right = null;}public BinTree(Object data,BinTree left,BinTree right){ //構(gòu)造有值結(jié)點 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é)點個數(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é)點為第一層public int level(Object object){ int levelInTree; if(this == null) return -1; if(object == data) return 1;//規(guī)定根節(jié)點為第一層 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é)點的孩子對換位置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é)點移走,并輸出移走的節(jié)點public void defoliate(){ if(this == null) return; //若本節(jié)點是葉節(jié)點，則將其移走 if(left==nullright == null) { System.out.print(this + " "); data = null; return; } //移走左子樹若其存在 if(left!=null){ left.defoliate(); left = null; } //移走本節(jié)點，放在中間表示中跟移走... 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("前序遍歷二叉樹結(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é)點的孩子節(jié)點后......"); 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());
import java.util.ArrayList;
// 樹的一個節(jié)點
class TreeNode {
Object _value = null; // 他的值
TreeNode _parent = null; // 他的父節(jié)點，根節(jié)點沒有PARENT
ArrayList _childList = new ArrayList(); // 他的孩子節(jié)點
public TreeNode( Object value, TreeNode parent ){
this._parent = parent;
this._value = value;
}
public TreeNode getParent(){
return _parent;
}
public String toString() {
return _value.toString();
}
}
public class Tree {
// 給出寬度優(yōu)先遍歷的值數(shù)組，構(gòu)建出一棵多叉樹
// null 值表示一個層次的結(jié)束
// "|" 表示一個層次中一個父親節(jié)點的孩子輸入結(jié)束
// 如：給定下面的值數(shù)組：
// { "root", null, "left", "right", null }
// 則構(gòu)建出一個根節(jié)點，帶有兩個孩子("left","right")的樹
public Tree( Object[] values ){
// 創(chuàng)建根
_root = new TreeNode( values[0], null );
// 創(chuàng)建下面的子節(jié)點
TreeNode currentParent = _root; // 用于待創(chuàng)建節(jié)點的父親
//TreeNode nextParent = null;
int currentChildIndex = 0; // 表示 currentParent 是他的父親的第幾個兒子
//TreeNode lastNode = null; // 最后一個創(chuàng)建出來的TreeNode，用于找到他的父親
for ( int i = 2; i values.length; i++ ){
// 如果null ,表示下一個節(jié)點的父親是當前節(jié)點的父親的第一個孩子節(jié)點
if ( values[i] == null ){
currentParent = (TreeNode)currentParent._childList.get(0);
currentChildIndex = 0;
continue;
}
// 表示一個父節(jié)點的所有孩子輸入完畢
if ( values[i].equals("|") ){
if ( currentChildIndex+1 currentParent._childList.size() ){
currentChildIndex++;
currentParent = (TreeNode)currentParent._parent._childList.get(currentChildIndex);
}
continue;
}
TreeNode child = createChildNode( currentParent, values[i] );
}
}
TreeNode _root = null;
public TreeNode getRoot(){
return _root;
}
/**
// 按寬度優(yōu)先遍歷，打印出parent子樹所有的節(jié)點
private void printSteps( TreeNode parent, int currentDepth ){
for ( int i = 0; i parent._childList.size(); i++ ){
TreeNode child = (TreeNode)parent._childList.get(i);
System.out.println(currentDepth+":"+child);
}
if ( parent._childList.size() != 0 ) System.out.println(""+null);// 為了避免葉子節(jié)點也會打印null
//打印 parent 同層的節(jié)點的孩子
if ( parent._parent != null ){ // 不是root
int i = 1;
while ( i parent._parent._childList.size() ){// parent 的父親還有孩子
TreeNode current = (TreeNode)parent._parent._childList.get(i);
printSteps( current, currentDepth );
i++;
}
}
// 遞歸調(diào)用，打印所有節(jié)點
for ( int i = 0; i parent._childList.size(); i++ ){
TreeNode child = (TreeNode)parent._childList.get(i);
printSteps( child, currentDepth+1 );
}
}
// 按寬度優(yōu)先遍歷，打印出parent子樹所有的節(jié)點
public void printSteps(){
System.out.println(""+_root);
System.out.println(""+null);
printSteps(_root, 1 );
}**/
// 將給定的值做為 parent 的孩子，構(gòu)建節(jié)點
private TreeNode createChildNode( TreeNode parent, Object value ){
TreeNode child = new TreeNode( value , parent );
parent._childList.add( child );
return child;
}
public static void main(String[] args) {
Tree tree = new Tree( new Object[]{ "root", null,
"left", "right", null,
"l1","l2","l3", "|", "r1","r2",null } );
//tree.printSteps();
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(0) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(1) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(2) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(0) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(1) );
}
}
java：二叉樹添加和查詢方法
package arrays.myArray;
public class BinaryTree {
private Node root;
// 添加數(shù)據(jù)
public void add(int data) {
// 遞歸調(diào)用
if (null == root)
root = new Node(data, null, null);
else
addTree(root, data);
}
private void addTree(Node rootNode, int data) {
// 添加到左邊
if (rootNode.data data) {
if (rootNode.left == null)
rootNode.left = new Node(data, null, null);
else
addTree(rootNode.left, data);
} else {
// 添加到右邊
if (rootNode.right == null)
rootNode.right = new Node(data, null, null);
else
addTree(rootNode.right, data);
}
}
// 查詢數(shù)據(jù)
public void show() {
showTree(root);
}
private void showTree(Node node) {
if (node.left != null) {
showTree(node.left);
}
System.out.println(node.data);
if (node.right != null) {
showTree(node.right);
}
}
}
class Node {
int data;
Node left;
Node right;
public Node(int data, Node left, Node right) {
this.data = data;
this.left = left;
this.right = right;
}
}
重慶分公司
重慶分公司
