Java データ構造でスレッド化されたバイナリ ツリーを実装するにはどうすればよいですか?

1. 手がかり付き二分木の概要

シーケンス {1, 3, 6, 8, 10, 14} を二分木に構築します。

問題分析:

1. 上記のバイナリ ツリーで順序トラバーサルを実行すると、配列は {8, 3, 10, 1, 6, 14}

2 になります。ただし、6、これらのノード 8、10、14 の左右のポインタは十分に活用されていません。

3. 各ノードの左右のポインタを最大限に活用したい場合、各ノードは

4. 解決策 - 手がかりバイナリ ツリー

概念: バイナリ リンク リストをバイナリ ツリーの記憶構造として使用する場合、ノードの左と右の子を見つけるのは簡単ですが、一般に、特定の走査シーケンスでノードの先行ノードと後続ノードを直接見つけることは不可能です。したがって、スレッド化が使用され、二分木構造のリンク リストのヌル ポインタ フィールドがスレッド化に使用されます。

2. スレッド バイナリ ツリーの基本特性

n 個のノードのバイナリ リンク リストには、n 1 [式 2n-(n-1)=n 1] のヌル ポインタ フィールドが含まれます。バイナリ リンク リストの null ポインタ フィールドを使用して、ノードの先行ノードと後続ノードへのポインタを特定の走査順序で保存します (このような追加のポインタは「手がかり」と呼ばれます)

この種の追加バイナリ リンク手がかりを含むリストは手がかりリンクリストと呼ばれ、対応する二分木はスレッド化された二分木 (Threaded BinaryTree) と呼ばれます。手がかりの性質の違いにより、手がかり二分木は、前順序手がかり二分木、中間手がかり二分木、事後手がかり二分木という 3 つのタイプに分類できます。 ##中間手がかり バイナリ ツリーの変換とトラバース

アプリケーション ケースの説明: 次のバイナリ ツリーを順序クルー バイナリ ツリーに変換します。インオーダートラバーサルの数値シーケンスは {8, 3, 10, 1, 14, 6}

アイデア分析

インオーダーの結果order traversal: {8 , 3, 10, 1, 14, 6}

#スレッド化後のバイナリ ツリーの左右のポインタは、図に示すようになります。上記↑

説明: スレッド化時、バイナリ ツリーの後、Node ノードの左右の属性には次のような状況があります:

left は左側のサブツリーを指します。たとえば、① 左のノードは左のサブツリーを指し、⑩ のノードの左は先行ノードを指します。右のサブツリーを指すか、後続ノードを指す場合があります。たとえば、① ノードの右は右のサブツリーを指します。ツリー、⑩ ノードの右は後続ノードを指します。

• #したがって、元のバイナリ ツリーのノード構造を変更する必要があります。

  package com.studySelf.tree.threadedBinaryTree;
  
  /**
   * @author wang
   * @version 1.0
   * @packageName com.studySelf.tree.tree01
   * @className Node
   * @date 2022/4/19 20:15
   * @Description Node结点
   */
  public class Node {
      //唯一编号
      private int num;
      //结点的值
      private String name;
      //左结点
      private Node left;
      //右节点
      private Node right;
  
      //这个属性用来控制线索二叉树的结点的指向，0代表指向左结点，1代表指向前趋结点
      private int leftType;
      //这个属性用来控制线索二叉树的结点的指向，0代表指向右结点，1代表指向后继结点
      private int rightType;
  
  
      //构造方法
  
      public Node(int num, String name) {
          this.num = num;
          this.name = name;
      }
  
      public int getLeftType() {
          return leftType;
      }
  
      public void setLeftType(int leftType) {
          this.leftType = leftType;
      }
  
      public int getRightType() {
          return rightType;
      }
  
      public void setRightType(int rightType) {
          this.rightType = rightType;
      }
  
      public int getNum() {
          return num;
      }
  
      public void setNum(int num) {
          this.num = num;
      }
  
      public String getName() {
          return name;
      }
  
      public void setName(String name) {
          this.name = name;
      }
  
      public Node getLeft() {
          return left;
      }
  
      public void setLeft(Node left) {
          this.left = left;
      }
  
      public Node getRight() {
          return right;
      }
  
      public void setRight(Node right) {
          this.right = right;
      }
  
      @Override
      public String toString() {
          return "Node{" +
                  "num=" + num +
                  ", name='" + name +
                  '}';
      }
  
      /**
       * 前序遍历
       */
      public void preSelect() {
          //首先输出根结点
          System.out.println(this);
          //其次判断是否有左结点
          if (this.left != null) {
              //没有左结点，就递归调用本方法输出该结点。
              this.left.preSelect();
          }
          if (this.right != null) {
              this.right.preSelect();
          }
      }
  
      /**
       * 中序遍历
       */
      public void infixSelect() {
          //首先判断左结点
          if (this.left != null) {
              //如果左结点不为空，递归向左子树调用
              this.left.infixSelect();
          }
          //当左结点为空，再输出根结点。当他本身就是最后一个左结点的时候，会直接输出，且没有右节点
          System.out.println(this);
          if (this.right != null) {
              //右节点同样如此，递归调用。直到没有结点为止。
              this.right.infixSelect();
          }
      }
  
      /**
       * 设二叉树有三个结点，根结点，左结点，右节点。
       * 后序遍历,解释，当一个二叉树的左结点不为空，那么他会进入下一个递归调用自己的后序遍历方法
       * 此时，根结点就是左结点，这时判断左结点，右节点均为空，就会输出左结点
       * 回退到根结点为this的时候，左结点已经判断完毕，接下来是右节点，右节点不为空，进入后续遍历递归，
       * 此时的this就是右节点，进入递归后，判断，不存在左右结点，输出this，也就是整个二叉树的右节点
       * 回退到this为根结点时，右节点也已经输出，走到最后一步，输出自己也就是this。
       * 整个后序遍历就结束，那么该二叉树的遍历结果就是左，右，根
       */
  
      public void afterSelect() {
          if (this.left != null) {
              this.left.afterSelect();
          }
  
          if (this.right != null) {
              this.right.afterSelect();
          }
          System.out.println(this);
      }
  
      /**
       * @param num
       * @Date 2022/4/21 17:51
       * @Param
       * @Return Node
       * @MetodName preSearchByNum
       * @Author wang
       * @Description 根据结点的编号来查询结点, 前序遍历查询，根，左，右
       */
      public Node preSearchByNum(int num) {
          //首先判断传进来的num与该结点的num是否相等
          //如果相等，那该结点就是我们要找的结点。
          if (this.num == num) {
              return this;
          }
  
          //如果不相等，该结点就不是我们要找的结点
          //那么我们就遍历该结点的左子节点，和右子结点
          //定义一个结点用于接收最后的返回结果
          Node resultNode = null;
          //如果该结点的左子结点不为空，就递归调用前序遍历，继续查找，如果找到了，那么resultNode就是我们想要的值
          if (this.left != null) {
              resultNode = this.left.preSearchByNum(num);
          }
  
          //如果遍历完左子结点，已经找到了我们想要的结果，直接返回结果即可，
          if (resultNode != null) {
              return resultNode;
          }
  
          //如果左子结点为空，且没有找到我们想要的结点的情况下。那就判断右子结点
          if (this.right != null) {
              resultNode = this.right.preSearchByNum(num);
          }
          //最后，如果找到了，那么resultNode一定会被赋值，如果没找到，就会返回null
          return resultNode;
      }
  
      /**
       * @param num
       * @Date 2022/4/21 17:58
       * @Param
       * @Return Node
       * @MetodName infixSearchByNum
       * @Author wang
       * @Description 中序遍历查找，左，根，右进行查询即可。
       */
      public Node infixSearchByNum(int num) {
          //首先判断左子结点,如果存在左子结点，递归继续查询遍历即可即可。
          Node resultNode = null;
          if (this.left != null) {
              resultNode = this.left.infixSearchByNum(num);
          }
  
          //如果左子结点已经找到了我们想要的结点，直接返回当前结点即可
          if (resultNode != null) {
              return resultNode;
          }
  
          //判断根结点
          if (this.num == num) {
              return this;
          }
  
          //判断右子结点，
          if (this.right != null) {
              resultNode = this.right.infixSearchByNum(num);
          }
          //最后返回我们的结果即可。
          return resultNode;
      }
  
  
      /**
       * @param num
       * @Date 2022/4/21 19:15
       * @Param
       * @Return Node
       * @MetodName afterSearchNum
       * @Author wang
       * @Description 后续遍历结点进行查找结点。左，右，根
       */
      public Node afterSearchNum(int num) {
          Node resultNode = null;
          //首先遍历左结点
          if (this.left != null) {
              resultNode = this.left.afterSearchNum(num);
          }
  
          //判断左结点是否找到哦啊
          if (resultNode != null) {
              return resultNode;
          }
  
          //判断右节点是否为空
          if (this.right != null) {
              resultNode = this.right.afterSearchNum(num);
          }
  
          //判断右节点是否找到
          if (resultNode != null) {
              return resultNode;
          }
  
          //判断根结点是否为我们找的结点
          if (this.num == num) {
              return this;
          }
          //最后返回
          return resultNode;
      }
  
      /**
       * @param num
       * @Date 2022/4/25 19:30
       * @Param
       * @Return void
       * @MetodName delNodeByNum
       * @Author wang
       * @Description 根据结点的编号删除结点
       */
      public void delNodeByNum(int num) {
          //首先，判断当前结点的左结点是否为空，并且左结点的num是否与num相等
          if (this.left != null && this.left.num == num) {
              //如果相等，那就说明该结点就是我们要删除的结点,将其左结点置空即可
              this.left = null;
              return;
          }
  
          //如果左结点没有执行，说明左结点没有我们想要的结果，也就是要删除的结点不在左结点
          //那么就对右节点进行判断
          if (this.right != null && this.right.num == num) {
              this.right = null;
              return;
          }
  
          //如果左右结点均没有找到目标结点
          //那么就对左子树进行递归删除操作
          if (this.left != null) {
              this.left.delNodeByNum(num);
          }
  
          //同理，如果左子树没有目标结点，向右子树进行递归删除操作
          if (this.right != null) {
              this.right.delNodeByNum(num);
          }
  
      }
  }

  この追加の 2 つの属性があることがわかります:

    //这个属性用来控制线索二叉树的结点的指向，0代表指向左结点，1代表指向前趋结点
    private int leftType;
    //这个属性用来控制线索二叉树的结点的指向，0代表指向右结点，1代表指向后继结点
    private int rightType;

• 順番にスレッド化されたバイナリ ツリー

    /**中序线索化二叉树*/
      /**
       * @param node 该结点为根结点，从根节点开始线索化二叉树，中序
       */
      public void infixThreadNodes(Node node) {
          /**首先判断二叉树的根节点上会否为空，如果根结点为空，不可以线索化，因为没有二叉树*/
          if (node == null) {
              return;
          }
  
          /**接着对左子树进行线索化*/
          infixThreadNodes(node.getLeft());
  
          /**对当前结点进行线索化*/
          /**首先判断当前结点的左子结点是否为空*/
          if (node.getLeft() == null) {
              //如果左子结点为空，说明就找到了我们需要线索化的结点
              //就可以将pre也就是一直在当前结点的前趋结点设置给当前结点的左子结点，
              //如果这是第一个结点，那么pre为空，正好第一个结点的前趋结点也为空
              node.setLeft(pre);
              //并且将它的左子结点的类型设置为前趋结点。1代表前趋结点
              node.setLeftType(1);
          }
  
          /**接着判断前趋结点的右子结点是否为空，前提是前趋结点不能为空，如果他为空，说明这是第一个结点还没走完*/
          if (pre != null && pre.getRight() == null) {
              //如果条件满足，说明前趋结点现在已经走到了值，并且还没有线索到后继结点，
              // 也就是当前结点的上一个结点（这个上一个结点就是当前的前趋结点）还没有后继，
              //那么上一个结点的后继结点就是当前结点，因此赋值前趋结点（也就是上一个结点）的后继结点为当前结点。
              //这样这条线索就连接上了,并且只有满足叶子结点的结点才可以进行线索化
              pre.setRight(node);
              pre.setRightType(1);
          }
  
          //当前两步走完之后，就可以将pre结点赋值为当前结点，
          // 因为下一个结点一走，当前结点就是前趋结点了。直到走到全部线索化结束
          //这步十分重要，这一步不写，整个线索化就连接不上
          pre = node;
  
          /**对右子树进行线索化*/
          infixThreadNodes(node.getRight());
      }

  順番にスレッド化されたバイナリ ツリーのアイデア

順番に走査されるバイナリ ツリーの順序は左であり、ルートは右であるため、最初に左のサブツリーを手がかりにします。

再帰が左サブツリーの左端のノードに到達すると、その左ノード ポイントは空である必要があり、その左ノードを pre に割り当てます (pre ノードは再帰を続行できるように、スレッドの最後のステップで現在のノードに割り当てられます。左側のノードのタイプは、それが先行ノードであることを意味する 1 に変更する必要があることに注意してください。先行ノードは手がかりを失いました。

1. 後続ノードの処理は、先行ノードを決定することです。現在のノードが空ではなく、先行ノードの右側のノードが空の場合は、先行ノードを設定します。右ノードは現在のノード、つまり、設定されていない前のノードの右ノードです。タイプもサクセサ

2. に設定する必要があります。最後に、値を代入します。 pre ノードを現在のノードに割り当てます。次の再帰では、現在のノードが前のノード (pre

3. になります) になるためです。最後に、右側の子ノードバイナリツリーのスレッド化。

4. 順番にスレッド化されたバイナリ ツリーのトラバース

5. 順番にスレッド化されたバイナリ ツリーをトラバースするときは、まず次のことを明確にする必要があります。走査順序は元の走査と同じである必要があります。順序どおりのバイナリ ツリー走査の結果が同じであれば、走査は成功です。

次に、最初のステップは次のことを判断する必要があります。ルート ノードが空ではない (これがループ終了条件です)

1. 次にループして、タイプが 0 である現在のノードの左側の子ノード、つまり、スレッド化されていない。0 である限り、ノードは常に左側の子ノードに値を割り当てます。最初のスレッド化されたノードを見つけて出力するまでは、それが最初のスレッド化されたノードであり、順序走査の最初の左側の子ノードになります。

2. 出力後、その右側の子ノードがスレッド化されているかどうかを確認します。スレッド化されている場合は、現在のノード ノードが独自の右側の子ノードとして割り当てられ、タイプが次の場合は出力されます。ノードの右側の子ノードが再び 1 になった後、引き続き戻って値を割り当て、右側の子ノードのタイプが になるまで後継ノード

3. があることを示します0. ループを終了した後、右側にも値を割り当て、後方へのトラバースを続ける必要があります

4. コードのデモ

       /**遍历中序线索化二叉树*/
       public void infixThreadNodesSelect() {
           /**第一个结点为根结点*/
           Node node = root;
           while(node != null) {
               /**当结点不为空，就一直遍历*/
               /**当该结点的左子结点的类型为1的时候，也就是说该结点是被线索化的结点,
                * 因为是中序遍历，所以应该遍历到最左边的最左子结点，那么就是第一个
                * 左子结点类型为1的结点。*/
               while(node.getLeftType() == 0) {
                   node = node.getLeft();
               }
               /**当左子结点的类型为1,输出左子结点*/
               System.out.println(node);
   
               /**当右子结点类型为1，当前结点输出完毕后
                * 中序遍历就应该输出右子结点，那么就是当前结点的右子结点类型只要为1，就往后移动
                * 并且输出，当他为0，说明没有线索化，那么没有后继结点，但是他有右子结点，
                * 因此要在循环结束以后向后移动。*/
               while (node.getRightType() == 1) {
                   node = node.getRight();
                   System.out.println(node);
               }
               /**当右子结点循环退出，说明这里到了类型为0也就是后继结点*/
               node = node.getRight();
           }

   4. スレッド化されたバイナリ ツリーを事前注文します。トラバーサル
5. スレッド化されたバイナリ ツリー

    /**
        * 前序线索化二叉树
        */
       public void preThreadNodes(Node node) {
           /**首先判断当前节点是否为空*/
           if (node == null) {
               return;
           }
   
           /**如果是前序遍历，那么先对当前结点进行判断，当前结点的前趋结点的操作*/
           if (node.getLeft() == null) {
               node.setLeft(pre);
               node.setLeftType(1);
           }
   
           /**处理后继结点,定义的前趋结点不为空，说明他有值，就是已经存在了上一个结点的值，他的右子结点没有值的话，就可以
            * 给他赋予后继结点为当前结点，这里赋予的也就是上一个结点*/
           if (pre != null && pre.getRight() == null) {
               pre.setRight(node);
               pre.setRightType(1);
           }
   
           /**这里是关键的一步*/
           pre = node;
   
           /**对左子结点进行线索化,注意，这里需要排除已经被线索化掉的结点,因为这里要考虑一个情况，
            * 比如这里已将到了最下面一个左子结点，由于是前序遍历，遍历到左子结点，他的前趋结点在上面就设置了
            * 如果这里不判断左子结点的类型，那么就会进入递归，但是这个递归如果进去了，就是错误的递归，因为他传过去的结点
            * 是我们刚刚给他赋值的前趋结点，也就是根结点。会发生错误。因此得判断类型*/
           if (node.getLeftType() != 1) {
               preThreadNodes(node.getLeft());
           }
   
   
           /**对右子结点进行递归线索化*/
           if (node.getRightType() != 1) {
               preThreadNodes(node.getRight());
           }
       }

    遍历线索化二叉树

   /**
        * 前序遍历线索二叉树*/
       public void preThreadNodeSelect() {
           Node node = root;
           while(node !=null) {
               while(node.getLeftType() == 0) {
                   /**前序遍历为根左右，先输出根结点,因为他每次进来循环肯定是先到根结点，所以一进该循环
                    * 就要输出根结点，当他的lefttype=1循环结束，说明遇到了被线索化的地方了。*/
                   System.out.println(node);
                   /**再最左子结点进行遍历*/
                   node = node.getLeft();
               }
               /**上面的循环结束之后就应该输出当前结点，也就是那个序列化的结点
                * 之后结点向右移动继续遍历*/
               System.out.println(node);
               node = node.getRight();
           }
     }

   图解

   

   5.后序线索化二叉树

   后续线索化二叉树

   /**
    * 后序线索化二叉树的方法
    */
   public void postThreadedBinaryTree(Node node) {
       /**首先判断结店不能为空*/
       if (node == null) {
           return;
       }
   
       /**先后续线索化左子结点*/
       postThreadedBinaryTree(node.getLeft());
       /**在后续线索化右子结点*/
       postThreadedBinaryTree(node.getRight());
   
       /**处理当前结点的前趋结点*/
       if (node.getLeft() == null) {
           node.setLeft(pre);
           node.setLeftType(1);
       }
   
       /**处理后继结点*/
       if (pre != null && pre.getRight() == null) {
           pre.setRight(node);
           pre.setRightType(1);
       }
       pre = node;
   }

以上がJava データ構造でスレッド化されたバイナリ ツリーを実装するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。