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

二叉查找树之查找算法

发表于: 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

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号