java 二叉树的实现

BinaryTree类：

package com.javaeye.rsrt;

/**
 * 
 * @author nishiting
 *
 */

public class BinaryTree {

	private Node root;
	
	/**
	 * 内部类实现结点类，可提高安全性
	 * @author nishiting
	 *
	 */

	private static class Node {
		Node left;
		Node right;
		int data;

		Node(int newData) {
			left = null;
			right = null;
			data = newData;
		}

	}

	/**
	 * 创建一个空的二叉树
	 */

	public BinaryTree() {
		root = null;
	}
	
	/**
	 * 递归的插入数值
	 * @param data	要插入的数值
	 */

	public void insert(int data) {
		root = insert(root, data);
	}
	
	/**
	 * 将数值插入到二叉树中，比当前结点小或等于当前结点的插在当前结点的左侧，比当前结点大的数插在当前结点的右侧，每次从根结点开始递归比较
	 * @param node	当前的结点，就是根结点，只是每次根结点的左右子孙更新
	 * @param data	要插入的数值
	 * @return	新排好的二叉树
	 */

	private Node insert(Node node, int data) {

		if (node == null) {

			node = new Node(data);

		} else {
			if (data <= node.data) {
				node.left = insert(node.left, data);
			} else {
				node.right = insert(node.right, data);
			}
		}
		return (node);
	}
	
	/**
	 * 将数值输入构建二叉树
	 * @param data	要输入的数值
	 */

	public void buildTree(int[] data) {

		for (int i = 0; i < data.length; i++) {

			insert(data[i]);

		}

	}
	
	/**
	 * 递归打印出二叉树
	 */

	public void printTree() {

		printTree(root);

		System.out.println();

	}
	
	/**
	 * 从根结点开始遍历，从树的最高层叶子结点开始输出，从左至右
	 * @param node	当前的结点
	 */

	private void printTree(Node node) {

		if (node == null)
			return;

		// left, node itself, right

		printTree(node.left);

		System.out.print(node.data + "  ");

		printTree(node.right);

	}

}

 测试类：

package com.javaeye.rsrt;

import junit.framework.TestCase;

public class BinaryTreeTest extends TestCase {

	public void testBinaryTreeTest() {

		BinaryTree biTree = new BinaryTree();

		int[] data = { 2, 8, 7, 4 ,9,3,1,6,7,5};

		biTree.buildTree(data);

		biTree.printTree();

	}

}

 

评论

7 楼 皓子罗 2012-11-22  

遍历顺序错了，应该是
    if(node==null){
    return;
    }
    else {
    System.out.println(node.data+" ");
    printTree(node.left);
    printTree(node.right);
    }

6 楼 TheMatrix 2012-09-24  

现在是int，如果是字符呢，比如：Comparable[] strArr2 = { "c", "b", "x", "a", "k" };

以下是另外一种写法，请指教：

class TreeNode {
	@SuppressWarnings("rawtypes")
	public Comparable nodeData;
	public TreeNode left;
	public TreeNode right;

	public TreeNode(Comparable<?> nodeData) {
		this.nodeData = nodeData;
	}

	@SuppressWarnings("unchecked")
	public void addNode(TreeNode newNode) {
		if (this.nodeData.compareTo(newNode.nodeData) >= 0) {
			if (this.left == null) {
				this.left = newNode;
			} else {
				this.left.addNode(newNode);
			}
		} else {
			if (this.right == null) {
				this.right = newNode;
			} else {
				this.right.addNode(newNode);
			}
		}
	}

	public void printNode() {
		// 1����ʾ��ڵ�
		if (this.left != null) {
			this.left.printNode();
		}
		// 2����ʾ�м�ڵ�
		System.out.println(this.nodeData);
		// 3����ʾ�ҽڵ�
		if (this.right != null) {
			this.right.printNode();
		}
	}
}

class BinaryTreeCtrl {
	private TreeNode root = null;

	private void buildBinaryTree(Comparable<?>[] args) {
		for (Comparable<?> i : args) {
			if (root == null) {
				root = new TreeNode(i);
			} else {
				root.addNode(new TreeNode(i));
			}

		}

	}

	public BinaryTreeCtrl(Comparable<?> args[]) {
		buildBinaryTree(args);
	}

	public void printSortedList() {
		this.root.printNode();
	}

}

public class BinaryTree {

	public BinaryTree() {

	}

	@SuppressWarnings("rawtypes")
	public static void main(String[] args) {
		Comparable[] intArr1 = { 3, 5, 66, 7, 2, 33, 6, 46, 17 };
		new BinaryTreeCtrl(intArr1).printSortedList();
		
		Comparable[] strArr2 = { "c", "b", "x", "a", "k" };
		new BinaryTreeCtrl(strArr2).printSortedList();		
	}

}

5 楼 hanazawakana 2012-06-27  

马克下，学习之

4 楼 knowledge360 2012-05-27  

顶

3 楼 bo_hai 2011-01-17  

写的很好，我学习了。

2 楼 hlzhou 2010-12-23  

1 楼 biguan 2010-07-21  

感谢你让我明白了二叉树的规则，同时发现对二叉树的抽象对象还可以改进一下，特把代码发上来，以供交流。

/**
 * 写一个二叉树
 * */
public class MyBinaryTree {
	private MyNode root;//根节点
	private MyBinaryTree left;//左子树
	private MyBinaryTree right;//右子树
	
	/**
	 * 添加一个数
	 * 将数值插入到二叉树中，比当前结点小或等于当前结点的插在当前结点的左侧，比当前结点大的数插在当前结点的右侧，每次从根结点开始递归比较
	 * */
	public void addData(int n){
		if(root==null){
			root = new MyNode();
			root.setData(n);
		}else{
			int data = root.getData();
			if(n<=data){
				if(this.left==null)
					this.left = new MyBinaryTree();
				this.left.addData(n);
			}else{
				if(this.right==null)
					this.right = new MyBinaryTree();
				this.right.addData(n);
			}
		}
	}
	/**
	 * 先序排序
	 * */
	public void preorder(){
		if(this.root!=null)
			System.out.print(root.getData()+",");
		if(this.left!=null)
			this.left.preorder();
		if(this.right!=null)
			this.right.preorder();
	}
	/**
	 * 中序排序
	 * */
	public void inorder(){
		if(this.left!=null)
			this.left.inorder();
		if(this.root!=null)
			System.out.print(root.getData()+",");
		if(this.right!=null)
			this.right.inorder();
	}
	/**
	 * 后序排序
	 * */
	public void postorder(){
		if(this.left!=null)
			this.left.postorder();
		if(this.right!=null)
			this.right.postorder();
		if(this.root!=null)
			System.out.print(root.getData()+",");
	}

	
	public static void main(String[] args) {
		int[] arr = {2, 8, 7, 4 ,9,3,1,6,7,5};
		MyBinaryTree bt = new MyBinaryTree();
		for(int i=0;i<arr.length;i++){
			bt.addData(arr[i]);
		}
		System.out.println("先序：");
		bt.preorder();
		System.out.println("\n中序：");
		bt.inorder();
		System.out.println("\n后序：");
		bt.postorder();
	}

}
/**
 * 节点对象
 * */
class MyNode {
	private int data;//存储的数据

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}
	
}