㈠ 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二叉樹的順序表實現
做了很多年的程序員，覺得什麼樹的設計並不是非常實用。二叉樹有順序存儲，當一個insert大量同時順序自增插入的時候，樹就會失去平衡。樹的一方為了不讓塌陷，會增大樹的高度。性能會非常不好。以上是題外話。分析需求在寫代碼。
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);
}
}
㈢ 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實現樹形結構啊
定義一個簡單的菜單類 這里是簡單的示例 你可以自行擴展package entity;import java.util.ArrayList;
import java.util.List;/**
* 菜單類
* @author Administrator
*
*/
public class Menu {
/**
* 菜單標題
*/
private String title;
/**
* 子菜單的集合
*/
private List<Menu> childs;
/**
* 父菜單
*/
private Menu parent;
/**
* 構造函數 初始化標題和子菜單集合
*/
public Menu(String title) {
this();
this.title=title;
}
/**
* 構造函數 創建一個虛擬的父菜單(零級菜單) 所有的一級菜單都歸屬於一個虛擬的零級菜單
*
*/
public Menu() {
this.childs = new ArrayList<Menu>();
}
/**
* 獲取子菜單
* @return
*/
public List<Menu> getChilds() {
return childs;
}
/**
* 獲取標題
* @return
*/
public String getTitle() {
return title;
}
/**
* 獲取父菜單
* @return
*/
public Menu getParent() {
return parent;
}
/**
* 添加子菜單並返回該子菜單對象
* @param child
* @return
*/
public Menu addChild(Menu child){
this.childs.add(child);
return child;
}
/**
* 設置父菜單
* @param parent
*/
public void setParent(Menu parent) {
this.parent = parent;
}
/**
* 設置標題
* @param title
*/
public void setTitle(String title) {
this.title = title;
}
} 測試package entity;
/**
* 測試類
* @author Administrator
*
*/
public class Test { /**
* @param args
*/
public static void main(String[] args) {
/**
* 創建一個虛擬的父菜單 用於存放一級菜單 menu01 和 menu02
*/
Menu root = new Menu();
/**
* 創建兩個一級菜單
*/
Menu menu01 = new Menu("一級菜單01");
Menu menu02 = new Menu("一級菜單02");
/**
* 加入虛擬菜單
*/
root.addChild(menu01);
root.addChild(menu02);
/**
* 為兩個一級菜單分別添加兩個子菜單 並返回該子菜單 需要進一步處理的時候 才接收返回的對象 否則只要調用方法
*/
Menu menu0101 = menu01.addChild(new Menu("二級菜單0101"));
menu01.addChild(new Menu("二級菜單0102"));
menu02.addChild(new Menu("二級菜單0201"));
Menu menu0202 = menu02.addChild(new Menu("二級菜單0202"));
/**
* 添加三級菜單
*/
menu0101.addChild(new Menu("三級菜單010101"));
menu0202.addChild(new Menu("三級菜單020201"));
/**
* 列印樹形結構
*/
showMenu(root);
} /**
* 遞歸遍歷某個菜單下的菜單樹
*
* @param menu
* 根菜單
*/
private static void showMenu(Menu menu) {
for (Menu child : menu.getChilds()) {
showMenu(child, 0);
}
} private static void showMenu(Menu menu, int tabNum) {
for (int i = 0; i < tabNum; i++)
System.out.print("\t");
System.out.println(menu.getTitle());
for (Menu child : menu.getChilds())
// 遞歸調用
showMenu(child, tabNum + 1);
}}
控制台輸出結果 一級菜單01 二級菜單0101
三級菜單010101
二級菜單0102一級菜單02
二級菜單0201
二級菜單0202
三級菜單020201
㈤ 用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();
}
}