好了，代碼如下，自己運行下，看下是否符合你的要求：
成都創(chuàng)新互聯(lián)公司專注于企業(yè)營銷型網站建設、網站重做改版、汕尾網站定制設計、自適應品牌網站建設、H5高端網站建設、商城網站開發(fā)、集團公司官網建設、外貿網站建設、高端網站制作、響應式網頁設計等建站業(yè)務，價格優(yōu)惠性價比高，為汕尾等各大城市提供網站開發(fā)制作服務。
public class Test
{
static Node root;
static class Node
{
Node left;
Node right;
char data;
Node(char data)
{
this.data = data;
}
}
public static void main(String[] args)
{
String content = "welcomeyou";
for(int i=0;icontent.length();i++)
{
root = insert(root, content.charAt(i));
}
System.out.println("先序遍歷結果如下：");
perorder(root);
System.out.println("中序遍歷結果如下：");
inorder(root);
System.out.println("后序遍歷結果如下：");
postorder(root);
}
public static Node insert(Node node, char data)
{
if(node == null)
node = new Node(data);
else
{
if(node.data data)
node.left = insert(node.left,data);
else
node.right = insert(node.right,data);
}
return node;
}
public static void perorder(Node node)
{
if (node == null)
return;
System.out.println(node.data);
if (node.left != null)
perorder(node.left);
if (node.right != null)
perorder(node.right);
}
public static void inorder(Node node)
{
if (node == null)
return;
if (node.left != null)
inorder(node.left);
System.out.println(node.data);
if (node.right != null)
inorder(node.right);
}
public static void postorder(Node node)
{
if (node == null)
return;
if (node.left != null)
postorder(node.left);
if (node.right != null)
postorder(node.right);
System.out.println(node.data);
}
}
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ù)組，構建出一棵多叉樹
// null 值表示一個層次的結束
// "|" 表示一個層次中一個父親節(jié)點的孩子輸入結束
// 如：給定下面的值數(shù)組：
// { "root", null, "left", "right", null }
// 則構建出一個根節(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++;
}
}
// 遞歸調用，打印所有節(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 的孩子，構建節(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ù)據
public void add(int data) {
// 遞歸調用
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ù)據
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;
}
}
在JAVA中實現(xiàn)二叉樹，程序如下 //******************************************************************** //filename: BinaryTreeTest.java //purpose: test a binarytree with java //author: //ver: 0.1 //******************************************************************** public class BinaryTreeTest { public static void main(String args[]) { BinaryTreeTest b= new BinaryTreeTest(); int data[]={12,11,34,45,67,89,56,43,22,98}; BinaryTree root = new BinaryTree(data[0]); System.out.print("二叉樹的中的數(shù)據： "); for ( int i=1;idata.length;i++) { root.insertTree(root,data[i]); System.out.print(data[i-1]+";"); } System.out.println(data[data.length-1]); int key=Integer.parseInt(args[0]); if (b.searchkey(root,key)) { System.out.println("找到了:"+key); } else { System.out.println("沒有找到："+key); } } public boolean searchkey(BinaryTree root, int key) { boolean bl= false ; if (root== null ) { bl= false ; return bl; } else if (root.data==key) { bl= true ; return bl; } else if (key=root.data) { return searchkey(root.rightpoiter,key); } return searchkey(root.leftpoiter,key); } } class BinaryTree { int data; BinaryTree leftpoiter; BinaryTree rightpoiter; BinaryTree( int data) { this .data=data; leftpoiter= null ; rightpoiter= null ; } public void insertTree(BinaryTree root, int data) { if (data=root.data) { if (root.rightpoiter== null ) { root.rightpoiter= new BinaryTree(data); } else { insertTree(root.rightpoiter,data); } } else { if (root.leftpoiter== null ) { root.leftpoiter= new BinaryTree(data); } else { insertTree(root.leftpoiter,data); } } } } //end
/**
* [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();
}
//從中序遍歷中根據后序遍歷查找節(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));
}
}
樹結構如圖:
1
|-------|
2 3
|---| |---|
4 5 6 7
|-| |-|
8 9 A B
二叉樹的相關操作，包括創(chuàng)建，中序、先序、后序（遞歸和非遞歸），其中重點的是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();
//
}
}
重慶分公司
重慶分公司
