数据结构与算法_二叉查找树

1.建立BST树

/**
	 * 往BST树中添加节点（公开的接口函数）
	 * @param node 需要添加到BST树的那个节点
	 */
	public void add(TreeNode node){
		if(root == null){
			root = node;
		}else{
			add(root,node);
		}
	}
	
	/**
	 * 隐藏的函数，add方法的具体实现
	 * @param parent BST树（或者子树）的根节点
	 * @param child  要插入BST树的节点
	 */
	private void add(TreeNode parent,TreeNode child){
		if(child.value < parent.value){		//判断与父节点的大小
			if(parent.left != null){		//判断父节点是否有子节点，没有才能代入子节点进入下一次递归
				add(parent.left,child);
			}else
				parent.left = child;			
		}else if(child.value >= parent.value){
			if(parent.right != null){
				add(parent.right,child);
			}else
				parent.right = child;
		}			
	}
           

注意：

1.add方法具体实现中，添加一个node的时候，有两步判断，一个是跟父节点比较大小确定是放在左子树还是右子树，第二是判断node是该父节点的直属儿子还是其儿子的后代，即父节点左右子树是不是为null，是的话node就做该父节点的儿子节点，否则交给其子树递归处理，作为该父节点的孙子或者重孙。

2.BST树搜索

/**
	 * 在BST树中搜索指定元素，返回元素的position
	 * @param root BST树(子树)的根节点
	 * @param key  要查找的元素
	 * @return  key元素的位置，不存在就返回-1
	 */

	public int searchBST(TreeNode root,int key){
		if(root == null){
			return -1;
		}else{
                      //判断当前节点的value是否与key相等，是则返回该节点位置，否则左右递归
                        if(key == root.value){
				return root.position;
			}else if(key <root.value){
				return searchBST(root.left,key);
			}else{
				return searchBST(root.right,key);
			}
		}
	}
           

3.BST树的深度优先遍历【Deep First Search】

* 深度优先遍历[中序遍历left->center->right]
	 * 前中后遍历的依据是看center是第几个访问的
	 * @param root 二叉树的根节点
	 */
	public void DSF(TreeNode root){
		if(root == null){
			return;
		}else{
			DSF(root.left);
			System.out.print(root.value+"\t");
			DSF(root.right);
			
			/*
			//先序遍历：center->left->right
			System.out.print(root.value+"\t");
			DSF(root.left);
			DSF(root.right);
			*/
			
			/*
			//后序遍历	left->right->center		
			DSF(root.left);
			DSF(root.right);
			System.out.print(root.value+"\t");
			*/
		}
	}
           

4.广度优先遍历【Breadth First Search】

/**
	 * 广度优先遍历
	 * @param root 二叉树的根节点
	 */
	public void BSF(TreeNode root){
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		TreeNode currentNode = null;
		queue.offer(root);
		
		while(!queue.isEmpty()){
			currentNode = queue.poll();
			System.out.print(currentNode.value+"\t");
			
			if(currentNode.left != null)
				queue.offer(currentNode.left);
			if(currentNode.right != null)
				queue.offer(currentNode.right);						
		}
	}
           

注意：

1.while里面的两个判断是都要执行的，而不是选择执行其中一个。因为当前节点的左右子节点要一起输出。

2.while里面的输出队列元素的打印速度和元素入队的速度不是同步的，依次循环可能添加多个元素入队，但是输出一个元素出队。有可能BST树所有的元素都已经遍历到队列中了，还在利用while循环输出