首先我想問為什么要用LinkedList 來建立二叉樹呢? LinkedList 是線性表,
創(chuàng)新互聯(lián)建站是一家專注于網(wǎng)站建設、成都網(wǎng)站制作與策劃設計,崇陽網(wǎng)站建設哪家好?創(chuàng)新互聯(lián)建站做網(wǎng)站,專注于網(wǎng)站建設10余年,網(wǎng)設計領(lǐng)域的專業(yè)建站公司;建站業(yè)務涵蓋:崇陽等地區(qū)。崇陽做網(wǎng)站價格咨詢:18980820575
樹是樹形的, 似乎不太合適。
其實也可以用數(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é)點設置左右子樹:
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個元素就是樹根，思路大體是這樣吧。
二叉樹的相關(guān)操作，包括創(chuàng)建，中序、先序、后序（遞歸和非遞歸），碧閉知其中重態(tài)謹點的是java在先序創(chuàng)建二叉樹和后序非遞歸遍歷的的實現(xiàn)悔消。
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 {
private Node root;
public Tree() {
}
public Tree(Node root) {
this.root = root;
}
//創(chuàng)建二叉樹
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);
}
//先序遍歷創(chuàng)建二叉樹
private Node createTree(Node node,Scanner scn) {
String temp = scn.next();
if (temp.trim().equals("#")) {
return null;
} else {
node = new Node((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 node) {
if (node != null) {
inOrderTraverse(node.getLeft());
System.out.println(node.getValue());
inOrderTraverse(node.getRight());
}
}
//中序遍歷(非遞歸)
public void nrInOrderTraverse() {
StackNode stack = new StackNode();
Node 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 node) {
if (node != null) {
System.out.println(node.getValue());
preOrderTraverse(node.getLeft());
preOrderTraverse(node.getRight());
}
}
//先序遍歷（非遞歸）
public void nrPreOrderTraverse() {
StackNode stack = new StackNode();
Node 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 node) {
if (node != null) {
postOrderTraverse(node.getLeft());
postOrderTraverse(node.getRight());
System.out.println(node.getValue());
}
}
//后續(xù)遍歷(非遞歸)
public void nrPostOrderTraverse() {
StackNode stack = new StackNode();
Node node = root;
Node preNode = null;//表示最近一次訪問的節(jié)點
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 node) {
QueueNode queue = new LinkedBlockingQueueNode();
queue.add(node);
while (!queue.isEmpty()) {
Node temp = queue.poll();
if (temp != null) {
System.out.println(temp.getValue());
queue.add(temp.getLeft());
queue.add(temp.getRight());
}
}
}
}
//樹的節(jié)點
class Node {
private Node left;
private Node right;
private T value;
public Node() {
}
public Node(Node left,Node right,T value) {
this.left = left;
this.right = right;
this.value = value;
}
public Node(T value) {
this(null,null,value);
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node 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 tree = new Tree();
tree.buildTree();
System.out.println("中序遍歷");
tree.inOrderTraverse();
tree.nrInOrderTraverse();
System.out.println("后續(xù)遍歷");
//tree.nrPostOrderTraverse();
tree.postOrderTraverse();
tree.nrPostOrderTraverse();
System.out.println("先序遍歷");
tree.preOrderTraverse();
tree.nrPreOrderTraverse();
//
}
}
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);
}
}
輸出結(jié)果：
前序遍歷：
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
重慶分公司
重慶分公司
