`
marcoSpring
  • 浏览: 32671 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

java 二叉搜索树(搜索、添加、遍历)

阅读更多
     栈、队列、链表都有他们各自的好处,同样的也有弊端的存在。
     如果我想要一个有序的数组和链表这个当然很好实现。现在我要在这几个数据结构中查找一个值。先说数组,因为是有序的通过二分查找很快的就可以找到。查找的效率还是很高的,但如果要是插入呢,为了保证有序,我要先找到插入位置,然后再将比插入数字大的数字依次向后移动;这时的第一反应就是链表!他打插入速度很快,只要改变指针的指向就可以了。但是链表大查找要从头开始找啊。只有知道了前一个元素的地址才能知道下一个地址。所以链表查找起来又费劲了。这时候就有人引进了树。
    树也分很多种,只说特殊的二叉树中的二叉搜索树。
    二叉搜索树定义:一个节点的左子节点的关键自值小于这个节点,右子节点的关键字值大于或等于这个父节点。
    二叉搜索树插入的时候可以直接改变左树右树的指针指向,查找的时候可以根据排序二叉树的特点。
    这就是一个二叉搜索树

    现在开始用代码来描述这棵树。先看节点类
   
package test; 
/** 
 * @author 作者 MarcoSpring 
 * @version 创建时间:2012-8-3 上午10:13:13 
 * 树节点类 
 */
public class TreeNode {
	public int keyValue;    //关键字值
	public TreeNode leftNode;//左节点
	public TreeNode rightNode;//右节点
	
	public TreeNode(){}
	public TreeNode(int Key){
		this.keyValue = Key;
	}
}

代码不多,描述了一个节点的内容。关于二叉搜索树的描述主要从查询节点、添加节点、遍历、最大值、最小值、删除节点来描述。这里不包括存在相等节点的情况。
查询节点:这个比较简单,根据二叉树的定义查询就可以了。看图写代码最方便,

再看代码
public TreeNode search(int Key) {
		TreeNode node = root;
		// 首先定义一个节点让其指向根,在下面的循环中
		// 只要节点值不等于要查找的节点值就进入循环如果没有找到则返回null
		while (node.keyValue != Key) {
			if (Key < node.keyValue) { // 如果要查找的值小于节点值则指向左节点
				node = node.leftNode;
			} else { // 否则指向右节点
				node = node.rightNode;
			}
			if (node == null) { // 如果节点为空了则返回null
				return null;
			}
		}
		return node;
	}

添加节点,添加节点的过程是现搜索再添加。先看图

再看代码
public void insert(int Key) {
		TreeNode node = new TreeNode(Key);
		// 添加节点之前首先要找到要添加的位置,这样就要记住要添加节点的父节点
		// 让父节点的左右指向要添加的节点
		if (root == null) { // 如果根结点为空,则根节点指向新节点
			root = node;
		} else {
			TreeNode currentNode = root;// 定义当前节点并指向根节点
			TreeNode parentNode;
			while (true) { // 寻找节点添加的位置
				parentNode = currentNode;
				if (Key < currentNode.keyValue) {
					currentNode = currentNode.leftNode;
					if (currentNode == null) { // 当找到空节点的时候,父节点的左节点指向新节点
						parentNode.leftNode = node;
						return;
					}
				} else {
					currentNode = currentNode.rightNode;
					if (currentNode == null) { // 当找到空节点的时候,父节点的右节点指向新节点
						parentNode.rightNode = node;
						return;
					}
				}
			}
		}
	}


遍历树:遍历分为中序遍历(最常用,也最有用),前序遍历,后续遍历。
这里就发一个中序遍历的图,理解了这个前序和后续都很好理解。

再看代码
public void display(TreeNode node) {
		if (node != null) {
			display(node.leftNode);
			System.out.println(node.keyValue + ",");
			display(node.rightNode);
		}
	}


最大值、最小值:这个就不用说了,最大值一直往右走,最小值一直往左走。
直接上代码:
	public int max() {
		TreeNode node = root;
		TreeNode parent = null;
		while (node != null) {
			parent = node;
			node = node.rightNode;
		}
		return parent.keyValue;
	}

	
	public int min() {
		TreeNode node = root;
		TreeNode parent = null;
		while (node != null) {
			parent = node;
			node = node.leftNode;
		}
		return parent.keyValue;
	}

关于删除节点单独发一篇,因为实在太麻烦了。。。
  • 大小: 106.1 KB
  • 大小: 108.1 KB
  • 大小: 90.7 KB
  • 大小: 92.7 KB
分享到:
评论
1 楼 cuisuqiang 2012-08-07  
非常好,坚决学习!

相关推荐

Global site tag (gtag.js) - Google Analytics