请解释 java 中给定的二叉树代码

Question

我找不到人向我解释这个 java 代码所以最后我发布这个 question.please 解释这个特定语句如何影响 tree.the 问题的过程在 comments.I BST class.

中有问题

 import java.util.Scanner;

 class BSTNode
 {
     BSTNode left, right;
     int data;

     public BSTNode()
     {
         left = null;
         right = null;
         data = 0;
     }

     public BSTNode(int n)
     {
         left = null;
         right = null;
         data = n;
     }

     public void setLeft(BSTNode n)
     {
         left = n;
     }

     public void setRight(BSTNode n)
     {
         right = n;
     }

     public BSTNode getLeft()
     {
         return left;
     }

     public BSTNode getRight()
     {
         return right;
     }

     public void setData(int d)
     {
         data = d;
     }

     public int getData()
     {
         return data;
     }     
 }

 class BST
 {
     private BSTNode root;

     public BST()
     {
         root = null;
     }

     public boolean isEmpty()
     {
         return root == null;
     }

插入函数为什么写成root=insert(.....。是否每次都返回 root = 实际根元素？

     public void insert(int data)
     {
         root = insert(root, data);
     }

我明白插入过程是如何进行的，但是插入函数返回了什么？我知道它 returns 某个节点，但迭代过程中的过程是如何进行的？

     private BSTNode insert(BSTNode node, int data)
     {
         if (node == null)
             node = new BSTNode(data);
         else
         {
             if (data <= node.getData())
                 node.left = insert(node.left, data);
             else
                 node.right = insert(node.right, data);
         }

         return node;
     }

     public void delete(int k)
     {
         if (isEmpty())
             System.out.println("Tree Empty");
         else if (search(k) == false)
             System.out.println("Sorry "+ k +" is not present");
         else
         {
             root = delete(root, k);

再说一次，为什么删除函数要写成root=delete(.....？是不是每次都返回root=实际根元素？

             System.out.println(k+ " deleted from the tree");
         }
     }

     private BSTNode delete(BSTNode root, int k)
     {
         BSTNode p, p2, n;

         if (root.getData() == k)
         {
             BSTNode lt, rt;
             lt = root.getLeft();
             rt = root.getRight();

             if (lt == null && rt == null)
                 return null;
             else if (lt == null)
             {
                 p = rt;
                 return p;
             }
             else if (rt == null)
             {
                 p = lt;
                 return p;
             }
             else
             {
                 //case when we delete node having both children.
                 p2 = rt;
                 p = rt;

                 //getting the min of the right child subtree in p variable .
                 while (p.getLeft() != null)
                     p = p.getLeft();

                 p.setLeft(lt);

请解释这里发生了什么以及为什么要返回 p2 即 rt。

                 return p2;
             }
         }

         if (k < root.getData())
         {
             n = delete(root.getLeft(), k);
             root.setLeft(n);
         }
         else
         {
             n = delete(root.getRight(), k);
             root.setRight(n);             
         }

         return root;
     }

     public int countNodes()
     {
         return countNodes(root);
     }

Answer 1

在代码的删除部分，您所做的是检查节点（称为根）的数据值是否等于您要删除的值 (k)。如果那是真的，那么你检查你似乎掌握的两个children。因此，当您同时拥有节点的 children 而不是 null 时，我们开始讨论您的问题。在这种情况下你想删除你所在的子树的当前节点（根），但是你需要选择一个节点（左边或右边）来提升到这个节点的位置。因此（假设这棵树不平衡）您只需选择（左或右）子树以提升到已知根。请记住，您只是将当前节点称为根，因为它是较大树中某个子树的根（这并不意味着树的实际根，除非它是作为根传入的值）。知道右 child 子树中的所有值都将大于左 child 子树中的值，您只需获取当前节点的左子树然后递归到左 [=27] =]ren 的右子树，直到你走到尽头。然后将此节点的左 child 设置为整个左子树。

//case when we delete node having both children.
p2 = rt;
p = rt;

//getting the min of the right child subtree in p variable .
while (p.getLeft() != null)
p = p.getLeft();

p.setLeft(lt);

声明中的通知

p = rt;

您正在将 P 设置为右子树的根。那么p现在就是传入的当前根的右边child。

while (p.getLeft() != null)
    p = p.getLeft();

p.setLeft(lt);

这基本上是说，对于那个右子树，如果根节点有左 child，则将 p 设置为该值并继续这样做，直到该值为空。这将继续沿着右子树的左 children 向下移动。最后一旦该值为 null

p.setLeft(lt);

会将右子树中最左边的叶子的左边 child 设置为您开始时的整个左子树。 return 您所说的节点是原始节点的右子树（现在原始节点的左子树附加到其最左边的叶子）。

请解释 java 中给定的二叉树代码

Please explain the given binary tree code that is in java

java

recursion

recursive-datastructures