Was ist der Java-Morris-Traversalalgorithmus und seine Anwendung in Binärbäumen?

1. Morris-Traversal Die zeitliche Komplexität dieses Algorithmus beträgt O(n) und die räumliche Komplexität beträgt O(1).

2. Grundidee

Die Grundidee von Morris Traversal besteht darin, den Nullzeiger von Blattknoten zu verwenden, um temporäre Informationen platzsparend zu speichern. Insbesondere für den aktuell durchlaufenen Knoten: Wenn er einen linken untergeordneten Knoten hat, suchen Sie den Knoten ganz rechts im linken Teilbaum, zeigen Sie seinen rechten untergeordneten Knoten auf den aktuellen Knoten und aktualisieren Sie dann den aktuellen Knoten auf seinen linken untergeordneten Knoten. Wenn es kein linkes Kind hat, geben Sie den Wert des aktuellen Knotens aus und aktualisieren Sie den aktuellen Knoten auf sein rechtes Kind. Wiederholen Sie die obigen Schritte, bis der gesamte Baum durchlaufen ist.

3. Vor- und Nachteile der Morris-Durchquerung

Der Vorteil der Morris-Durchquerung besteht darin, dass die Raumkomplexität niedrig ist (O(1), aber ihr Nachteil besteht darin, dass sie die ursprüngliche Binärbaumstruktur ändert, sodass der Binärbaum so sein muss nach der Durchquerung wiederhergestellt. Darüber hinaus ist der Algorithmus möglicherweise etwas langsamer als rekursive oder Stack-verwendende Algorithmen.

4. Beim Threading von Binärbäumen wird hauptsächlich das Nullzeigerfeld in den Blattknoten verwendet, um die Vorgänger- oder Folgeknoten in einer bestimmten Durchlaufreihenfolge zu speichern, wodurch der Zweck eines Clued-Binärbaums erreicht wird Beispiel: Das Ergebnis der Durchquerung in der Reihenfolge ist unten dargestellt. Das Nullzeigerfeld wird entsprechend der Durchquerung in der Reihenfolge angezeigt Der Knoten zeigt darauf, und wenn Sie ihn nach rechts zeichnen, bedeutet dies, dass er nach rechts zeigt. Beispielsweise ist der Vorgängerknoten von 7 5, dann zeigt der linke Knoten von 7 auf 5, der Nachfolgerknoten von 7 ist 1 und dann ist der rechte Knoten von 7 zeigt auf 1

Daraus können wir schließen, dass der Knoten, der auf den aktuellen Knoten des Binärbaums zeigt, der Knoten ganz rechts im linken Teilbaum des aktuellen Knotens ist zu 1 ist 1, der Knoten ganz rechts von Knoten 2 ist 7 und der Knoten, der auf Knoten 2 zeigt, ist 2. Der Knoten ganz rechts ist 4 des linken Knotens 4. Dies ist bei der anschließenden Morris-Durchquerung sehr wichtig

Der spezifische Code ist implementiert wie folgt:

public class InorderThreadedBinaryTree {
    private ThreadTreeNode pre = null;
    public void threadedNodes(ThreadTreeNode node) {
        //如果node==null，不能线索化
        if (node == null) {
            return;
        }
        //1、先线索化左子树
        threadedNodes(node.left);
        //2、线索化当前结点
        //处理当前结点的前驱结点
        //以8为例来理解
        //8结点的.left = null，8结点的.leftType = 1
        if (node.left == null) {
            //让当前结点的左指针指向前驱结点
            node.left = pre;
            //修改当前结点的左指针的类型，指向前驱结点
            node.leftType = 1;
        }
        //处理后继结点
        if (pre != null && pre.right == null) {
            //让当前结点的右指针指向当前结点
            pre.right = node;
            //修改当前结点的右指针的类型=
            pre.rightType = 1;
        }
        //每处理一个结点后，让当前结点是下一个结点的前驱结点
        pre = node;
        //3、线索化右子树
        threadedNodes(node.right);
    }
}
class ThreadTreeNode {
    int val;
    ThreadTreeNode left;
    //0为非线索化,1为线索化
    int leftType;
    ThreadTreeNode right;
    //0为非线索化,1为线索化
    int rightType;
    public ThreadTreeNode(int val) {
        this.val = val;
    }
}

Aber bei der Implementierung der Morris-Traversierung ist es nicht erforderlich, den linken Knoten des Knotens anzugeben, sondern nur den rechten Knoten des Knotens. Die spezifischen Gründe werden unten analysiert -Morris-Durchquerung

1. Analyse der Morris-Durchquerung mittlerer Ordnung

Wir haben oben über die Morris-Durchquerung gesprochen. Wenn wir nur den richtigen Knoten finden müssen, erklären wir es hier. Wenn wir einen Baum in der richtigen Reihenfolge durchqueren, z Als Baum wie dieser kommen wir Schritt für Schritt mit node.left zum Knoten 6. Die linke Seite des Knotens ist leer, daher drucken wir den Wert des Knotens 6. Zu diesem Zeitpunkt müssen wir zum vorherigen Knoten zurückkehren Wenn wir die Rekursion in der richtigen Reihenfolge durchlaufen möchten, müssen wir zum vorherigen Stapel zurückkehren. Wenn wir Morris durchlaufen, ist eine rekursive Rückkehr nicht möglich. Daher müssen wir zu diesem Zeitpunkt nur den rechten Knoten von 6 einfädeln. Der rechte Knoten von 6 zeigt auf 4, wir können zu 4 zurückkehren, den Knoten 4 drucken, und 4 wird ebenfalls eingefädelt und 2 zurückgegeben, 2 gedruckt und dann zum rechten Knoten 5 von 2 übergegangen. Der linke Knoten von 5 ist leer, also wird 5 gedruckt, und dann wird der rechte Knoten 7 von 5 eingegeben und 7 gedruckt, und der rechte Knoten von 7 wird ebenfalls gedruckt. Geben Sie zum Einfädeln den rechten Knoten von 7 als 1 ein, drucken Sie dann 1 und geben Sie ein 3 Knoten und drucken

Da es am besten ist, die Struktur des Baums nicht zu ändern, ändern wir beim Drucken den rechten Knoten des Thread-Knotens. Setzen Sie ihn auf leer.

2 In-Order-Morris-Traversal

Morris-Traversal verwendet die Idee eines Hinweis-Binärbaums. Der Stapel wird während des Traversierungsprozesses nicht verwendet, wodurch eine Raumkomplexität von O(1) erreicht wird

Die spezifische Implementierung ist wie folgt:

1. Initialisieren Sie den aktuellen Knoten als Wurzelknoten.

2 Wenn der linke Knoten des aktuellen Knotens leer ist, geben Sie den aktuellen Knoten aus und durchlaufen Sie dann den rechten Teilbaum des aktuellen Knotens. Das heißt, 'curr=curr'. rechts'

3. Wenn der linke Knoten des aktuellen Knotens nicht leer ist, suchen Sie den Vorgängerknoten des aktuellen Knotens, dh den Knoten ganz rechts des linken Knotens des aktuellen Knotens, aufgezeichnet als „vorheriger“

Wenn „prev.right“ leer ist, zeigen Sie pre.right auf den aktuellen Knoten und durchlaufen Sie dann den linken Teilbaum des aktuellen Knotens, d. h. „curr=curr.left“. '' ist nicht leer, was darauf hinweist, dass der linke Teilbaum des aktuellen Knotens durchlaufen wurde. Trennen Sie „prev.right“, also „prev.left=null“, den aktuellen Knoten und durchlaufen Sie dann den rechten Teilbaum aktueller Knoten, Das ist „curr=curr.right“.

3. Spezifische Code-Implementierung

public class Morris {
    /**
     * 将当前根结点中序遍历的结果存储到list集合中
     * @param root  根结点
     * @return  中序遍历的结合
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left == null) { // 左子树为空，则输出当前节点，然后遍历右子树
                res.add(curr.val);  //如果要求直接打印,直接输出System.out.println(curr.val);
                curr = curr.right;
            } else {
                // 找到当前节点的前驱节点
                TreeNode prev = curr.left;
                while (prev.right != null && prev.right != curr) {
                    prev = prev.right;
                }
                if (prev.right == null) {
                    // 将前驱节点的右子树连接到当前节点
                    prev.right = curr;
                    curr = curr.left;
                } else {
                    // 前驱节点的右子树已经连接到当前节点，断开连接，输出当前节点，然后遍历右子树
                    prev.right = null;
                    res.add(curr.val);//如果要求直接打印,直接输出System.out.println(curr.val);
                    curr = curr.right;
                }
            }
        }
        return res;
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

Test:

Es ist immer noch so ein Binärbaum, die Ausgabe ist wie folgt:

[ 6, 4, 2, 5, 7, 1, 3]

• 三.前序Morris遍历

  1.前序Morris遍历的思路

  前序和中序的遍历很想,只不过在打印(收集结点信息的时候不同),中序遍历是在当前结点的左节点为空(curr.left==null),或者当前结点已经被线索化(prev.right==curr)的时候进行打印,仔细观察前序遍历的过程,我们通过修改打印的顺序即可.前序遍历是在当前结点的左节点为空(curr.left==null),或者当前结点没有被线索化(prev.right==null)的时候进行打印

  具体的思路如下:

  1.初始化当前的结点为根结点

  2.若当前的结点的左节点为空,则输出当前结点,然后遍历当前结点的右子树,即'curr=curr.right'

  3.若当前结点的左节点不为空,则找到当前结点的前驱节点,即当前结点左节点的最右侧结点,记为'prev'

  • 如果'prev.right''为空,输出当前节点,然后将pre.right指向curr结点,然后遍历当前结点的左子树,即'curr=curr.left'

  • 如果'prev.right''不为空,说明已经遍历完了当前节点的左子树,断开 `prev.right` 的连接,即'prev.left=null',然后遍历当前节点的右子树,即 `curr=curr.right`.

  

  2.具体的代码实现

      public List<Integer> preorderTraversal(TreeNode root) {
          List<Integer> res = new ArrayList<>();
          TreeNode curr = root;
          while (curr != null) {
              if (curr.left == null) { // 左子树为空，则输出当前节点，然后遍历右子树
                  res.add(curr.val);//如果要求直接打印,直接输出System.out.println(curr.val);
                  curr = curr.right;
              } else {
                  // 找到当前节点的前驱节点
                  TreeNode prev = curr.left;
                  while (prev.right != null && prev.right != curr) {
                      prev = prev.right;
                  }
                  if (prev.right == null) {
                      res.add(curr.val);//如果要求直接打印,直接输出System.out.println(curr.val);
                      // 将前驱节点的右子树连接到当前节点
                      prev.right = curr;
                      curr = curr.left;
                  } else {
                      // 前驱节点的右子树已经连接到当前节点，断开连接，输出当前节点，然后遍历右子树
                      prev.right = null;
                      curr = curr.right;
                  }
              }
          }
          return res;
      }

  测试:

      public static void main(String[] args) {
          TreeNode root = new TreeNode(1);
          root.left = new TreeNode(2);
          root.left.right = new TreeNode(5);
          root.left.right.right = new TreeNode(7);
          root.right = new TreeNode(3);
          root.left.left = new TreeNode(4);
          root.left.left.left = new TreeNode(6);
          System.out.println(preorderTraversal(root));
      }

  还是这样一颗二叉树,输出如下:

  [1, 2, 4, 6, 5, 7, 3]

  四.后序Morris遍历

  1.后序Morris遍历的思路

  后序Morris遍历实现起来有一定的难度,但是基本代码还是不变,只是在打印的地方有略微的区别,

  具体的思路如下:

  1.初始化当前的结点为根结点

  2.若当前的结点的左节点为空,则输出当前结点,然后遍历当前结点的右子树,即'curr=curr.right'

  3.若当前结点的左节点不为空,则找到当前结点的前驱节点,即当前结点左节点的最右侧结点,记为'prev'

  • 如果'prev.right''为空,然后将pre.right指向curr结点,然后遍历当前结点的左子树,即'curr=curr.left'

  • 如果'prev.right''不为空,此时进行逆序存储,说明已经遍历完了当前节点的左子树,断开 `prev.right` 的连接,即'prev.left=null',然后遍历当前节点的右子树,即 `curr=curr.right`.

  

  2.具体的代码实现

      public List<Integer> postorderTraversal(TreeNode root) {
          List<Integer> res = new ArrayList<>();
          TreeNode dump = new TreeNode(0);//建立一个临时结点
          dump.left = root;  //设置dump的左节点为root
          TreeNode curr = dump;  //当前节点为dump
          while (curr != null) {
              if (curr.left == null) { // 左子树为空，则输出当前节点，然后遍历右子树
                  curr = curr.right;
              } else {
                  // 找到当前节点的前驱节点
                  TreeNode prev = curr.left;
                  while (prev.right != null && prev.right != curr) {
                      prev = prev.right;
                  }
                  if (prev.right == null) {
                      // 将前驱节点的右子树连接到当前节点
                      prev.right = curr;
                      curr = curr.left;
                  } else {
                      reverseAddNodes(curr.left, prev, res);
                      // 前驱节点的右子树已经连接到当前节点，断开连接，输出当前节点，然后遍历右子树
                      prev.right = null;
                      curr = curr.right;
                  }
              }
          }
          return res;
      }
      private void reverseAddNodes(TreeNode begin, TreeNode end, List<Integer> res) {
          reverseNodes(begin, end); //将begin到end的进行逆序连接
          TreeNode curr = end;
          while (true) {//将逆序连接后端begin到end添加
              res.add(curr.val);
              if (curr == begin)
                  break;
              curr = curr.right;
          }
          reverseNodes(end, begin);//恢复之前的连接状态
      }
      /**
       * 将begin到end的进行逆序连接
       *
       * @param begin
       * @param end
       */
      private void reverseNodes(TreeNode begin, TreeNode end) {
          TreeNode prev = begin;
          TreeNode curr = prev.right;
          TreeNode post;
          while (prev != end) {
              post = curr.right;
              curr.right = prev;
              prev = curr;
              curr = post;
          }
      }

  测试:

      public static void main(String[] args) {
          TreeNode root = new TreeNode(1);
          root.left = new TreeNode(2);
          root.left.right = new TreeNode(5);
          root.left.right.right = new TreeNode(7);
          root.right = new TreeNode(3);
          root.left.left = new TreeNode(4);
          root.left.left.left = new TreeNode(6);
          System.out.println(postorderTraversal(root));
      }

  还是这样一颗二叉树,输出如下:

  [6, 4, 7, 5, 2, 3, 1]

Das obige ist der detaillierte Inhalt vonWas ist der Java-Morris-Traversalalgorithmus und seine Anwendung in Binärbäumen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!