初识“树”——搜索二叉树

今天第一次接触了“树”这种数据结构，和双向链表差不多（一个父亲有多个儿子……）

 

为了加深理解，老师让我们做一个搜索二叉树~

 

二叉树 顾名思义就是有两个叉子的树，也是用得比较多的一种，

 

搜索二叉树的优点就是简化搜索步骤：

 

一个节点左面的子节点的数据比这个节点小，右面的子节点比这个数据大，把这样的小树连起来，就是搜索二叉树了

 

比如我要把{4,1,3,2,5}这样一个数组放入搜索二叉树，那么得到的树就如下如所示：

这样，如果搜索的数比4小，那就找根节点左面的那一支，如果比1大，就搜索1右面的那一支，这样递归搜所，效率会比从头开始搜索高。

 

另外一个比较简单的应用就是用这个二叉树把数组排序

 

从小到大输出就是按照 左→根→右的顺序输出就好了~

 

下面是新建节点类的代码：

/**
 * 树的节点
 * @author Micro
 *
 */
public class TreeNode {
	private int obj;
	private TreeNode root;
	private TreeNode left;
	private TreeNode right;
	
	//重载构造器
	public TreeNode(int obj){
		this.obj=obj;
	}
	public int getObj() {
		return obj;
	}
	public void setObj(int obj) {
		this.obj = obj;
	}
	public TreeNode getRoot() {
		return root;
	}
	public void setRoot(TreeNode root) {
		this.root = root;
	}
	public TreeNode getLeft() {
		return left;
	}
	public void setLeft(TreeNode left) {
		this.left = left;
	}
	public TreeNode getRight() {
		return right;
	}
	public void setRight(TreeNode right) {
		this.right = right;
	}
	
	
}

 

下面是创建二叉树的方法，输出的方法还有程序入口

 

/**
 * 数组变成搜索二叉树
 * 
 * @author Micro
 * 
 */
public class TreeTest {
	private static TreeNode root = null;

	// static int n = 0;

	// 程序入口
	public static void main(String[] args) {
		TreeTest ts = new TreeTest();
		int[] a = { 4, 1, 3, 2,5};
		for (int i = 0; i < a.length; i++) {
			ts.add(a[i]);
		}
		// System.out.println(root.getObj());
		ts.print(root);
		// System.out.println(n);
	}

	// 放入树
	public void putin(TreeNode i, TreeNode j) {
		if (i.getObj() < j.getObj()) {
			if (j.getLeft() == null) {
				j.setLeft(i);
				i.setRoot(j);
			} else {
				putin(i, j.getLeft());
			}
		} else {
			if (j.getRight() == null) {
				j.setRight(i);
				i.setRoot(j);
			} else {
				putin(i, j.getRight());
			}
		}
	}

	// 添加树节点
	public void add(int i) {
		TreeNode fat = null;
		TreeNode newTree = new TreeNode(i);
		if (root == null) {
			root = newTree;
		} else {
			fat = root;
			putin(newTree, fat);
		}

	}

	// 遍历节点
	public void print(TreeNode a) {
		if(a!=null) {
			print(a.getLeft());
			System.out.println(a.getObj());
			print(a.getRight());
		}
	}

}

输出的结果是：

1

2

3

4

5  

达到目的了~

 

这样一个搜索二叉树就完成了，我对于二叉树也有了基本的了解，接下来就是要研究研究五十年前那个叫哈夫曼的人种下的树了~哈~