什么是二叉查找树：

根节点的值大于其左子树中任意一个节点的值，小于其右节点中任意一节点的值，这一规则适用于二叉查找树中的每一个节点。

本文章重点来讨论一下关于二叉查找树删除节点的问题。

有一下二叉查找树，如图：



在删除节点的时候我们只需考虑一下三种情况：

（1）要删除的节点是叶子结点，如图：



（2）要删除的节点有左节点但是没有右节点，或者有右节点但是没有左节点，如图：



（3）要删除的节点既有左节点又有右节点，在这种情况下，我们只需要将找到待删节点的右子树中值最小的节点，将其删除并且获取其值，并用其值替换待删节点的值即可。如图：



如上图所示，如果要删除节点7，则需寻找其右子树中节点值最小的9，并且该值一定位于该右子树的最左子节点；但是还有一种情况，如图一右子树没有左节点，但是只有右节点，这种情况就回到了前面的第二种情况。

具体代码如下：注意Node类是一个内部类，在使用时注意方法。
package com.zc.algorithm;

public class BinarySortTree {

    public class Node{
        int value;
        Node left;
        Node right;

        public Node(int  value)
        {
            this.value = value;
        }
        public void add(Node node)
        {
            if(node == null)
            {
                return;
            }
            //判断传入的节点的值比当前子树的根节点的值大还是小
            if(node.value < this.value)
            {
                //如果左节点为空
                if(this.left == null)
                {
                    this.left = node;
                }
                else
                {
                    this.left.add(node);
                }
            }
            else
            {
                if(this.right == null)
                {
                    this.right =node;
                }
                else
                {
                    this.right.add(node);
                }

            }
        }

        /**
         * 前序遍历二叉排序树
         * @param node
         */
        public void middleOder(Node node)
        {
            if(node == null)
            {
                return;
            }
            middleOder(node.left);
            System.out.println(node.value);
            middleOder(node.right);
        }

        /**
         * 查找某一节点
         * @param value
         * @return
         */
        public Node search(int value)
        {
            if(this.value == value)
            {
                return this;
            }
            else if(value < this.value)
            {
                if(this.left == null)
                {
                    return null;
                }
                 return this.left.search(value);
            }
            else
            {
                if(this.right == null)
                {
                    return null;
                }
                return  this.right.search(value);
            }

        }
        public Node searchParent(int value) {
            if((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value))
            {
                return this;
            }
            else
            {
                if(this.value > value&& this.left != null)
                {
                    return this.left.searchParent(value);
                }
                else if(this.value < value && this.right !=null)
                {
                    return this.right.searchParent(value);
                }
            }
            return null;
        }
      }


    Node root;
    /**
     * 向二叉排序树中添加节点
     * @param node
     */
    public void add(Node node)
    {
        if(root == null)
        {
            root = node;
        }
      else
        {
            root.add(node);
        }
    }
    public void frontShow()
    {
        if(root != null)
        {
            this.root.middleOder(root);
        }
    }
    public Node SearchNode(int value)
    {
        if(root == null)
            return null;
        else
        {
            return root.search(value);
        }
    }

    public void delete(int value) {
        if (root == null)
            return;
        else
        {
            Node target = SearchNode(value);
            //如果没有这个节点
            if(target == null)
            {
                return;
            }
            //找到他的父节点
            Node parent = searchParent(value);
            //要删除的节点是叶子结点
            if(target.left == null && target.right == null)
            {
                //要删除的节点是节点的左子节点
                if(parent.left.value == value)
                {
                    parent.left =null;
                }
                else
                {
                    parent.right = null;
                }
            }
            //要删除的节点有两个子节点的情况
            else if(target.left != null && target.right != null)
            {
                   //删除右子树中值最小的节点，并获取到该节点的值
                int min = minDelete(target.right);
                //替换目标节点中的值
                target.value = min;
            }
            else
            {
                //需要删除的目标节点的左节点不为空
                if(target.left != null)
                {
                    //要删除的子节点是其父节点的左子节点，并且有左节点而没有有节点
                    if(parent.left.value == value)
                    {
                        parent.left = target.left;
                    }
                    //要删除的子节点是其父节点的右子节点，并且有左节点而没有有节点
                    else
                    {
                        parent.right = target.left;
                    }
                }
                //需要删除的目标节点的右节点不为空
                else
                {
                    //要删除的节点是父节点的左节点，并且有右节点儿没有左节点
                    if(parent.left.value == value)
                    {
                        parent.left = target.right;
                    }
                    //要删除的节点是其父节点的右节点，并且有右孩子没有左孩子
                    else
                    {
                        parent.right = target.right;
                    }
                }


            }

        }
    }

    /**
     * 删除一颗树中最小的节点
     * @param node
     * @return
     */
    public int minDelete(Node node)
    {
        Node target = node;
        while(target.left != null)
        {
            target = target.left;
        }
       delete(target.value);
        return target.value;

    }
    /**
     * 查找父节点
     * @param value
     * @return
     */
    public Node searchParent(int value)
    {
        if(root == null)
        {
            return null;
        }
        else
        {
            return root.searchParent(value);
        }
    }
    public static void main(String[] args)
    {
        int[] arr = new int[]{7,3,10,12,5,1,9};
        BinarySortTree binTree = new BinarySortTree();
        for(int i : arr)
        {
            binTree.add(binTree.new Node(i));
        }
        binTree.delete(7);
        //查看树中的值
        binTree.frontShow();
        //查找
      //  Node node = binTree.new Node(3);
        //Node res = binTree.SearchNode(node.value);
        //System.out.println(res.value);
       // Node temp = binTree.SearchNode(20);
        //System.out.println(temp.value);
    }
}

二叉查找树的定义
二叉查找树：

要么二叉查找树是一棵空树
要么二叉查找树由根结点、左子树、右子树组成，其中左子树和右子树都是二叉查找树，且左子树上所有结点的数据域均小于或等于根结点的数据域，右子树上所有结点的数据域均大于根结点的数据域。



二叉查找树的基本操作
1.查找操作

3. 如果当前根结点root为空，说明查找失败，返回

4. 如果需要查找的值x等于当前根结点的数据域root->data，说明查找成功，访问之。

5. 如果需要查找的值x小于当前根结点的数据域root->data，说明应该往左子树查找，因此向root->lchild递归。

6. 说明需要查找的值x大于当前根结点的数据域root->data，则应该往右子树查找，因此向root->rchild递归。
//search函数查找二叉查找树中数据域为x的结点
void search(node* root, int x)
{
    if(root == NULL) //空树，查找失败
    {
        printf("search failed\n");
        return;
    }
    if(x == root->data) //查找成功，访问之
    {
        printf("%d\n", root->data);
    }
    else if(x < root->data) //如果x比根结点的数据域小，说明x在左子树
    {
        search(root->lchild); //往左子树搜索x
    }
    else //如果x比根结点的数据域大，说明x在右子树
    {
        search(root->rchild, x); //往右子树搜索x
    }
}

二叉查找树中数据域顺序：左子树<根结点<右子树

2.插入操作

7. 当对某个需要查找的值在二叉查找树中查找成功，说明结点已经存在。

8. 如果这个需要查找的值在二叉查找树中查找失败，说明查找失败的地方一定是结点需要插入的地方。
//insert函数将在二叉树中插入一个数据域为x的新结点(注意参数root要加引用&)
void insert(node* &root, int x)
{
    if(root == NULL) //空树，说明查找失败,即插入位置
    {
        root = newNode(x); //新建结点，权值为x
        return;
    }
    if(x == root->data) //查找成功，说明结点已存在，直接返回
    {
        return;
    }
    else if(x < root->data) //如果x比根结点的数据域小，说明x需要插在左子树
    {
        insert(root->lchild, x); //往左子树搜索x
    }
    else //如果x比根结点的数据域大，说明x需要插在右子树
    {
        insert(root->rchild, x); //往右子树搜索x
    }
}

3.二叉查找树的建立

建立一棵二叉查找树，先后插入n个结点的过程
//二叉查找树的建立
node* Create(int data[], int n)
{
    node* root = NULL; //新建根结点root
    for(int i = 0; i < n; i++)
    {
        insert(root, data[i]); //将data[0]~data[n-1]插入二叉查找树中
    }
    return root; //返回根结点
}

4.二叉查找树的删除

前驱：把比结点权值小的最大结点称为该结点的前驱，即该结点左子树中最右结点(从左子树根结点开始不断沿着rchild往下直到rchild为NULL时的结点)。

后继：把比结点权值大的最小结点称为该结点的后继，即该结点右子树中最左结点(从右子树根结点开始不断沿着lchild往下直到lchild为NULL时的结点)。
//寻找以root为根结点的树中的最大权值结点
node* findMax(node* root)
{
    while(root->rchild != NULL)
    {
        root = root->rchild; //不断往右，直到没有右孩子
    }
    return root;
}
//寻找以root为根结点的树中的最小权值结点
node* findMin(node* root)
{
    while(root->lchild != NULL)
    {
        root = root->lchild; //不断往左，直到没有左孩子
    }
    return root;
}


如果当前结点root为空，说明不存在权值为给定权值x的结点，直接返回
如果当前结点root的权值恰为给定的权值x，说明找到了想要删除的结点，此时进入删除处理

1）如果当前结点root不存在左右孩子，说明是叶子结点，直接删除

2）如果当前结点root存在左孩子，那么在左子树中寻找结点前驱pre，然后让pre的数据覆盖root，接着在左子树中删除结点pre

3）如果当前结点root存在右孩子，那么在右子树中寻找结点后继next，然后让next的数据覆盖root，接着在右子树中删除结点next
如果当前结点root的权值大于给定的权值x，则在左子树中递归删除权值为x的结点
如果当前结点root的权值小于给定的权值x，则在右子树中递归删除权值为x的结点

//删除以root为根结点的树中权值为x的结点
void deleteNode(node* &root, int x)
{
    if(root == NULL) //不存在权值为x的结点
        return;
    if(root->data == x) //找到欲删除结点
    {
        if(root->lchild == NULL && root->rchild == NULL) //叶子结点直接删除
        {
            root = NULL; //把root地址设为NULL，父节点就引用不到它了
        }
        else if(root->lchild != NULL) //左子树不为空时
        {
            node* pre = findMax(root->lchild); //找root前驱
            root->data = pre->data; //用前驱覆盖root
            deleteNode(root->lchild, pre->rchild); //在左子树中删除结点pre
        }
        else //右子树不为空时
        {
            node* next = findMin(root->rchild); //找root后继
            root->data = next->data; //用后继覆盖root
            deleteNode(root->rchild, next->data); //在右子树中删除结点next
        }
        else if(root->data > x)
        {
            deleteNode(root->lchild, x); //在左子树中删除x
        }
        else
        {
            deleteNode(root->rchild, x); //在右子树中删除x
        }
    }
}

二叉查找树的性质
对二叉查找树进行中序遍历，遍历结果是有序的。

         二叉排序树又叫二叉查找树，英文名称是：Binary Sort Tree.  BST的定义就不详细说了，我用一句话概括：左 < 中 < 右。

        根据这个原理，我们可以推断：BST的中序遍历必定是严格递增的。

 

         在建立一个BST之前，大家可以做一下这个题目（很简单的）：

        已知，某树的先序遍历为：4, 2, 1 ,0, 3, 5, 9, 7, 6, 8. 中序遍历为: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. 请画出该树。

 

        我们知道，树的基本遍历有4种方式，分别是：

        先序遍历；中序遍历；后续遍历；层次遍历。事实上，知道任意两种方式，并不能唯一地确定树的结构，但是，只要知道中序遍历和另外任意一种遍历方式，就一定可以唯一地确定一棵树，于是，上面那个题目的答案如下：



 

      下面，我们来看看BST的建立过程，程序如下（没考虑内存泄露）：

#include <iostream>
using namespace std;

// BST的结点
typedef struct node
{
	int key;
	struct node *lChild, *rChild;
}Node, *BST;

// 在给定的BST中插入结点，其数据域为element, 使之称为新的BST
bool BSTInsert(Node * &p, int element)
{
	if(NULL == p) // 空树
	{
		p = new Node;
		p->key = element;
		p->lChild = p->rChild = NULL;
		return true;
	}

	if(element == p->key) // BST中不能有相等的值
		return false;

	if(element < p->key)  // 递归
		return BSTInsert(p->lChild, element);

	return BSTInsert(p->rChild, element); // 递归
}

// 建立BST
void createBST(Node * &T, int a[], int n)
{
	T = NULL; 
	int i;
	for(i = 0; i < n; i++)
	{
		BSTInsert(T, a[i]);
	}
}

// 先序遍历
void preOrderTraverse(BST T)
{
	if(T)
	{
		cout << T->key << " ";
		preOrderTraverse(T->lChild);
		preOrderTraverse(T->rChild);
	}
}

// 中序遍历
void inOrderTraverse(BST T)
{
	if(T)
	{
		inOrderTraverse(T->lChild);
		cout << T->key << " ";
		inOrderTraverse(T->rChild);
	}
}

int main()
{
	int a[10] = {4, 5, 2, 1, 0, 9, 3, 7, 6, 8};
	int n = 10;
	BST T;

	// 并非所有的a[]都能构造出BST,所以，最好对createBST的返回值进行判断
	createBST(T, a, n);

	preOrderTraverse(T);
	cout << endl;

	inOrderTraverse(T);
	cout << endl;

	return 0;
}

 

       那么，怎么知道我们这个程序对不对呢？

       我们输出其先序和中序遍历，这样就可以完全确定这棵树，运行程序。

       发现先序遍历为：4, 2, 1 ,0, 3, 5, 9, 7, 6, 8.

       中序遍历为: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

       好了，这棵树确定了，如上图（已画），那棵树真的是一棵BST, 真的。在后续的博文中，我们会给出二叉排序树的判定方法，期待ing.

 

 

 

 

数据结构进阶(四)二叉排序树(二叉查找树)

    注:构造一棵二叉排序树的目的，其实并不是为了排序(中序遍历)，而是为了提高查找、插入、删除关键字的速度。

定义

    二叉排序树又叫二叉查找树，英文名称是：Binary Sort Tree.BST的定义就不详细说了，我用一句话概括：左 < 中 < 右。 根据这个原理，我们可以推断：BST的中序遍历必定是严格递增的。

    二叉查找树是满足以下条件的二叉树：

    1.左子树上的所有节点值均小于根节点值；

    2.右子树上的所有节点值均不小于根节点值；

    3.左右子树也满足上述两个条件。

    二叉查找树是基于二叉树的，其结点数据结构定义为如下：

 

public class TreeNode {
  public Integer data;
    
  /*该节点的父节点*/ 
  public TreeNode parent;
    
  /*该节点的左子节点*/
  public TreeNode left;
    
  /*该节点的右子节点*/
  public TreeNode right;
    
  public TreeNode(Integer data) {
    this.data = data;
  }
  
  @Override
  public String toString() {
    return "TreeNode [data=" + data + "]";
  }
}

 

    现在明白了什么是二叉查找树，那么二叉查找树的基本操作又是如何来实现的呢？

查找

    在二叉查找树中查找x的过程如下：

    1、若二叉树是空树，则查找失败。

    2、若x等于根结点的数据，则查找成功，否则。

    3、若x小于根结点的数据，则递归查找其左子树，否则。

    4、递归查找其右子树。

   根据上述的步骤，写出其查找操作的代码：

 

  /**
   * @param data
   * @return TreeNode
   */
  public TreeNode findTreeNode(Integer data){
    if(null == root){
      return null;
    }
    TreeNode current = root;
    while(current != null){
      if(current.data > data){
        current = current.left;
      }else if(current.data < data){
        current = current.right;
      }else {
        return current;
      }
        
    }
    return null;
  }

 

插入

    二叉查找树的插入过程如下：

    1.若当前的二叉查找树为空，则插入的元素为根节点；

    2.若插入的元素值小于根节点值，则将元素插入到左子树中；

    3.若插入的元素值不小于根节点值，则将元素插入到右子树中。

 

  /**
   * 往树中加节点  
   * @param data
   * @return Boolean 插入成功返回true
   */
  public Boolean addTreeNode(Integer data) {
  
    if (null == root) {
      root = new TreeNode(data);
      System.out.println("数据成功插入到平衡二叉树中");
      return true;
    }
  
    TreeNode treeNode = new TreeNode(data);// 即将被插入的数据
    TreeNode currentNode = root;
    TreeNode parentNode;
  
    while (true) {
      parentNode = currentNode;// 保存父节点
      // 插入的数据比父节点小
      if (currentNode.data > data) {
        currentNode = currentNode.left;
        // 当前父节点的左子节点为空
        if (null == currentNode) {
          parentNode.left = treeNode;
          treeNode.parent = parentNode;
          System.out.println("数据成功插入到二叉查找树中");
          size++;
          return true;
        }
        // 插入的数据比父节点大
      } else if (currentNode.data < data) {
        currentNode = currentNode.right;
        // 当前父节点的右子节点为空
        if (null == currentNode) {
          parentNode.right = treeNode;
          treeNode.parent = parentNode;
          System.out.println("数据成功插入到二叉查找树中");
          size++;
          return true;
        }
      } else {
        System.out.println("输入数据与节点的数据相同");
        return false;
      }
    }     
}

 

删除

   二叉查找树的删除，分三种情况进行处理：

   1.p为叶子节点，直接删除该节点，再修改其父节点的指针（注意分是根节点和不是根节点），如图a。

   2.p为单支节点（即只有左子树或右子树）。让p的子树与p的父亲节点相连，删除p即可；（注意分是根节点和不是根节点）；如图b。

   3.p的左子树和右子树均不空。找到p的后继y，因为y一定没有左子树，所以可以删除y，并让y的父亲节点成为y的右子树的父亲节点，并用y的值代替p的值；或者方法二是找到p的前驱x，x一定没有右子树，所以可以删除x，并让x的父亲节点成为y的左子树的父亲节点。如图c。







 

美文美图