devbox
花生_TL007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java 数据结构之二叉搜索树(头歌平台，详细注释)_java n叉搜索树

作者：花生_TL007 | 2024-06-04 01:47:12

赞

踩

java n叉搜索树

目录

第1关：二叉搜索树的介绍与构建

任务描述

相关知识

二叉搜索树

什么是二叉搜索树

二叉搜索树的构建

代码： 

第2关：二叉搜索树的删除

任务描述

相关知识

后继结点

二叉搜索树的删除

代码： 

第3关：二叉搜索树的查找

任务描述

相关知识

二叉搜索树的查找

代码： 

第1关：二叉搜索树的介绍与构建

任务描述

顾名思义，一棵二叉搜索树是以一棵二叉树来组织的，但是在组织的时候需要满足一些特定的性质。

本关任务：构建一棵二叉搜索树，向其中添加结点。

相关知识
二叉搜索树
什么是二叉搜索树

二叉搜索树(binary search tree)，又称二叉排序树，它或者是空树，或者是满足如下性质的二叉树：

  1. 若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
  2. 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
  3. 左、右子树本身又各是一棵二叉排序树。

简而言之，二叉搜索树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。

下图是两棵二叉搜索树：

可以看到，对于树中的任何结点，其值大于左结点，小于右结点。 如果我们以中序遍历遍历一棵二叉搜索树，所得到的中序序列是一个递增有序序列。

上图二叉搜索树的中序遍历结果均为2 3 4 5 7 8。

二叉搜索树的构建

构建一棵二叉搜索树，实际是构建一棵二叉树，但在添加结点时，需要满足二叉搜索树的性质。 以输入序列5 3 7 2 4 8为例，构建一棵二叉搜索树。如下图所示：

(1)二叉搜索树为空，5为根结点；

(2)输入值3比根结点5小，且此时根结点的左结点为空，所以3添加为根结点的左结点；

(3)输入值7比根结点5大，添加为根结点的右结点；

(4)输入值2比根结点5小，应添加至根结点的左结点，但此时根结点的左结点是3，2与3比较，小于，所以添加为3的左结点；

(5)输入值4比根结点5小，应添加至根结点的左结点，但此时根结点的左结点是3，4与3比较，大于，所以添加为3的右结点；

(6)输入值8比根结点5大，应添加至根结点的右结点，但此时根结点的左结点是7，8与7比较，大于，所以添加为7的右结点。

循环中小于当前需要置入结点放左边，大于当前置入结点放右边

代码： 
  1. package step1;
  2.  
  3. /**
  4.  * Created by zengpeng on 2018/3/3.
  5.  */
  6. public class BSTree {
  7.  
  8.     private TreeNode root;//根结点
  9.  
  10.     public BSTree() {
  11.         root = null;
  12.     }
  13.  
  14.     /**
  15.      * 向树root中插入key
  16.      *
  17.      * @param key 要插入的值
  18.      */
  19.     public void insert(int key) {
  20.         /********** Begin *********/  
  21.     //二叉搜索树，严格要求左子树的值小于中间结点，右子树的值大于中间结点
  22.     TreeNode x = root;//创建一个结点x，储存根结点root
  23.     TreeNode p = null;//创建一个结点p，初始化为空
  24.     while (x != null) {//如果x不为空则继续，找到需要插入的结点的前一个位置
  25.     p = x;//用p储存x结点
  26.     if (key < x.item) {//如果值小于当前结点的值，则进入左子树
  27.     x = x.leftChild;//将左子树储存x
  28.     } else {//如果值大于当前结点的值，则进入右子树
  29.     x = x.rightChild;//将右子树储存x
  30.     }
  31.     }
  32.     //找到位置后再进行判断，应该构建左还是右
  33.     if (null == p) {//如果p为空，代表没有根结点
  34.     root = new TreeNode(key);//根结点储存需要构建的当前结点
  35.     } else if (key < p.item) {//如果值小于p结点的值
  36.     p.leftChild = new TreeNode(key);//p的左子树构建当前结点
  37.     } else {//如果值大于p结点的值
  38.       p.rightChild = new TreeNode(key);//p的右子树构建当前结点
  39.     }
  40.         /********** End *********/
  41.     }
  42.  
  43.     public void preOrder() {
  44.         preOrder(root);
  45.     }
  46.  
  47.     public void inOrder() {
  48.         inOrder(root);
  49.     }
  50.  
  51.     public void postOrder(){
  52.         postOrder(root);
  53.     }
  54.  
  55.     private void preOrder(TreeNode node) {
  56.         if (node != null) {
  57.             System.out.print(node.item + " ");
  58.             preOrder(node.leftChild);
  59.             preOrder(node.rightChild);
  60.         }
  61.     }
  62.  
  63.     private void inOrder(TreeNode node) {
  64.         if (node != null) {
  65.             inOrder(node.leftChild);
  66.             System.out.print(node.item + " ");
  67.             inOrder(node.rightChild);
  68.         }
  69.     }
  70.  
  71.     private void postOrder(TreeNode node) {
  72.         if (node != null) {
  73.             postOrder(node.leftChild);
  74.             postOrder(node.rightChild);
  75.             System.out.print(node.item + " ");
  76.         }
  77.     }
  78.  
  79.  
  80.     public static class TreeNode {
  81.         private TreeNode leftChild;
  82.         private TreeNode rightChild;
  83.         private int item;
  84.  
  85.         public TreeNode(int item) {
  86.             this(null, null, item);
  87.         }
  88.  
  89.         public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
  90.             this.leftChild = leftChild;
  91.             this.rightChild = rightChild;
  92.             this.item = item;
  93.         }
  94.     }
  95. }

以下是测试样例：

测试输入：

  1. 3 2 1 0 21

预期输出：

  1. 前序遍历: 3 2 1 0 21
  2. 中序遍历: 0 1 2 3 21
  3. 后序遍历: 0 1 2 21 3

第2关：二叉搜索树的删除

任务描述

在上一关，我们构建了一棵二叉搜索树，并且可以向其添加结点数据，本关将实现在二叉搜索树的删除功能。

本关任务是：实现二叉搜索树的删除功能。

相关知识
后继结点

给定一棵二叉搜索树中的一个结点，有时候需要按中序遍历的次序查找它的后继。如果所有的关键字互不相同，则一个结点x的后继结点是大于x的最小关键字的结点。

上图中，结点66的后继结点为68。20的后继结点为66。

二叉搜索树的删除

从一棵二叉搜索树T中删除一个结点z的整个策略可分为三个基本情况：

  • 如果z没有孩子结点，那么只是简单地将它删除，并修改它的父结点；
  • 如果z只有一个孩子结点，那么将这个孩子提升到树中z的位置上，并修改z的父结点，使其指向z的孩子结点；
  • 如果z有两个孩子，那么找z的后继结点y，并让y占据树中z的位置。z的原来右子树部分成为y的新的右子树，并且z的左子树成为y的新的左子树。（根据二叉搜索树的性质，后继结点y一定在z的右子树中）。

下列是几种情况的图示： （1）删除没有子结点的结点；

因为结点150没有孩子结点，所以直接把其删掉。

（2）删除有一个子结点的结点；

结点50有一个孩子结点，我们只需把其孩子结点提升到结点50的位置即可。

（3）删除有两个子结点的结点；

对于有两个子结点的结点50，在其右子树中找到其后继结点66，使后继结点相应的替换结点50。

删除的方法是如果有左子树，以左子树中最大值作为新的树根，否则，以右子树最小值作为树根。

代码： 
  1. package step2;
  2.  
  3. /**
  4.  * Created by zengpeng on 2018/3/14.
  5.  */
  6. public class BSTree {
  7.     private TreeNode root;//根结点
  8.  
  9.     public BSTree() {
  10.         root = null;
  11.     }
  12.  
  13.     /**
  14.      * 向树root中插入a
  15.      *
  16.      * @param key 要插入的值
  17.      */
  18.     public void insert(int key) {
  19.         TreeNode x = root;
  20.         TreeNode p = null;//始终指向x的父结点
  21.         while (x != null) {
  22.             p = x;
  23.             if (key < x.item) {
  24.                 x = x.leftChild;
  25.             } else {
  26.                 x = x.rightChild;
  27.             }
  28.         }
  29.         if (null == p) {//空树
  30.             root = new TreeNode(key);
  31.         } else if (key < p.item) {
  32.             p.leftChild = new TreeNode(key);
  33.         } else {
  34.             p.rightChild = new TreeNode(key);
  35.         }
  36.     }
  37.  
  38.     /**
  39.      * 在树root中删除结点key
  40.      *
  41.      * @param key
  42.      * @return
  43.      */
  44.     public void delete(int key) {
  45.         root = delete(root, key);
  46.     }
  47.  
  48.     private TreeNode delete(TreeNode x, int key) {
  49.         /********** Begin *********/
  50.         if (x == null)//x为根结点，如果根结点为空
  51.             return null;//返回空
  52.             //递归实现
  53.         if (key < x.item) {//如果删除的值小于当前结点
  54.         x.leftChild = delete(x.leftChild, key);//再次进入delete方法，往左子树继续搜寻需要删除的结点
  55.         } else if (key > x.item) {
  56.         x.rightChild = delete(x.rightChild, key);//再次进入delete方法，往右子树继续搜寻需要删除的结点
  57.         } else {//如果等于，由于是二叉搜索树需要严格满足条件
  58.         if (x.leftChild == null) return x.rightChild;//如果左子树为空，返回右子树的结点
  59.         if (x.rightChild == null) return x.leftChild;//如果右子树为空，返回左子树的结点
  60.         TreeNode t = x;//用t储存x结点
  61.         x = min(t.rightChild);//寻找t右子树的最小值结点，并用x储存，需要用最小结点代替要被删除的结点的位置
  62.         x.rightChild = deleteMin(t.rightChild);//删除找到的最小结点
  63.         x.leftChild = t.leftChild;//让最小结点的左子树变为要删除的结点的左子树
  64. }
  65.         return x;//返回
  66.  
  67.  
  68.         /********** End *********/
  69.     }
  70.  
  71.     /**
  72.      * 删除树x中的最小结点
  73.      *
  74.      * @param x
  75.      * @return
  76.      */
  77.     private TreeNode deleteMin(TreeNode x) {
  78.         if (x.leftChild == null) return x.rightChild;
  79.         x.leftChild = deleteMin(x.leftChild);
  80.         return x;
  81.     }
  82.  
  83.     /**
  84.      * 查找树x中的最小结点
  85.      *
  86.      * @param x
  87.      * @return
  88.      */
  89.     private TreeNode min(TreeNode x) {
  90.         TreeNode p = x;
  91.         while (p.leftChild != null) {
  92.             p = p.leftChild;
  93.         }
  94.         return p;
  95.     }
  96.  
  97.     public void preOrder() {
  98.         preOrder(root);
  99.     }
  100.  
  101.     private void preOrder(TreeNode node) {
  102.         if (node != null) {
  103.             System.out.print(node.item + " ");
  104.             preOrder(node.leftChild);
  105.             preOrder(node.rightChild);
  106.         }
  107.     }
  108.  
  109.     public void inOrder() {
  110.         inOrder(root);
  111.     }
  112.  
  113.     private void inOrder(TreeNode node) {
  114.         if (node != null) {
  115.             inOrder(node.leftChild);
  116.             System.out.print(node.item + " ");
  117.             inOrder(node.rightChild);
  118.         }
  119.     }
  120.  
  121.     public void postOrder() {
  122.         postOrder(root);
  123.     }
  124.  
  125.     private void postOrder(TreeNode node) {
  126.         if (node != null) {
  127.             postOrder(node.leftChild);
  128.             postOrder(node.rightChild);
  129.             System.out.print(node.item + " ");
  130.         }
  131.     }
  132.  
  133.  
  134.     public static class TreeNode {
  135.         private TreeNode leftChild;
  136.         private TreeNode rightChild;
  137.         private int item;
  138.  
  139.         public TreeNode(int item) {
  140.             this(null, null, item);
  141.         }
  142.  
  143.         public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
  144.             this.leftChild = leftChild;
  145.             this.rightChild = rightChild;
  146.             this.item = item;
  147.         }
  148.     }
  149. }

以下是测试样例：

测试输入：3 2 1 0 21 预期输出：

  1. 前序遍历: 3 2 1 0 21
  2. 中序遍历: 0 1 2 3 21
  3. 后序遍历: 0 1 2 21 3
  4. 前序遍历: 21 2 1 0
  5. 中序遍历: 0 1 2 21
  6. 后序遍历: 0 1 2 21

第3关：二叉搜索树的查找

任务描述

我们经常需要查找一个存储在二叉搜索树中的关键字，本关卡将讨论并实现查找功能。

本关任务：实现二叉搜索树的查找功能，如果指定的元素x存在树中则返回true，否则返回false。

相关知识
二叉搜索树的查找

给定一个关键字key，我们要判断key是否在指定的二叉搜索树T中，如果存在则返回true，不存在则返回false。

这个查找过程从树根结点开始，并沿着这棵树中的一条简单路径向下进行，如下图所示。对于遇到的每个结点x，比较key和x。如果两个关键字相等，查找终止。如果key小于x，查找在x的左子树中继续，因为二叉搜索树的性质意味着key不可能被存储在x的右子树中。对称地，如果key大于x，查找在右子树中继续。

为了查找上图中的关键字为13的结点，从树根开始沿着15->6->7->13路径进行查找。

代码： 
  1. package step3;
  2.  
  3. /**
  4.  * Created by zengpeng on 2018/3/14.
  5.  */
  6. public class BSTree {
  7.     private TreeNode root;//根结点
  8.  
  9.     public BSTree() {
  10.         root = null;
  11.     }
  12.  
  13.     /**
  14.      * 向树root中插入a
  15.      *
  16.      * @param key    要插入的值
  17.      */
  18.     public void insert(int key) {
  19.         TreeNode x = root;
  20.         TreeNode p = null;//始终指向x的父结点
  21.         while (x != null) {
  22.             p = x;
  23.             if (key < x.item) {
  24.                 x = x.leftChild;
  25.             } else {
  26.                 x = x.rightChild;
  27.             }
  28.         }
  29.         if (null == p) {//空树
  30.             root = new TreeNode(key);
  31.         } else if (key < p.item) {
  32.             p.leftChild = new TreeNode(key);
  33.         } else {
  34.             p.rightChild = new TreeNode(key);
  35.         }
  36.     }
  37.  
  38.     /**
  39.      * 判断树root中是否包含key，包含则返回true，不包含返回false
  40.      *
  41.      * @param key
  42.      * @return
  43.      */
  44.     public boolean search(int key) {
  45.         /********** Begin *********/
  46.         TreeNode p=root;//用p结点储存根结点
  47.         while(p!=null&&key!=p.item)//如果p不为空，并且要查找的值不为p结点的值
  48.         {
  49.         if(key<p.item)//如果要查找的值小于p结点的值
  50.         {
  51.         p=p.leftChild;//让p储存为p的左子树，因为小于p结点值的，结点都在左边
  52.         }
  53.         else//如果要查找的值大于p结点的值
  54.         {
  55.         p=p.rightChild;//让p储存为p的大子树，因为大于p结点值的，结点都在右边
  56.         }
  57.         }
  58.         if(p==null)//如果p为空则表示没找到
  59.         return false;//返回false
  60.         else//找到了
  61.         return true;//返回true
  62.         /********** End *********/
  63.     }
  64.  
  65.  
  66.     /**
  67.      * 在树root中删除结点key
  68.      *
  69.      * @param key
  70.      * @return
  71.      */
  72.     public void delete(int key) {
  73.         root = delete(root, key);
  74.     }
  75.  
  76.     private TreeNode delete(TreeNode x, int key) {
  77.         if (x == null) {
  78.             return null;
  79.         }
  80.  
  81.         if (key < x.item) {
  82.             x.leftChild = delete(x.leftChild, key);
  83.         } else if (key > x.item) {
  84.             x.rightChild = delete(x.rightChild, key);
  85.         } else {
  86.             if (x.leftChild == null) return x.rightChild;
  87.             if (x.rightChild == null) return x.leftChild;
  88.             TreeNode t = x;
  89.             x = min(t.rightChild);
  90.             x.rightChild = deleteMin(t.rightChild);
  91.             x.leftChild = t.leftChild;
  92.         }
  93.  
  94.         return x;
  95.     }
  96.  
  97.     /**
  98.      * 删除树x中的最小结点
  99.      * @param x
  100.      * @return
  101.      */
  102.     private TreeNode deleteMin(TreeNode x) {
  103.         if (x.leftChild == null) return x.rightChild;
  104.         x.leftChild = deleteMin(x.leftChild);
  105.         return x;
  106.     }
  107.  
  108.     /**
  109.      * 查找树x中的最小结点
  110.      *
  111.      * @param x
  112.      * @return
  113.      */
  114.     private TreeNode min(TreeNode x) {
  115.         TreeNode p = x;
  116.         while (p.leftChild != null) {
  117.             p = p.leftChild;
  118.         }
  119.         return p;
  120.     }
  121.  
  122.     public void preOrder() {
  123.         preOrder(root);
  124.     }
  125.  
  126.     public void inOrder() {
  127.         inOrder(root);
  128.     }
  129.  
  130.     public void postOrder() {
  131.         postOrder(root);
  132.     }
  133.  
  134.     private void preOrder(TreeNode node) {
  135.         if (node != null) {
  136.             System.out.print(node.item + " ");
  137.             preOrder(node.leftChild);
  138.             preOrder(node.rightChild);
  139.         }
  140.     }
  141.  
  142.     private void inOrder(TreeNode node) {
  143.         if (node != null) {
  144.             inOrder(node.leftChild);
  145.             System.out.print(node.item + " ");
  146.             inOrder(node.rightChild);
  147.         }
  148.     }
  149.  
  150.     private void postOrder(TreeNode node) {
  151.         if (node != null) {
  152.             postOrder(node.leftChild);
  153.             postOrder(node.rightChild);
  154.             System.out.print(node.item + " ");
  155.         }
  156.     }
  157.  
  158.  
  159.     public static class TreeNode {
  160.         private TreeNode leftChild;
  161.         private TreeNode rightChild;
  162.         private int item;
  163.  
  164.         public TreeNode(int item) {
  165.             this(null, null, item);
  166.         }
  167.  
  168.         public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
  169.             this.leftChild = leftChild;
  170.             this.rightChild = rightChild;
  171.             this.item = item;
  172.         }
  173.     }
  174. }

以下是测试样例：

测试输入：1 5 4 3 2 6 预期输出：

  1. 删除前树中的结点：1 5 4 3 2 6
  2. 删除后树中的结点：5 4 3 2
  3. false true true true true false

注意：二叉搜索树中，如果存在左右子树，则左子树上的结点都小于根结点，右结点子树上的结点都大于根结点，严格要求左子树小于根结点，右子树大于根结点

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/669854
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号