Обход PreOrder и PostOrder путем изменения обхода Морриса

Question

Обход Морриса отлично работает для обхода InOrder с O (n) временем и O (1) пространством. Возможно ли, просто изменив несколько вещей, добиться прохождения PreOrder и PostOrder, используя один и тот же алгоритм.

Answer 1

Пост-заказ может быть достигнут простым изменением порядка алгоритма Морриса.Для объяснения,

Реализация Python Morris в порядке:

def in_order(root):
    if not root:
        return []
    current = root
    in_order_list = []
    while current:
        if not current.left:
            in_order_list += [current.val] # Mark current as visited
            current = current.right
        else:
            # find the right most of the left tree
            predecessor = current.left
            while (predecessor.right) and (predecessor.right != current):
                predecessor = predecessor.right
            # and create a link from this to current
            if not predecessor.right:
                predecessor.right = current
                current = current.left
            else: # now bring back the tree to it's original shape
                 predecessor.right = None
                 in_order_list += [current.val]
                 current = current.right
    return in_order

Для пост-заказа начните с current, а если current.right пуст - начните смотреть влево.Если нет, найдите самый левый предшественник и свяжите левую часть этого предшественника с текущим.(Короче говоря, переверните левые в порядке прав и продолжайте вставлять узлы в начало списка посещенных;))

Post-order Python Morris

def post_order(root):
    if not root:
        return []
    current = root
    post_order_list = []
    while current:
        if not current.right:
            post_order_list.insert(0, current.val)
            current = current.left
        else:
            # find left most of the right sub-tree
            predecessor = current.right
            while (predecessor.left) and (predecessor.left != current):
                predecessor = predecessor.left
            # and create a link from this to current
            if not predecessor.left:
                post_order_list.insert(0, current.val)
                predecessor.left = current
                current = current.right
            else:
                predecessor.left = None
                current = current.left
    return post_order

Answer 2

Я не думаю, что мы можем реализовать почтовый заказ, используя темы.В почтовом заказе мы должны пройти обоих детей, а затем их родителей.Мы можем установить ссылку от дочернего элемента к родительскому, но после этого мы не можем перейти к этому родительскому элементу, потому что они не являются ссылками.мы можем создать поток в правом узле 4, указывая на узел 5.Мы можем создать поток в правом узле 5, указывая на узел 2.

Но в узле 2 нет пустых указателей для создания каких-либо потоков.У узла 2 уже есть указатели, указывающие на узлы 4 и 5.

Answer 3

Я знаю решение для Предзаказа с использованием morison Algo.

вот код Java

public static void morisonPreOrder(TreeNode root) {
    TreeNode curr = root, tmp=null;

    while (curr != null) {
        if(curr.leftNode == null) {
            System.out.print(curr.value + "  ");
            curr = curr.rightNode;
        } else {
            tmp = curr.leftNode;
            while (tmp.rightNode != null && tmp.rightNode != curr) {
                tmp = tmp.rightNode;
            }

            if(tmp.rightNode == null) {
                System.out.print(curr.value + "  ");
                tmp.rightNode = curr;
                curr = curr.leftNode;
            } else {
                tmp.rightNode = null;
                curr = curr.rightNode;
            }
        }
    }
}

Answer 4

Ответ на предварительный заказ был дан выше.

Для ответа на обратный заказ также ответ "Да".

Единственные изменения, которые вам нужны: 1. Когда правильный ребенокЕсли предшественником является текущий узел, установите для правого дочернего элемента значение null и выведите обратно все узлы от левого дочернего элемента текущего узла к предшественнику .2. Установите фиктивный узел и установите его левый дочерний элемент в корень дерева.

Код Java написан здесь:

    private void printPostTraverse(List<Integer> traverseList, TreeNode start, TreeNode end) {
        TreeNode node = start;
        int insertIndex = traverseList.size();
        while (node != end) {
            traverseList.add(insertIndex, node.val);
            node = node.right;
        }
        traverseList.add(insertIndex, node.val);
    }

    public List<Integer> postorderMorrisTraversal(TreeNode root) {
        List<Integer> traverseList = new ArrayList<>();
        TreeNode dummy = new TreeNode(-1);
        dummy.left = root;
        TreeNode cur = dummy, prev = null;
        while (cur != null) {
            if (cur.left == null) {
                cur = cur.right;
            } else {
                prev = cur.left;
                while (prev.right != null && prev.right != cur)
                    prev = prev.right;

                if (prev.right == null) {
                    prev.right = cur;
                    cur = cur.left;
                } else {
                    // Modification on get the traversal list
                    printPostTraverse(traverseList, cur.left, prev);
                    prev.right = null;
                    cur = cur.right;
                }
            }
        }
        return traverseList;
    }

Answer 5

/ Реализация предварительного заказа без стека и рекурсии /

private static void morrisPreorder(){
        while(node != null){
            System.out.println(node.getData());
            if (node.getLeftNode() == null){
                node = node.getRightNode();
            } else {
                Node rightnode = node.getRightNode();
                Node current = node.getLeftNode();
                while(current.getRightNode() != null && current.getRightNode().getData() != node.getData())
                    current = current.getRightNode();
                if(current.getRightNode() == null){
                    current.setRightNode(node.getRightNode());
                    node = node.getLeftNode();
                } else {
                    node = node.getRightNode();
                }
            }
        }
    }

Answer 6

Вот пример кода для обхода предварительного заказа с использованием модифицированного обхода Морриса.

Аналогичным способом вы можете изменить левую ссылку правого предшественника для прохождения пост-заказа.

У меня не было времени проверить код. Пожалуйста, дайте мне знать, если что-то не так в этом коде.

void preOrderNonRecursive( BSTNode* root )
{
    if(!root)
        return;
    BSTNode* cur = root;

    while(cur)
    {
        bool b = false;
        BSTNode* pre = NULL;
        if (cur->left)
        {
            pre = cur->left;
            while(pre->right && pre->right != cur)
                pre = pre->right;
            if(!pre->right)
            {
                pre->right = cur;
                b = true;
            }               
            else
                pre->right = NULL;
        }   
        else
            printf("%d\n",cur->val);

        if(b)
        {   
            printf("%d\n",cur->val);
            cur = cur->left;        
        }
        else            
            cur = cur->right;
    }
}