当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

二叉查找树

发表于: 2014-07-15   作者:不懂事的小屁孩   来源:转载   浏览:
摘要: 二叉排序树(Binary Sort Tree)又称 二叉查找树(Binary Search Tree),亦称二叉搜索树。 它或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树; 增加 查找 删除 序列化 impor
二叉排序树(Binary Sort Tree)又称 二叉查找树(Binary Search Tree),亦称二叉搜索树。 它或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树;

增加 查找 删除 序列化
import java.util.ArrayList;
import java.util.List;


public class BinsearTree {

	private static Node rootNode = null ;

	private static List<Node> nodelist = new ArrayList<Node>();

	private class Node{
		private int key;
		private Node LeftchildNode;
		private Node rightchildNode;
		private Node parentNode;
		Node(int key,Node leftchildNode,Node rightNode,Node parentNode){
			this.key = key;
			this.LeftchildNode = leftchildNode;
			this.rightchildNode = rightNode;
			this.parentNode = parentNode;
		}
		public int getKey(){
			return key;
		}

	}

	public Boolean isEmpty(){
		if(rootNode == null){
			return true;
		}else{
			return false;
		}
	}

	public void insert(int k){
		Node parentNode = null;
		Node newNode = new Node(k, null, null, null);
		Node pNode = rootNode;
		if(rootNode ==null){
			rootNode = newNode;
			return;
		}
		while(pNode != null){
			parentNode = pNode;
			if(k<pNode.key){
				pNode = pNode.LeftchildNode;
			}else if(k>pNode.key){
				pNode = pNode.rightchildNode;
			}else{
				return;
			}
		}
		if(k<parentNode.key){
			parentNode.LeftchildNode = newNode;
			newNode.parentNode = parentNode;
		}else{
			parentNode.rightchildNode = newNode;
			newNode.parentNode = parentNode;
		}
	}

	public static void main(String[] args) {
		BinsearTree nodetreeBinsearTree = new BinsearTree();
		System.out.println("查找树是否为空? " + (nodetreeBinsearTree.isEmpty() ? "是" : "否"));
		int[] src = {9,1,32,4,2,34,5,44,23,11,87,94,31};
		for(int k : src){
			nodetreeBinsearTree.insert(k);
		}
		System.out.println("查找树是否为空? " + (nodetreeBinsearTree.isEmpty() ? "是" : "否"));
		System.out.println("最小关键字为:" + minnode(rootNode).getKey());
		System.out.println("最大关键字为:" + maxnode(rootNode).getKey());
		tranver(nodetreeBinsearTree);
		Node serNode = findnode(23);
		if(serNode == null){
			System.out.println("不含有该结点");
		}else{
			delate(serNode);
		}
		tranver(nodetreeBinsearTree);
	}

	private static void delate(Node node) {
		if(rootNode == null){
			System.out.println("树为空");
			return;
		}
		if(node==rootNode){
			rootNode = null;
			System.out.println("该节点是树的根节点,删除树成功!");
		}
		if(node.LeftchildNode==null && node.rightchildNode ==null){
			System.out.println("该节点无子节点");
			if(node == node.parentNode.LeftchildNode){
				node.parentNode.LeftchildNode = null;
			}else{
				node.parentNode.rightchildNode = null;
			}
			System.out.println("删除成功!");
			return;
		}
		if(node.rightchildNode==null){
			System.out.println("该节点有一个左节点");
			if(node == node.parentNode.LeftchildNode){
				node.parentNode.LeftchildNode = node.LeftchildNode;
			}else{
				node.parentNode.rightchildNode = node.LeftchildNode;
			}
			System.out.println("删除成功!");
			return;
		}
		if(node.LeftchildNode==null){
			System.out.println("该节点有一个右节点");
			if(node == node.parentNode.LeftchildNode){
				node.parentNode.LeftchildNode = node.rightchildNode;
			}else{
				node.parentNode.rightchildNode = node.rightchildNode;
			}
			System.out.println("删除成功!");
			return;
		}
		System.out.println("该节点有两个节点");
		Node node2 = maxnode(node.LeftchildNode);
		if(node == node.parentNode.LeftchildNode){
			node.parentNode.LeftchildNode = node2;
		}else{
			node.parentNode.rightchildNode = node2;
		}
		if(node2 != node.LeftchildNode){
			node2.parentNode.rightchildNode = null;
			node2.LeftchildNode = node.LeftchildNode;
			node.LeftchildNode.parentNode = node2.LeftchildNode;
		}
		node2.parentNode = node.parentNode;
		node2.rightchildNode = node.rightchildNode;
		node.rightchildNode.parentNode = node2.rightchildNode;
		System.out.println("删除成功!");
	}

	private static Node findnode(int key) {
		if(rootNode == null){
			System.out.println("树为空");
		}
		Node prodeNode = rootNode;
		while(prodeNode != null){
			if(key<prodeNode.key){
				prodeNode = prodeNode.LeftchildNode;
			}else if(key>prodeNode.key){
				prodeNode = prodeNode.rightchildNode;
			}else{
				break;
			}
		}
		if(prodeNode != null){
			return prodeNode;
		}else{
			return null;
		}
	}

	private static void tranver(BinsearTree tree) {
		inmidtranver();
		System.out.println("对树进行有序化:");
		for(Node node : nodelist){
			System.out.print(node.key+" ");
		}
		System.out.println();
	}

	private static void  inmidtranver(){
		if(nodelist.size()>0){
			nodelist.clear();
		}
		midtranver(rootNode);
	}

	private static void midtranver(Node rootNode){
		if(rootNode == null){
			return;
		}
		midtranver(rootNode.LeftchildNode);
		nodelist.add(rootNode);
		midtranver(rootNode.rightchildNode);
	}

	private static Node minnode(Node rootNode) {
		if(rootNode == null){
			System.out.println("树为空 ");
		}
		while(rootNode.LeftchildNode  !=null){
			rootNode = rootNode.LeftchildNode;
		}
		return rootNode;
	}

	private static Node maxnode(Node rootNode) {
		if(rootNode == null){
			System.out.println("树为空 ");
		}
		while(rootNode.rightchildNode  !=null){
			rootNode = rootNode.rightchildNode;
		}
		return rootNode;
	}


}

二叉查找树

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
当进行插入,删除和查找操作中,二叉查找树的性能比迄今为止所研究的任何一种数据结构都好。 1. 二
根据算法导论上的思路方法,写了一个c语言版的二叉查找树实现。 一颗淡定的二叉查找树 以下为算法详
  接上一篇,继续讲二叉查找树的操作,之前的博客都讲得差不多了,本篇就讲一下删除操作,以及求
接上一篇,继续讲二叉查找树的操作,之前的博客都讲得差不多了,本篇就讲一下删除操作,以及求最矮
一、二叉查找树: 查找树是一种数据结构,它支持多种动态集合操作,包括search,minimum,maximum,
//二叉搜索树 public class BinarySearchTree<T extends Comparable<? super T>> { /**
看了二叉查找树就自己用java写了个。。写插入时。犯了个很二的错误,就不提了,使用的是中序遍历。
原文地址:http://www.cnblogs.com/yc_sunniwell/archive/2010/06/27/1766236.html 这篇将是最有难
来源:http://www.cnblogs.com/JCSU/articles/2026482.html /* **********************************
在文章《常用数据结构及复杂度》中,介绍了一些计算机程序设计中常用的线性数据结构,包括 Array、A
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号