Morris Inorder Traversal


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຕົ້ນໄມ້ Traversal ຕົ້ນໄມ້

ພວກເຮົາສາມາດຂ້າມຕົ້ນໄມ້ໃນ ອິນບອກ ຄົນອັບເດດ: iteratively, ການນໍາໃຊ້ stack, ແຕ່ມັນໃຊ້ເວລາຫວ່າງ. ສະນັ້ນ, ໃນບັນຫານີ້, ພວກເຮົາ ກຳ ລັງຈະຂ້າມຕົ້ນໄມ້ໂດຍບໍ່ມີພື້ນທີ່ເສັ້ນຊື່. ແນວຄິດນີ້ຖືກເອີ້ນວ່າ Morris Inorder Traversal ຫຼື Threading ໃນຕົ້ນໄມ້ຖານສອງ.

ຍົກຕົວຢ່າງ

          2

       /      \

     1           3

  /      \

4          5
4 1 5 2 3
       3

    /      \

  1          4
            
          /      \
 
        2          5
1 3 2 4 5

ວິທີການ

ແນວຄວາມຄິດແມ່ນ: ພວກເຮົາສາມາດຂ້າມຕົ້ນໄມ້ໂດຍບໍ່ມີພື້ນທີ່ຂອງທ່ອນໄມ້ (ຫຼືພື້ນທີ່ຊ່ວຍໃນການເອີ້ນຄືນ) ຖ້າພວກເຮົາ ບໍ່ສູນເສຍທີ່ຢູ່ຂອງ node ໃດໆ ພວກເຮົາໄດ້ໄປຢ້ຽມຢາມກ່ອນ ໜ້າ ນີ້ໂດຍບໍ່ເກັບຮັກສາໄວ້ໃນຄວາມຊົງ ຈຳ. ວິທີການນີ້ເອີ້ນວ່າ Morris Inorder Traversal.

ແຕ່ຖ້າບໍ່ມີພື້ນທີ່ໃດໆອະນຸຍາດ, ທ່ານສາມາດເກັບທີ່ຢູ່ຂອງຂໍ້ ກຳ ນົດໄດ້ແນວໃດ? ແນວຄວາມຄິດກໍ່ຄືການປ່ຽນໂຄງສ້າງຂອງຕົ້ນໄມ້ໃນລັກສະນະດັ່ງກ່າວ, ວ່າຫລັງຈາກໄດ້ໄປເບິ່ງຂໍ້ສະເພາະໃດ ໜຶ່ງ ຂອງ ໜຶ່ງ ປະໂຫຍກຈາກຮາກຮາກ, ພວກເຮົາສາມາດກັບໄປຫາຮາກຂອງຮາກເພື່ອປະມວນຜົນລັດຍ່ອຍອື່ນໆ. ບອກວ່າພວກເຮົາໄດ້ເຂົ້າເບິ່ງລັດຖະບັນຍັດເບື້ອງຊ້າຍຢ່າງຄົບຖ້ວນ, ແລະເພີ່ມຕົວຊີ້ຈາກບາງສ່ວນຂອງ ດຳ ລັດດ້ານຊ້າຍໄປຫາຮາກອີກຄັ້ງ. ດຽວນີ້, ພວກເຮົາສາມາດປະມວນຜົນລັດຖະ ທຳ ມະນູນທີ່ຖືກຕ້ອງໂດຍການກັບຄືນມາສູ່ຮາກເດີມ. ໃນ Morris Inorder Traversal, ພວກເຮົາເຊື່ອມໂຍງກັບຜູ້ຕິດຕັ້ງເບື້ອງຕົ້ນຂອງຮາກ (ໃນລັດຖະບັນຍັດເບື້ອງຊ້າຍ) ຂອງມັນເອງ.

ການສອນ Tutorial Morris Inorder Traversal C ++

ຂັ້ນຕອນການເພີ່ມຈຸດຊີ້ບອກ (ກະທູ້) ຈາກ predecessor inorder ກັບຮາກເອີ້ນວ່າ ກະທູ້. ອີກເທື່ອ ໜຶ່ງ, ພວກເຮົາບໍ່ຕ້ອງການລົບກວນໂຄງສ້າງຂອງຕົ້ນໄມ້, ສະນັ້ນພວກເຮົາຈະອອກແບບສູດການຄິດໄລ່ທີ່ຈະລຶບການເຊື່ອມໂຍງແລະ ໄຮ້ສາລະ ຕົ້ນໄມ້ທີ່ ຮັກສາໂຄງສ້າງເດີມຂອງມັນໄວ້.

ລະບົບວິເຄາະ

  1. ເລີ່ມຕົ້ນ node ປັດຈຸບັນເປັນຮາກຂອງຕົ້ນໄມ້.
  2. ຮັກສາ iterating ຈົນກ່ວາພວກເຮົາສາມາດບັນລຸສະພາບການທີ່ໄດ້ node ປະຈຸບັນ ກາຍເປັນ NULL. 
    • ຖ້າ ໄວ້ subtree ຂອງຮາກໃນປະຈຸບັນແມ່ນ NULL :
        • ດຽວນີ້ພວກເຮົາສາມາດພິມຮາກແລະຍ້າຍໄປທີ່ ດຳ ລັດທີ່ຖືກຕ້ອງ, ສະນັ້ນ currentNode = currentNode-> ຖືກ.
    • ຖ້າ ໄວ້ subtree ຂອງຮາກໃນປະຈຸບັນແມ່ນ  ບໍ່ NULL :
        • ໃນກໍລະນີນີ້, ພວກເຮົາ unthread / ກະທູ້ ຂໍ້ທີ່ຖືກຕ້ອງທີ່ສຸດໃນລັດຖະບັນຍັດເບື້ອງຊ້າຍ (ຜູ້ປະສານງານກ່ອນ) ຂອງ node ປັດຈຸບັນ
            • temp = currentNode-> ຊ້າຍ;
            • ໃນຂະນະທີ່ temp-> ຖືກຕ້ອງ ບໍ່ NULL ຫຼື temp ແມ່ນ ບໍ່ປະຈຸບັນ
              • temp = temp-> ຖືກ
        • ຖ້າ temp-> ຖືກຕ້ອງ NULL:
            • ເອົາກະທູ້ອອກເປັນ temp-> ສິດ = NULL
            • ປະມວນຜົນ ດຳ ລັດທີ່ຖືກຕ້ອງ, currentNode = currentNode-> ຖືກ
        • ຖ້າ temp-> ຖືກຕ້ອງ ບໍ່ ໝາຍ:
            • ກະທູ້ຂໍ້ນີ້ temp-> right = currentNode
            • ປະມວນຜົນປະໂຫຍກຊ້າຍຢູ່ດຽວນີ້, currentNode = currentNode-> ຊ້າຍ

ການຈັດຕັ້ງປະຕິບັດ 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 Program

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), ບ່ອນທີ່ N ແມ່ນຈໍານວນຂອງຂໍ້ໃນຕົ້ນໄມ້. ມັນແນ່ນອນວ່າພວກເຮົາໄປຢ້ຽມຢາມທຸກໆໂຫນດຢ່າງແນ່ນອນ 2 ຄັ້ງ, ຍ້ອນວ່າພວກເຂົາທຸກຄົນແມ່ນຜ່ານຂັ້ນຕອນການເຮັດກະທູ້ແລະບໍ່ໄດ້ອ່ານ. ແຕ່ວ່າ, ຄວາມສັບສົນເວລາຍັງຄົງເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (1), ດັ່ງທີ່ພວກເຮົາໃຊ້ພື້ນທີ່ຄົງທີ່ ສຳ ລັບການປະກາດຕົວແປບາງຢ່າງ. ແຕ່ວ່າ, ບໍ່ມີບ່ອນຊ່ວຍອື່ນໃດທີ່ໃຊ້ເພື່ອຈຸດປະສົງໃດໆ. ນັ້ນແມ່ນສິ່ງທີ່ Morris Inorder Traversal ສັນຍາກ່ຽວກັບ.