树集合了数组（查找速度快）和链表（插入、删除速度快）的优点

二叉树是一种特殊的树，即：树中的每个节点最多只能有两个子节点

二叉搜索树是一种特殊的二叉树，即：节点的左子节点的值都小于这个节点的值，节点的右子节点的值都大于等于这个节点的值

节点类：

public class Node {

	public int id;

	public String name;

	public Node leftChild;

	public Node rightChild;

	public Node(int id, String name) {

		this.id = id;

		this.name = name;

	}

}

实现类（如果树中允许存在重复数据，处理起来比较麻烦，故实现中不允许树中存在重复数据，即节点的右子节点的值必须大于节点的值）：

搜索二叉树有一个特点，即如果使用中序遍历遍历搜索二叉树，将得到包含搜索二叉树中所有节点值的升序排序结果

public class BinarySearchTree {

	public Node root;

	public Node find(int key){

		if(root == null){

			System.out.println("The tree is empty!");

			return null;

		}

		Node current = root;

		while(current.id != key){

			if(key > current.id)

				current = current.rightChild;

			else

				current = current.leftChild;

			if(current == null)

				return null;

		}

		return current;

	}

	public boolean insert(Node node){

		if(root == null){

			root = node;

			return true;

		}

		//树中不允许插入重复的数据项

		if(this.find(node.id) != null){

			System.out.println("Node with id '" +

					node.id + "' has already existed!");

			return false;

		}

		Node current = root;

		while(current != null){

			if(node.id > current.id){

				if(current.rightChild == null){

					current.rightChild = node;

					return true;

				}

				current = current.rightChild;

			}else{

				if(current.leftChild == null){

					current.leftChild = node;

					return true;

				}

				current = current.leftChild;

			}

		}

		return false;

	}

	//前序遍历

	public void preorder_iterator(Node node){

		System.out.print(node.id + " ");

		if(node.leftChild != null)

			this.preorder_iterator(node.leftChild);

		if(node.rightChild != null)

			this.preorder_iterator(node.rightChild);

	}

	//中序遍历

	//中序遍历二叉搜索树将会得到包含二叉搜索树

	//所有数据项的有序数列

	public void inorder_iterator(Node node){

		if(node.leftChild != null)

			this.inorder_iterator(node.leftChild);

		System.out.print(node.id + " ");

		if(node.rightChild != null)

			this.inorder_iterator(node.rightChild);

	}

	//后序遍历

	public void postorder_iterator(Node node){

		if(node.leftChild != null)

			this.postorder_iterator(node.leftChild);

		if(node.rightChild != null)

			this.postorder_iterator(node.rightChild);

		System.out.print(node.id + " ");

	}

	//获取树（子树）中的最小节点

	public Node getMinNode(Node node){

		if(this.find(node.id) == null){

			System.out.println("Node dosen't exist!");

			return null;

		}

		if(node.leftChild == null)

			return node;

		Node current = node.leftChild;

		while(current.leftChild != null)

			current = current.leftChild;

		return current;

	}

	//获取树（子树）中的最大节点

	public Node getMaxNode(Node node){

		if(this.find(node.id) == null){

			System.out.println("Node dosen't exist!");

			return null;

		}

		if(node.rightChild == null)

			return node;

		Node current = node.rightChild;

		while(current.rightChild != null)

			current = current.rightChild;

		return current;

	}

	//删除节点需要分3种情况进行讨论

	public boolean delete(int key){

		if(root == null){

			System.out.println("The tree is empty!");

			return false;

		}

		Node targetParent = root;

		Node target = root;

		boolean isLeftChild = true;

		while(target.id != key){

			if(key > target.id){

				targetParent = target;

				target = target.rightChild;

				isLeftChild = false;

			}else{

				targetParent = target;

				target = target.leftChild;

				isLeftChild = true;

			}

			if(target == null)

				break;

		}

		if(target == null){

			System.out.println("Node dosen't exist!"

					+ "Can not delete.");

			return false;

		}

		//被删除节点为叶子节点

		if(target.leftChild == null &&

				target.rightChild == null){

			if(target.id == root.id){

				root = null;

				return true;

			}

			if(isLeftChild)

				targetParent.leftChild = null;

			else

				targetParent.rightChild = null;

		}

		//被删除节点有1个子节点

		//被删除节点只有右子节点

		else if(target.leftChild == null &&

				target.rightChild != null){

			if(target.id == root.id){

				root = root.rightChild;

				return true;

			}

			if(isLeftChild)

				targetParent.leftChild = target.rightChild;

			else

				targetParent.rightChild = target.rightChild;

		}

		//被删除节点只有左子节点

		else if(target.leftChild != null &&

				target.rightChild == null){

			if(target.id == root.id){

				root = root.leftChild;

				return true;

			}

			if(isLeftChild)

				targetParent.leftChild = target.leftChild;

			else

				targetParent.rightChild = target.leftChild;

		}

		//被删除节点有2个子节点

		else{

			Node followingNode = this.getFollowingNode(target);

			if(target.id == root.id)

				root = followingNode;

			else if(isLeftChild)

				targetParent.leftChild = followingNode;

			else

				targetParent.rightChild = followingNode;

			followingNode.leftChild = target.leftChild;

			followingNode.rightChild = target.rightChild;

		}

		return true;

	}

	//获取被删除节点的后续节点

	private Node getFollowingNode(Node node2Del){

		Node nodeParent = node2Del;

		//只有被删除节点有左右子节点时，才会调用该方法

		//这里直接调用rightChild是没有问题的

		Node node = node2Del.rightChild;

		while(node.leftChild != null){

			nodeParent = node;

			node = node.leftChild;

		}

		if(node.id != node2Del.rightChild.id)

			nodeParent.leftChild = node.rightChild;

		else

			nodeParent.rightChild = node.rightChild;

		return node;

	}

	public static void main(String[] args) {

		//插入

		BinarySearchTree bst = new BinarySearchTree();

		Node n1 = new Node(20, "root");

		Node n2 = new Node(10, "left");

		Node n3 = new Node(30, "right");

		bst.insert(n1);

		bst.insert(n2);

		bst.insert(n3);

		//遍历

		bst.preorder_iterator(bst.root);

		System.out.println();

		bst.inorder_iterator(bst.root);

		System.out.println();

		bst.postorder_iterator(bst.root);

		System.out.println();

		//删除

		Node n4 = new Node(5, "");

		Node n5 = new Node(15, "");

		Node n6 = new Node(40, "");

		Node n7 = new Node(35, "");

		Node n8 = new Node(45, "");

		bst.insert(n4);

		bst.insert(n5);

		bst.insert(n6);

		bst.insert(n7);

		bst.insert(n8);

		bst.inorder_iterator(bst.root);

		System.out.println();

		bst.delete(20);

		bst.inorder_iterator(bst.root);

		System.out.println();

	}

}

执行结果：

20 10 30

10 20 30

10 30 20

5 10 15 20 30 35 40 45

5 10 15 30 35 40 45

二叉搜索树的效率：

树的大部分操作需要从上至下一层层的查找树的节点，对于一棵满树，大约有一半的节点处于最底层（最底层节点数 = 其它层节点数的和 + 1），故节点操作大约有一半需要找到最底层节点，大约有四分之一的节点处于倒数第二层，故节点操作大约有四分之一需要找到倒数第二层节点，依此类推

查找过程中，需要访问每一层的节点，故只要知道了查找的层数，就能知道操作所需的时间，如果节点总数为N，层数为L，L=log2(N+1)

如果为查找操作或删除操作，被操作的节点可能是是树的任意节点，故查找操作或删除操作的时间复杂度为：1/21*log2(N+1) + 1/22*log2(N/2+1) + ... + 1/2N*1

如果为插入操作，由于每次都在树的最低层插入新的节点，故插入操作的时间复杂度为：log2(N+1)

总的来说可以认为二叉搜索树操作的时间复杂度为为O(logN)

如果树不是一棵满树，则判断起来比较复杂，但是如果层数相同，对满树的操作肯定比对不满树的操作更耗时

对于一个含有10000个数据项的有序链表，查找操作平均需要比较5000次，对于一个含有10000个节点的二叉搜索树，查找操作大约需要13次

对于一个含有10000个数据项的有序数组，插入操作平均需要移动5000次（对于比较次数，使用不同的算法比较次数并不相同），对于一个含有10000个节点的二叉搜索树，插入操作只需大约13次比较就可找到待插入节点的插入位置，并且由于该位置总是处于二叉搜索树的最底层，并不需要移动其它的节点

可以看出，二叉搜索树集合了有序链表插入删除效率高和有序数组查询效率高的优点

最新文章

  1. 理解 OpenStack 高可用（HA）（3）：Neutron 分布式虚拟路由（Neutron Distributed Virtual Routing）
  2. Notes for Studying Django
  3. <[你在荒废时间的时候别人都在拼命！]>
  4. mysql远程链接 方法和flush-hosts
  5. 【原创】解决国内Android SDK无法更新问题更新
  6. 利用JConsole工具监控java程序内存和JVM
  7. 为什么windows dos和Linux shell有这样的差别？？
  8. Android中GridView、ListView 的 getChildAt() 方法返回null 问题
  9. 关于表单提交submit的兼容性问题。
  10. 为什么使用bootstrap在一个页面同时做两个轮播效果时，只有第一个有效？？
  11. ElasticSearch Index 速度优化 （官方翻译）
  12. Python中最好用的命令行解析工具：argparse
  13. 作为小白，如何学习Web前端开发？
  14. 启动docker容器时的Error response from daemon: devmapper: Error mounting: invalid argument. 错误解决
  15. Codeforces Round #512 (Div. 2) D. Vasya and Triangle
  16. SpringBoot入门之Thymeleaf的使用
  17. HDFS 安全模式的理解
  18. ribbbitMq 教程，详细
  19. UI设计教程分享：设计一个高质量的logo要从哪方面入手呢？
  20. Ubuntu下部分软件的简介及安装

热门文章

  1. Struts2的输入验证
  2. php-fpm占用系统资源分析
  3. Mysql创建、删除用户
  4. javascript 工具方法（长期更新）
  5. 微信读书 iOS 性能优化总结
  6. UVA10361 - Automatic Poetry
  7. Codeforces Round #219 (Div. 1)（完全）
  8. android4.0访问不能网络解决方法
  9. Python3批量爬取网页图片
  10. OOP设计模式[JAVA]——03职责链模式