Morris Inorder Traversal  


ระดับความยาก กลาง
ต้นไม้ ทรีทราเวอร์ซัล

เราสามารถสำรวจต้นไม้ใน ไม่เป็นระเบียบ แฟชั่นซ้ำ ๆ โดยใช้ กองแต่มันกินพื้นที่ ดังนั้นในปัญหานี้เราจะสำรวจต้นไม้โดยไม่ใช้พื้นที่เชิงเส้น แนวคิดนี้เรียกว่า Morris Inorder Traversal หรือ Threading in Binary trees

ตัวอย่าง

          2

       /      \

     1           3

  /      \

4          5
4 1 5 2 3
       3

    /      \

  1          4
            
          /      \
 
        2          5
1 3 2 4 5

เข้าใกล้

แนวคิดคือเราสามารถสำรวจต้นไม้ได้โดยไม่ต้องมีพื้นที่ของสแต็ก (หรือพื้นที่เสริมของการเรียกซ้ำ) ถ้าเรา อย่าสูญเสียที่อยู่ของโหนดใด ๆ เราไปเยี่ยมชมก่อนหน้านี้โดยไม่ได้จัดเก็บไว้ในหน่วยความจำ วิธีนี้เรียกว่า Morris Inorder Traversal.

แต่ไม่อนุญาตให้มีช่องว่างเราจะจัดเก็บที่อยู่ของโหนดได้อย่างไร? แนวคิดคือการเปลี่ยนโครงสร้างของทรีด้วยวิธีดังกล่าวหลังจากเยี่ยมชมโหนดบางโหนดของทรีย่อยหนึ่งจากโหนดรูทเราสามารถกลับไปที่โหนดรูทเพื่อประมวลผลทรีย่อยอื่น ๆ สมมติว่าเราไปเยี่ยมชมทรีย่อยด้านซ้ายอย่างสมบูรณ์และเพิ่มตัวชี้จากโหนดบางส่วนของทรีย่อยด้านซ้ายไปยังรูทอีกครั้ง ตอนนี้เราสามารถประมวลผลทรีย่อยที่ถูกต้องได้โดยกลับมาที่รูทเดิม ใน Morris Inorder Traversal เราเชื่อมโยงลำดับก่อนหน้าของรูท (ในทรีย่อยด้านซ้าย) เข้ากับตัวมันเอง

Morris Inorder Traversal C ++ Tutorialหมุด

กระบวนการเพิ่มพอยน์เตอร์นี้ (หัวข้อ) จากลำดับก่อนหน้าไปยังรูทถูกเรียก เธรด อีกครั้งเราไม่ต้องการรบกวนโครงสร้างของต้นไม้ดังนั้นเราจะออกแบบอัลกอริทึมที่ลบลิงก์และ ยังไม่ได้อ่าน ต้นไม้ถึง คงโครงสร้างเดิมไว้.

ดูสิ่งนี้ด้วย
ลำดับต่อมาที่ยาวที่สุด

ขั้นตอนวิธี

  1. เริ่มต้นโหนดปัจจุบันเป็นรูทของทรี
  2. ทำซ้ำไปเรื่อย ๆ จนกว่าเราจะถึงเงื่อนไขที่ โหนดปัจจุบัน จะกลายเป็น เป็นโมฆะ 
    • ถ้า ซ้าย แผนผังย่อยของรูทปัจจุบันคือ NULL :
        • ตอนนี้เราสามารถพิมพ์รูทและย้ายไปยังทรีย่อยที่ถูกต้องได้ดังนั้น currentNode = currentNode-> right
    • ถ้า ซ้าย แผนผังย่อยของรูทปัจจุบันคือ  ไม่ NULL :
        • ในกรณีนี้เรา ยังไม่ได้อ่าน / เธรด โหนดขวาสุดในทรีย่อยด้านซ้าย (ลำดับก่อนหน้า) ของโหนดปัจจุบันไปเอง
            • temp = currentNode-> ซ้าย;
            • ในขณะที่ temp-> ขวาคือ ไม่ NULL หรืออุณหภูมิคือ ไม่ใช่ currentNode
              • temp = temp-> ขวา
        • ถ้า temp-> ถูกต้อง NULL:
            • ลบเธรดเป็น temp-> right = NULL
            • ประมวลผลทรีย่อยที่ถูกต้อง currentNode = currentNode-> right
        • ถ้า temp-> ถูกต้อง ไม่เป็นโมฆะ:
            • เธรดโหนดนี้เป็น temp-> right = currentNode
            • ประมวลผลทรีย่อยด้านซ้ายตอนนี้ currentNode = currentNode-> left

การใช้งาน Morris Inorder Traversal

โปรแกรม C ++

#include <bits/stdc++.h>

using namespace std;

struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};


void morrisInorder(treeNode* &root)
{
    treeNode* currentNode = root;
    while(currentNode != NULL)
    {
        if(currentNode->left == NULL)
        {
            cout << currentNode->value << " ";
            currentNode = currentNode->right;
        }
        else
        {
            treeNode* temp = currentNode->left;
            while((temp->right != NULL) && (temp->right != currentNode))
                temp = temp->right;

            if(temp->right == NULL)
            {
                temp->right = currentNode;
                //threading
                currentNode = currentNode->left;
            }
            else
            {
                cout << currentNode->value << " ";
                temp->right = NULL;
                //unthreading
                currentNode = currentNode->right;
            }
        }
    }
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->left->left = new treeNode(4);
    root->left->right = new treeNode(5);

    morrisInorder(root);
    return 0;
}
4 1 5 2 3

โปรแกรม Java

class treeNode
{
    int value;
    treeNode left, right;

    public treeNode(int x)
    {
        value = x;
        left = right = null;
    }
}

class BinaryTree
{
    treeNode root;
    void MorrisInorder()
    {
        treeNode currentNode = root;

        while(currentNode != null)
        {
            if(currentNode.left == null)
            {
                System.out.print(currentNode.value + " ");
                currentNode = currentNode.right;
            }
            else
            {
                treeNode temp = currentNode;
                while(temp.right != null && temp.right != currentNode)
                    temp = temp.right;

                if(temp.right == null)
                {
                    temp.right = currentNode;
                    currentNode = currentNode.left;
                }
                else
                {
                    temp.right = null;
                    System.out.print(currentNode.value + " ");
                    currentNode = currentNode.right;
                }
            }
        }

    }

    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new treeNode(2);
        tree.root.left = new treeNode(1);
        tree.root.left.left = new treeNode(4);
        tree.root.left.right = new treeNode(5);
        tree.root.right = new treeNode(3);
        tree.MorrisInorder();
    }
}
4 1 5 2 3

การวิเคราะห์ความซับซ้อนของ Morris Inorder Traversal

ความซับซ้อนของเวลา

บน), โดยที่ N คือจำนวนโหนดในทรี เป็นที่แน่นอนว่าเราเยี่ยมชมทุกโหนด 2 ครั้งเนื่องจากทั้งหมดต้องผ่านกระบวนการเธรดและไม่ได้อ่าน แต่ความซับซ้อนของเวลายังคงเป็นเส้นตรง

ดูสิ่งนี้ด้วย
ตรวจสอบว่าทุกระดับของ Binary Tree ทั้งสองเป็นแอนนาแกรมหรือไม่

ความซับซ้อนของอวกาศ

O (1), เมื่อเราใช้พื้นที่คงที่สำหรับการประกาศตัวแปรบางตัว แต่ไม่มีการใช้พื้นที่เสริมอื่น ๆ เพื่อวัตถุประสงค์ใด ๆ นั่นคือสิ่งที่ Morris Inorder Traversal สัญญาไว้

1