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

头歌Java数据结构实训作业——二叉树_头歌实践教学平台顺序存储结构二叉树答案

作者：Gausst松鼠会 | 2024-05-14 20:26:01

赞

踩

头歌实践教学平台顺序存储结构二叉树答案

Java 数据结构之二叉树

二叉树的定义：

二叉树是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。这是二叉树的递归定义。

二叉树的遍历：

所谓遍历，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题

对于二叉树的遍历，可进一步分为三种:

①前序遍历(根左右):对于每一棵子树，先访问该节点，然后是左子树，最后是右子树

②中序遍历(左根右):对于每一棵子树，先访问左子树，然后是该节点，最后是右子树

③后序遍历(左右根):对于每一棵子树，先访问左子树，然后是右子树，最后是该节点

其中递归是实现上三种遍历逻辑最简单的方式

第1关：二叉树的实现之前序遍历

1.任务描述

本关任务：完成用二叉链表存储的二叉树的前序遍历算法。

  • 补全preOrder(TreeNode root)方法，实现二叉树的前序遍历功能，并输出结点的值。

2.本关答案

        本关要求我们实现二叉树的前序遍历，我们根据递归来实现根左右的遍历方式

  1. package step1;
  2.  
  3. /**
  4.  * Created by zengpeng on 2018/2/9.
  5.  */
  6. public class BinaryTree {
  7.  
  8.     private TreeNode root;//根节点
  9.  
  10.     public BinaryTree() {
  11.         root = null;
  12.     }
  13.  
  14.     public void preOrder(TreeNode root) {
  15.         /********** Begin *********/
  16.         //递归实现  根左右
  17.         if(root==null){
  18.             return;
  19.         }
  20.         System.out.println(root.item);
  21.         preOrder(root.leftChild);
  22.         preOrder(root.rightChild);
  23.         
  24.         /********** End *********/
  25.     }
  26.  
  27.     /**
  28.      *以数组arr的数据，依次从上至下，从左至右构建一颗二叉树
  29.      *
  30.      * @param arr
  31.      * @param n
  32.      * @return
  33.      */
  34.     public TreeNode createTree(int arr[]) {
  35.         TreeNode tmp[] = new TreeNode[arr.length + 1];
  36.         for (int k = 1; k <= arr.length; k++) {
  37.             TreeNode node = new TreeNode(arr[k - 1]);
  38.             tmp[k] = node;
  39.             if (k == 1) {
  40.                 root = node;
  41.             } else {
  42.                 int j = k / 2;
  43.                 if (k % 2 == 0) {
  44.                     tmp[j].leftChild = node;
  45.                 } else {
  46.                     tmp[j].rightChild = node;
  47.                 }
  48.             }
  49.         }
  50.  
  51.         return root;
  52.     }
  53.  
  54.     public static class TreeNode {
  55.         private TreeNode leftChild;
  56.         private TreeNode rightChild;
  57.         private int item;
  58.  
  59.         public TreeNode(int item) {
  60.             this(null, null, item);
  61.         }
  62.  
  63.         public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
  64.             this.leftChild = leftChild;
  65.             this.rightChild = rightChild;
  66.             this.item = item;
  67.         }
  68.     }
  69.  
  70. }

第2关：二叉树的实现之中序遍历

1.任务描述

本关任务：实现以二叉链表存储的二叉树的中序遍历算法。

补全inOrder(TreeNode root)方法，实现二叉树的中序遍历功能，并输出结点的值

2.本关答案

        本关要求我们实现二叉树的中序遍历，我们根据递归来实现左根右的遍历方式

  1. package step2;
  2.  
  3. /**
  4.  * Created by zengpeng on 2018/2/12.
  5.  */
  6. public class BinaryTree {
  7.  
  8.     private TreeNode root;//根节点
  9.  
  10.     public BinaryTree() {
  11.         root = null;
  12.     }
  13.  
  14.     public void inOrder(TreeNode root) {
  15.         /********** Begin *********/
  16.         //递归实现  左根右
  17.         if(root==null){
  18.             return;
  19.         }
  20.         inOrder(root.leftChild);
  21.         System.out.println(root.item);
  22.         inOrder(root.rightChild);
  23.        
  24.         /********** End *********/
  25.     }
  26.  
  27.     /**
  28.      * 以数组arr的数据，依次从上至下，从左至右构建一颗二叉树
  29.      *
  30.      * @param arr
  31.      * @param n
  32.      * @return
  33.      */
  34.     public TreeNode createTree(int arr[]) {
  35.         TreeNode tmp[] = new TreeNode[arr.length + 1];
  36.         for (int k = 1; k <= arr.length; k++) {
  37.             TreeNode node = new TreeNode(arr[k - 1]);
  38.             tmp[k] = node;
  39.             if (k == 1) {
  40.                 root = node;
  41.             } else {
  42.                 int j = k / 2;
  43.                 if (k % 2 == 0) {
  44.                     tmp[j].leftChild = node;
  45.                 } else {
  46.                     tmp[j].rightChild = node;
  47.                 }
  48.             }
  49.         }
  50.  
  51.         return root;
  52.     }
  53.  
  54.     public static class TreeNode {
  55.         private TreeNode leftChild;
  56.         private TreeNode rightChild;
  57.         private int item;
  58.  
  59.         public TreeNode(int item) {
  60.             this(null, null, item);
  61.         }
  62.  
  63.         public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
  64.             this.leftChild = leftChild;
  65.             this.rightChild = rightChild;
  66.             this.item = item;
  67.         }
  68.     }
  69. }

第3关： 二叉树的实现之后序遍历

1.任务描述

本关任务：实现以二叉链表存储的二叉树的后序遍历算法。

  • 补全postOrder(TreeNode root)方法，实现后序遍历功能，并输出结点值。

2.本关答案

        本关要求我们实现二叉树的后序遍历，我们根据递归来实现左右根的遍历方式

  1. package step3;
  2.  
  3. /**
  4.  * Created by zengpeng on 2018/2/12.
  5.  */
  6. public class BinaryTree {
  7.     private TreeNode root;//根节点
  8.  
  9.     public BinaryTree() {
  10.         root = null;
  11.     }
  12.  
  13.     public void postOrder(TreeNode root) {
  14.         /********** Begin *********/
  15.         //递归实现  左右根
  16.         if(root==null){
  17.             return;
  18.         }
  19.         postOrder(root.leftChild);
  20.         postOrder(root.rightChild);
  21.         System.out.println(root.item);
  22.  
  23.         /********** End *********/
  24.     }
  25.  
  26.     /**
  27.      * 以数组arr的数据，依次从上至下，从左至右构建一颗二叉树
  28.      *
  29.      * @param arr
  30.      * @param n
  31.      * @return
  32.      */
  33.     public TreeNode createTree(int arr[]) {
  34.         TreeNode tmp[] = new TreeNode[arr.length + 1];
  35.         for (int k = 1; k <= arr.length; k++) {
  36.             TreeNode node = new TreeNode(arr[k - 1]);
  37.             tmp[k] = node;
  38.             if (k == 1) {
  39.                 root = node;
  40.             } else {
  41.                 int j = k / 2;
  42.                 if (k % 2 == 0) {
  43.                     tmp[j].leftChild = node;
  44.                 } else {
  45.                     tmp[j].rightChild = node;
  46.                 }
  47.             }
  48.         }
  49.  
  50.         return root;
  51.     }
  52.  
  53.     public static class TreeNode {
  54.         private TreeNode leftChild;
  55.         private TreeNode rightChild;
  56.         private int item;
  57.  
  58.         public TreeNode(int item) {
  59.             this(null, null, item);
  60.         }
  61.  
  62.         public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
  63.             this.leftChild = leftChild;
  64.             this.rightChild = rightChild;
  65.             this.item = item;
  66.         }
  67.     }
  68. }

Java 数据结构之二叉搜索树

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

1.任务描述

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

  • 平台将创建用户补全后的BSTree类的对象；
  • 调用对象的insert(int key)方法，向树中添加结点；
  • 调用对象的preOrder()方法执行前序遍历；
  • 调用对象的inOrder()方法执行中序遍历；
  • 调用对象的postOrder()方法执行后序遍历；
  • 接着根据程序的输出判断程序是否正确。

2.相关知识

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

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

33061458aabb4558b80e430bb4b3e8fc.png

3.思路分析

        本关要求我们实现二叉树的插入操作insert

        首先我们来分析BSTree类中已经给我们了的方法

        首先就是节点类TreeNode：其中该类是BSTree的静态内部类，外部类可直接调用该内部类的成员变量和方法

  1. //节点内部类
  2.     public static class TreeNode {
  3.         private TreeNode leftChild;//左孩子
  4.         private TreeNode rightChild;//右孩子
  5.         private int item;
  6.  
  7.         public TreeNode(int item) {
  8.             this(null, null, item);
  9.         }
  10.  
  11.         public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
  12.             this.leftChild = leftChild;
  13.             this.rightChild = rightChild;
  14.             this.item = item;
  15.         }
  16.     }

        然后就是BSTree的成员变量以及方法：一个成员变量root表示该树的根节点，空参的构造方法表示构建一个空树；然后是三种基本的遍历方式

        题目要求我们补全插入节点的代码

        我们根据二叉搜索树的性质，我们从根节点root开始一直向下寻找合适的插入位置，若插入的节点小于比较的节点，那么我们就向比较节点的左孩子处向下寻找；若插入的节点大于比较的节点，那么我们就向比较节点的右孩子处向下寻找，直到找到合适的位置

4.本关答案

  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.        TreeNode newnode=new TreeNode(key);
  22.        if(root==null){//树为空,要插入的节点即为根节点
  23.            root=newnode;
  24.        }else{
  25.            TreeNode cur=root;
  26.            while(cur!=null){
  27.                 if(cur.item==key){//已经存在
  28.                     return;
  29.                 }else if(key<cur.item){//在该节点的左边
  30.                     if(cur.leftChild==null){
  31.                         cur.leftChild=newnode;
  32.                     }else{//继续向左找
  33.                         cur=cur.leftChild;
  34.                     }
  35.                 }else if(key>cur.item){//在该节点的右边
  36.                     if(cur.rightChild==null){
  37.                         cur.rightChild=newnode;
  38.                     }else{//继续向右找
  39.                         cur=cur.rightChild;
  40.                     }
  41.                 }
  42.            }
  43.         }
  44.                  
  45.         /********** End *********/
  46.     }
  47.  
  48.     //前序遍历
  49.     public void preOrder() {
  50.         preOrder(root);
  51.     }
  52.     //中序遍历
  53.     public void inOrder() {
  54.         inOrder(root);
  55.     }
  56.     //后序遍历
  57.     public void postOrder(){
  58.         postOrder(root);
  59.     }
  60.  
  61.     private void preOrder(TreeNode node) {
  62.         if (node != null) {
  63.             System.out.print(node.item + " ");
  64.             preOrder(node.leftChild);
  65.             preOrder(node.rightChild);
  66.         }
  67.     }
  68.  
  69.     private void inOrder(TreeNode node) {
  70.         if (node != null) {
  71.             inOrder(node.leftChild);
  72.             System.out.print(node.item + " ");
  73.             inOrder(node.rightChild);
  74.         }
  75.     }
  76.  
  77.     private void postOrder(TreeNode node) {
  78.         if (node != null) {
  79.             postOrder(node.leftChild);
  80.             postOrder(node.rightChild);
  81.             System.out.print(node.item + " ");
  82.         }
  83.     }
  84.  
  85.     //节点内部类
  86.     public static class TreeNode {
  87.         private TreeNode leftChild;
  88.         private TreeNode rightChild;
  89.         private int item;
  90.  
  91.         public TreeNode(int item) {
  92.             this(null, null, item);
  93.         }
  94.  
  95.         public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
  96.             this.leftChild = leftChild;
  97.             this.rightChild = rightChild;
  98.             this.item = item;
  99.         }
  100.     }
  101. }

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

1.任务描述

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

  • 平台将创建用户补全后的BSTree类的对象；
  • 调用对象的insert(int key)()方法，构建一棵二叉搜索树；
  • 调用对象的遍历方法，输出删除元素前的各种遍历结果；
  • 调用对象的delete(int key)方法，删除元素key；
  • 调用对象的遍历方法，输出删除元素后的各种遍历结果；
  • 接着根据程序的输出判断程序是否正确。

2.相关知识

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

  • 如果z没有孩子结点，那么只是简单地将它删除，并修改它的父结点；
  • 如果z只有一个孩子结点，那么将这个孩子提升到树中z的位置上，并修改z的父结点，使其指向z的孩子结点；
  • 如果z有两个孩子，那么找z右子树的最小节点代替z,最后删除替换后的最小节点

17fdec8f9d584dd782a623bb611ea3b6.png

e9c9d4cce986440ebe1f14784ff6640e.png

510d071759284a5a91e29673ebb491f5.png

3.思路分析

        我们可以观察到，在第三种情况下（删除节点有左右两个节点），当我们将删除节点右子树的最小节点代替删除节点后，我们还需删除替换后的最小节点位置，但此时删除的情况就是情况一，二的一种，那么我们就可以从第三种情况开始，若存在第三种情况，那么我们就可以将其转化为第一二种情况的一种

        那么具体怎么操作呢？以下图为例：

75d8a5855f874fa3a7dd7b5fa15ec66e.png

        首先要删除一个节点，就要知道它的父节点以及其孩子节点，因此首先我们要先找到删除节点的父节点

833d478f07214238b4323110463fea21.png

        然后我们从第三种情况开始考虑：找到删除节点右子树的最小节点并与删除节点替换，将其转换为一二种情况

90cd8dbabba8469b8582aadb5554e239.png

       

        那么此时要删除的节点以及其父节点就变了，我们要重新记录

c973b79f2bad456c9345b7268f6396b4.png

        最后我们就要寻找删除节点的孩子节点，并将其父节点与其孩子节点相连，这样就完成了节点的删除，但我们需要考虑的是，若删除的是根节点，那么我们就直接返回其孩子节点即可，不用再更改其父节点的指针了（根节点的父节点为null）

8e7d9e5f2ff94e92973498fe3d0ed0b3.png

        当然特殊情况（parent==null）不会包括第三种情况，因为经转化后删除节点必定有父节点；因此该特殊情况只存在于第一二中

4.本关答案

  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.         //三种情况
  51.         TreeNode cur=x;
  52.         TreeNode parent=null;
  53.         while(x!=null && x.item!=key){
  54.             parent=x;
  55.             if(key<x.item){
  56.                 x=x.leftChild;
  57.             }else{
  58.                 x=x.rightChild;
  59.             }
  60.         }
  61.         //删除节点不存在
  62.         if(x==null) return cur;
  63.         //第三种情况:将删除节点与其右子树最小节点交换，并删除交换后的最小节点
  64.         if(x.leftChild!=null && x.rightChild!=null){
  65.             TreeNode mininode=x.rightChild;
  66.             TreeNode miniparent=x;
  67.             while(mininode.leftChild!=null){
  68.                 miniparent=mininode;
  69.                 mininode=mininode.leftChild;
  70.             }
  71.             //删除交换后的最小节点位置，转化为其他两种情况
  72.             x.item=mininode.item;
  73.             parent=miniparent;
  74.             x=mininode;
  75.         }
  76.             //最后两种情况，找删除节点的孩子节点
  77.             TreeNode child;
  78.             if(x.rightChild!=null){
  79.                 child=x.rightChild;
  80.             }else if(x.leftChild!=null){
  81.                 child=x.leftChild;
  82.             }else{
  83.                 child=null;
  84.             }
  85.             //删除的是根节点
  86.             if(parent==null) return child;
  87.             //删除节点
  88.             if(parent.leftChild==x){
  89.                 parent.leftChild=child;
  90.             }else if(parent.rightChild==x){
  91.                 parent.rightChild=child;
  92.             }
  93.         
  94.         return cur;
  95.  
  96.  
  97.  
  98.         /********** End *********/
  99.     }
  100.  
  101.     /**
  102.      * 删除树x中的最小结点
  103.      *
  104.      * @param x
  105.      * @return
  106.      */
  107.     private TreeNode deleteMin(TreeNode x) {
  108.         if (x.leftChild == null) return x.rightChild;
  109.         x.leftChild = deleteMin(x.leftChild);
  110.         return x;
  111.     }
  112.  
  113.     /**
  114.      * 查找树x中的最小结点
  115.      *
  116.      * @param x
  117.      * @return
  118.      */
  119.     private TreeNode min(TreeNode x) {
  120.         TreeNode p = x;
  121.         while (p.leftChild != null) {
  122.             p = p.leftChild;
  123.         }
  124.         return p;
  125.     }
  126.  
  127.     public void preOrder() {
  128.         preOrder(root);
  129.     }
  130.  
  131.     private void preOrder(TreeNode node) {
  132.         if (node != null) {
  133.             System.out.print(node.item + " ");
  134.             preOrder(node.leftChild);
  135.             preOrder(node.rightChild);
  136.         }
  137.     }
  138.  
  139.     public void inOrder() {
  140.         inOrder(root);
  141.     }
  142.  
  143.     private void inOrder(TreeNode node) {
  144.         if (node != null) {
  145.             inOrder(node.leftChild);
  146.             System.out.print(node.item + " ");
  147.             inOrder(node.rightChild);
  148.         }
  149.     }
  150.  
  151.     public void postOrder() {
  152.         postOrder(root);
  153.     }
  154.  
  155.     private void postOrder(TreeNode node) {
  156.         if (node != null) {
  157.             postOrder(node.leftChild);
  158.             postOrder(node.rightChild);
  159.             System.out.print(node.item + " ");
  160.         }
  161.     }
  162.  
  163.  
  164.     public static class TreeNode {
  165.         private TreeNode leftChild;
  166.         private TreeNode rightChild;
  167.         private int item;
  168.  
  169.         public TreeNode(int item) {
  170.             this(null, null, item);
  171.         }
  172.  
  173.         public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
  174.             this.leftChild = leftChild;
  175.             this.rightChild = rightChild;
  176.             this.item = item;
  177.         }
  178.     }
  179. }

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

1.任务描述

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

  • 平台将创建用户补全后的BSTree类的对象；
  • 调用对象的insert(int key)方法，构建一棵二叉搜索树；
  • 调用对象的preOrder()方法，输出删除操作前树中的结点；
  • 调用对象的delete(int key)方法，删除最先添加的结点和最后添加的结点；
  • 调用对象的preOrder()方法，输出删除操作后树中的结点；
  • 调用对象的search(int key)方法，测试原来的结点哪些还在树中；
  • 接着根据程序的输出判断程序是否正确。

2.思路分析

        根据二叉搜索树的性质，小了向左，大了向右，直到找到

3.本关答案

  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;
  47.         //小了向左，大了向右
  48.         while (p != null && key != p.item) {
  49.             if (key < p.item) {
  50.                 p = p.leftChild;
  51.             } else {
  52.                 p = p.rightChild;
  53.             }
  54.         }
  55.         if (p == null) {
  56.             return false;
  57.         } else {
  58.             return true;
  59.         }
  60.         /********** End *********/
  61.     }
  62.  
  63.  
  64.     /**
  65.      * 在树root中删除结点key
  66.      *
  67.      * @param key
  68.      * @return
  69.      */
  70.     public void delete(int key) {
  71.         root = delete(root, key);
  72.     }
  73.  
  74.     private TreeNode delete(TreeNode x, int key) {
  75.         if (x == null) {
  76.             return null;
  77.         }
  78.  
  79.         if (key < x.item) {
  80.             x.leftChild = delete(x.leftChild, key);
  81.         } else if (key > x.item) {
  82.             x.rightChild = delete(x.rightChild, key);
  83.         } else {
  84.             if (x.leftChild == null) return x.rightChild;
  85.             if (x.rightChild == null) return x.leftChild;
  86.             TreeNode t = x;
  87.             x = min(t.rightChild);
  88.             x.rightChild = deleteMin(t.rightChild);
  89.             x.leftChild = t.leftChild;
  90.         }
  91.  
  92.         return x;
  93.     }
  94.  
  95.     /**
  96.      * 删除树x中的最小结点
  97.      * @param x
  98.      * @return
  99.      */
  100.     private TreeNode deleteMin(TreeNode x) {
  101.         if (x.leftChild == null) return x.rightChild;
  102.         x.leftChild = deleteMin(x.leftChild);
  103.         return x;
  104.     }
  105.  
  106.     /**
  107.      * 查找树x中的最小结点
  108.      *
  109.      * @param x
  110.      * @return
  111.      */
  112.     private TreeNode min(TreeNode x) {
  113.         TreeNode p = x;
  114.         while (p.leftChild != null) {
  115.             p = p.leftChild;
  116.         }
  117.         return p;
  118.     }
  119.  
  120.     public void preOrder() {
  121.         preOrder(root);
  122.     }
  123.  
  124.     public void inOrder() {
  125.         inOrder(root);
  126.     }
  127.  
  128.     public void postOrder() {
  129.         postOrder(root);
  130.     }
  131.  
  132.     private void preOrder(TreeNode node) {
  133.         if (node != null) {
  134.             System.out.print(node.item + " ");
  135.             preOrder(node.leftChild);
  136.             preOrder(node.rightChild);
  137.         }
  138.     }
  139.  
  140.     private void inOrder(TreeNode node) {
  141.         if (node != null) {
  142.             inOrder(node.leftChild);
  143.             System.out.print(node.item + " ");
  144.             inOrder(node.rightChild);
  145.         }
  146.     }
  147.  
  148.     private void postOrder(TreeNode node) {
  149.         if (node != null) {
  150.             postOrder(node.leftChild);
  151.             postOrder(node.rightChild);
  152.             System.out.print(node.item + " ");
  153.         }
  154.     }
  155.  
  156.  
  157.     public static class TreeNode {
  158.         private TreeNode leftChild;
  159.         private TreeNode rightChild;
  160.         private int item;
  161.  
  162.         public TreeNode(int item) {
  163.             this(null, null, item);
  164.         }
  165.  
  166.         public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
  167.             this.leftChild = leftChild;
  168.             this.rightChild = rightChild;
  169.             this.item = item;
  170.         }
  171.     }
  172. }

Java算法与数据结构测试——二叉树

第1关：向二叉树中插入叶子节点

1.任务描述

本关任务：向二叉树中插入左叶子节点，请补全insertLeft(T x, Node<T> parent)函数实现插入左叶子节点的功能

2.思路分析

        我们主要看本关已经给出的insertRight方法，本关要求我们补全插入左子节点的方法，这与insertRight思路逻辑一致，我们只需稍微更改一下孩子的指向即可

  1.     //在当前二叉树的parent节点中插入一个新的左子结点，若已存在左子树，则将该左子树变成新左子结点的右子树
  2. 	public boolean insertLeft(T x, Node<T> parent)
  3. 	{ 
  4. 		/********* Begin *********/
  5. 		if(parent==null) return false;
  6.         Node<T> p=new Node<>(x);
  7.         if(parent.lChild==null){
  8.             parent.lChild=p;
  9.         }else{
  10.             p.rChild=parent.lChild;
  11.             parent.lChild=p;
  12.         }
  13.         return true;
  14. 		/********* End *********/
  15. 	} 
  16.     //在当前二叉树的parent节点中插入一个新的右子结点，若已存在右子树，则将该右子树变成新右子结点的左子树
  17.     public boolean insertRight(T x, Node<T> parent)
  18.     { 
  19. 		if(parent==null)	return false;
  20. 		Node<T> p= new Node<T>(x);
  21. 		if(parent.rChild==null) parent.rChild = p;
  22. 		else
  23. 		{
  24. 			p.rChild = parent.rChild;
  25. 			parent.rChild = p;
  26. 		}
  27. 		return true; 
  28. 	}

具体了解二叉搜索树请参考下面文章：

https://blog.csdn.net/m0_74808313/article/details/130103168

 

 

 

 

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/569964
推荐阅读
相关标签

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

  

闽ICP备14008679号