在JAVA中實(shí)現(xiàn)二叉樹，程序如下（轉(zhuǎn)載）
我們提供的服務(wù)有：網(wǎng)站設(shè)計(jì)制作、網(wǎng)站設(shè)計(jì)、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、駐馬店ssl等。為成百上千企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的駐馬店網(wǎng)站制作公司
//********************************************************************
//filename: BinaryTreeTest.java
//purpose: test a binarytree with java
//date: 2002/12/18
//author: flyfan
//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ù)據(jù)： ");
for(int i=1;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
二叉樹的定義
二叉樹(binary tree)是結(jié)點(diǎn)的有限集合，這個集合或者空，或者由一個根及兩個互不相交的稱為這個根的左子樹或右子樹構(gòu)成.
從定義可以看出，二叉樹包括：1.空樹 2.只有一個根節(jié)點(diǎn) 3.只有左子樹 ? 4.只有右子樹 ?5.左右子樹都存在 ? ?有且僅有這5種表現(xiàn)形式
二叉樹的遍歷分為三種：前序遍歷 中序遍歷 后序遍歷
前序遍歷：按照“根左右”,先遍歷根節(jié)點(diǎn)，再遍歷左子樹 ，再遍歷右子樹
中序遍歷：按照“左根右“,先遍歷左子樹，再遍歷根節(jié)點(diǎn)，最后遍歷右子樹
后續(xù)遍歷：按照“左右根”，先遍歷左子樹，再遍歷右子樹，最后遍歷根節(jié)點(diǎn)
其中前，后，中指的是每次遍歷時候的根節(jié)點(diǎn)被遍歷的順序
具體實(shí)現(xiàn)看下圖：
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();
}
}
import java.util.ArrayList;
// 樹的一個節(jié)點(diǎn)
class TreeNode {
Object _value = null; // 他的值
TreeNode _parent = null; // 他的父節(jié)點(diǎn)，根節(jié)點(diǎn)沒有PARENT
ArrayList _childList = new ArrayList(); // 他的孩子節(jié)點(diǎn)
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é)點(diǎn)的孩子輸入結(jié)束
// 如：給定下面的值數(shù)組：
// { "root", null, "left", "right", null }
// 則構(gòu)建出一個根節(jié)點(diǎn)，帶有兩個孩子("left","right")的樹
public Tree( Object[] values ){
// 創(chuàng)建根
_root = new TreeNode( values[0], null );
// 創(chuàng)建下面的子節(jié)點(diǎn)
TreeNode currentParent = _root; // 用于待創(chuàng)建節(jié)點(diǎn)的父親
//TreeNode nextParent = null;
int currentChildIndex = 0; // 表示 currentParent 是他的父親的第幾個兒子
//TreeNode lastNode = null; // 最后一個創(chuàng)建出來的TreeNode，用于找到他的父親
for ( int i = 2; i values.length; i++ ){
// 如果null ,表示下一個節(jié)點(diǎn)的父親是當(dāng)前節(jié)點(diǎn)的父親的第一個孩子節(jié)點(diǎn)
if ( values[i] == null ){
currentParent = (TreeNode)currentParent._childList.get(0);
currentChildIndex = 0;
continue;
}
// 表示一個父節(jié)點(diǎn)的所有孩子輸入完畢
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é)點(diǎn)
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é)點(diǎn)也會打印null
//打印 parent 同層的節(jié)點(diǎn)的孩子
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é)點(diǎn)
for ( int i = 0; i parent._childList.size(); i++ ){
TreeNode child = (TreeNode)parent._childList.get(i);
printSteps( child, currentDepth+1 );
}
}
// 按寬度優(yōu)先遍歷，打印出parent子樹所有的節(jié)點(diǎn)
public void printSteps(){
System.out.println(""+_root);
System.out.println(""+null);
printSteps(_root, 1 );
}**/
// 將給定的值做為 parent 的孩子，構(gòu)建節(jié)點(diǎn)
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;
}
}
//類Node定義二叉樹結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu);
//一個結(jié)點(diǎn)應(yīng)包含結(jié)點(diǎn)值，左子結(jié)點(diǎn)的引用和右子結(jié)點(diǎn)的引用
class Node{
public Node left; //左子結(jié)點(diǎn)
public Node right; //右子結(jié)點(diǎn)
public int value; //結(jié)點(diǎn)值
public Node(int val){
value = val;
}
}
public class Traversal
{
//read()方法將按照前序遍歷的方式遍歷輸出二叉樹的結(jié)點(diǎn)值
//此處采用遞歸算法會比較簡單，也容易理解，當(dāng)然也可以用
//循環(huán)的方法遍歷，但會比較復(fù)雜，也比較難懂。二叉樹遍歷
//用遞歸算法最為簡單，因?yàn)槊總€結(jié)點(diǎn)的遍歷方式都是，根，
//左，右，遞歸的調(diào)用可以讓每個結(jié)點(diǎn)以這種方式遍歷
public static void read(Node node){
if(node != null){
System.out.println(node.value);//輸出當(dāng)前結(jié)點(diǎn)的值
if(node.left != null)
read(node.left); //遞歸調(diào)用 先讀左結(jié)點(diǎn)
if(node.right != null)
read(node.right); //遞歸調(diào)用 后讀右結(jié)點(diǎn)
}
}
public static void main(String[] args){
//初始化5個結(jié)點(diǎn)，分別初始值為1，2，3，4，5
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
//構(gòu)建二叉樹，以n1為根結(jié)點(diǎn)
n1.left = n2;
n1.right = n5;
n2.left = n3;
n2.right = n4;
read(n1);
}
}
注釋和代碼都是我自己寫的，如果樓主覺得有的注釋多余可以自己刪除一些！代碼我都編譯通過，并且運(yùn)行結(jié)果如你提的要求一樣！你只要把代碼復(fù)制編譯就可以了，注意要以文件名Traversal.java來保存，否則編譯不通過，因?yàn)閙ain函數(shù)所在的類是public類型的！
class TreeNode {
public TreeNode left;
public TreeNode right;
public int value;
public TreeNode(TreeNode left, TreeNode right, int value) {
this.left = left;
this.right = right;
this.value = value;
}
}
public class BinaryTree {
public static int getTreeHeight(TreeNode root) {
if (root == null)
return 0;
if (root.left == null root.right == null)
return 1;
return 1 + Math
.max(getTreeHeight(root.left), getTreeHeight(root.right));
}
public static void recursePreOrder(TreeNode root) {
if (root == null)
return;
System.out.println(root.value);
if (root.left != null)
recursePreOrder(root.left);
if (root.right != null)
recursePreOrder(root.right);
}
public static void stackPreOrder(TreeNode root) {
Stack stack = new Stack();
if (root == null)
return;
stack.push(root);
System.out.println(root.value);
TreeNode temp = root.left;
while (temp != null) {
stack.push(temp);
System.out.println(temp.value);
temp = temp.left;
}
temp = (TreeNode) stack.pop();
while (temp != null) {
temp = temp.right;
while (temp != null) {
stack.push(temp);
System.out.println(temp.value);
temp = temp.left;
}
if (stack.empty())
break;
temp = (TreeNode) stack.pop();
}
}
public static void recurseInOrder(TreeNode root) {
if (root == null)
return;
if (root.left != null)
recurseInOrder(root.left);
System.out.println(root.value);
if (root.right != null)
recurseInOrder(root.right);
}
public static void stackInOrder(TreeNode root) {
Stack stack = new Stack();
if (root == null)
return;
else
stack.push(root);
TreeNode temp = root.left;
while (temp != null) {
stack.push(temp);
temp = temp.left;
}
temp = (TreeNode) stack.pop();
while (temp != null) {
System.out.println(temp.value);
temp = temp.right;
while (temp != null) {
stack.push(temp);
temp = temp.left;
}
if (stack.empty())
break;
temp = (TreeNode) stack.pop();
}
}
public static void main(String[] args) {
TreeNode node1 = new TreeNode(null, null, 1);
TreeNode node2 = new TreeNode(null, node1, 2);
TreeNode node3 = new TreeNode(null, null, 3);
TreeNode node4 = new TreeNode(node2, node3, 4);
TreeNode node5 = new TreeNode(null, null, 5);
TreeNode root = new TreeNode(node4, node5, 0);
System.out.println("Tree Height is " + getTreeHeight(root));
System.out.println("Recurse In Order Traverse");
recurseInOrder(root);
System.out.println("Stack In Order Traverse");
stackInOrder(root);
System.out.println("Recurse Pre Order Traverse");
recursePreOrder(root);
System.out.println("Stack Pre Order Traverse");
stackPreOrder(root);
}
}
可以做個參考
重慶分公司
重慶分公司
