当前位置:首页 > 开发 > 系统架构 > 架构 > 正文

二叉查找树之查找算法

发表于: 2014-10-22   作者:书安然   来源:转载   浏览次数:
摘要: package com.pb.datastructure.find; /** *二叉查找树查找算法 * * @author Administrator */ public class FindSortTree { private Node root;// 根节点 /** * 增加节点 * * @param data */ publ
package com.pb.datastructure.find;

/**
 *二叉查找树查找算法
 * 
 * @author Administrator
 */
public class FindSortTree {
	private Node root;// 根节点

	/**
	 * 增加节点
	 * 
	 * @param data
	 */
	public void add(int data) {
		if (root == null) {
			this.root = new Node(data, null, null);
		} else {
			addTree(root, data);
		}
	}

	/**
	 * 增加节点(根节点不为空)
	 */
	public void addTree(Node root, int data) {
		if (root.data > data) {
			if (root.left == null) {
				root.left = new Node(data, null, null);// 当前节点左子树为空,直接插入左子树
			} else {
				addTree(root.left, data);// 递归调用左子树
			}
		} else {
			if (root.right == null) {
				root.right = new Node(data, null, null);// 当前节点右子树为空,直接插入右子树
			} else {
				addTree(root.right, data);// 递归调用右子树
			}
		}
	}

	[color=darkred]/**
	 * 查找 @ id
	 */
	public Node searchNode(int id) {
		Node n = null;
		Node cur = root;
		while (true) {
			if (cur == null) {
				break;
			}
			if (cur.data == id) {
				n = cur;
				break;
			}
			if (id > cur.data) {
				cur = cur.right;// 如果给定值大于当前节点值的关键字,进入右子树继续循环
			} else {
				cur = cur.left;// 如果给定值小于当前节点值的关键字,进入左子树继续循环
			}
		}
		return n;
	}
[/color]
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		FindSortTree tree = new FindSortTree();
		tree.add(3);
		tree.add(12);
		tree.add(7);
		tree.add(42);
		tree.add(23);
		tree.add(37);
		System.out.println("查找节点为 23");
		if (tree.searchNode(23) == null) {
			System.out.println("查找失败");
		} else {
			System.out.println("查找成功!查找到的节点为:" + tree.searchNode(23).data);
		}
	}

	/**
	 * Node 类
	 */
	public 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;
		}
	}

}

运行结果:
查找节点为 23
查找成功!查找到的节点为:23

二叉查找树之查找算法

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
前一篇博客学习了高效动态表查找的二叉排序树,虽然在二叉排序树上实现的插入,删除和查找等基本操
摘要:   本章介绍了二叉查找树的概念及操作。主要内容包括二叉查找树的性质,如何在二叉查找树中
  1、前言:   接着学习动态规划方法,最优二叉查找树问题。二叉查找树参考http://www.cnblogs.
从前面介绍的查找方法我们知道,折半查找较顺序查找速度快,但折半查找要求表中记录必须有序,因为
1. 查找 利用二叉查找树左小右大的性质,可以很容易实现查找任意值和最大/小值。 BSTNode * bst_sea
前面介绍的BST(二叉排序树)和AVL(平衡二叉树)都是二叉树,用作内部查找的数据结构,即被查找的数据
一、二叉查找树 1.定义特点维基百科 2.我当时在写实例化的方法的时候很犯愁 =》理解RootNode为整个
第十二章 二叉查找树 前几章比较简单,都是数据结构里的简单内容,以前也都写过,这次就不浪费时间
概要 在前面分别介绍了"二叉查找树的相关理论知识,然后给出了二叉查找树的C和C++实现版本"。这一章
基数树与二叉查找树和Trie树很相似。它像BST一样是二叉的,向左表示0而不是BST的小于, 而向右则表
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号