精华内容
下载资源
问答
  • 二叉排序树(二叉查找树、二叉搜索树)

    万次阅读 多人点赞 2019-05-03 00:16:08
    什么是二叉查找树: 根节点的值大于其左子树中任意一个节点的值,小于其右节点中任意一节点的值,这一规则适用于二叉查找树中的每一个节点。 本文章重点来讨论一下关于二叉查找树删除节点的问题。 有一下二叉查找树...

    什么是二叉查找树:
    根节点的值大于其左子树中任意一个节点的值,小于其右节点中任意一节点的值,这一规则适用于二叉查找树中的每一个节点。
    本文章重点来讨论一下关于二叉查找树删除节点的问题。
    有一下二叉查找树,如图:
    在这里插入图片描述
    在删除节点的时候我们只需考虑一下三种情况:
    (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);
        }
    }
    
    
    展开全文
  • 二叉查找树

    2021-01-13 10:30:57
    二叉查找树的定义 二叉查找树: 要么二叉查找树是一棵空树 要么二叉查找树由根结点、左子树、右子树组成,其中左子树和右子树都是二叉查找树,且左子树上所有结点的数据域均小于或等于根结点的数据域,右子树上所有...

    二叉查找树的定义

    二叉查找树:

    1. 要么二叉查找树是一棵空树
    2. 要么二叉查找树由根结点、左子树、右子树组成,其中左子树和右子树都是二叉查找树,且左子树上所有结点的数据域均小于或等于根结点的数据域,右子树上所有结点的数据域均大于根结点的数据域。
      在这里插入图片描述

    二叉查找树的基本操作

    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;
    }
    
    1. 如果当前结点root为空,说明不存在权值为给定权值x的结点,直接返回
    2. 如果当前结点root的权值恰为给定的权值x,说明找到了想要删除的结点,此时进入删除处理
      1)如果当前结点root不存在左右孩子,说明是叶子结点,直接删除
      2)如果当前结点root存在左孩子,那么在左子树中寻找结点前驱pre,然后让pre的数据覆盖root,接着在左子树中删除结点pre
      3)如果当前结点root存在右孩子,那么在右子树中寻找结点后继next,然后让next的数据覆盖root,接着在右子树中删除结点next
    3. 如果当前结点root的权值大于给定的权值x,则在左子树中递归删除权值为x的结点
    4. 如果当前结点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之前,大家可以做一下这个...

             二叉排序树又叫二叉查找树,英文名称是: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的定义...

     

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

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

    定义

        二叉排序树又叫二叉查找树,英文名称是: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。

     

    美文美图

     

    展开全文
  • Algorithm:树相关算法(BBT/BST/B树/R树)简介(二叉查找树二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C++语言实现 目录 树的基础知识 1、二叉树的遍—前序、中序、后序 一、二叉树 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,510
精华内容 8,604
关键字:

二叉查找树