无需递归或附加数据结构的二叉搜索树中序遍历

Question

如果二叉搜索树中的节点有指向其父节点的指针，是否可以在不需要递归或其他数据结构的情况下进行中序遍历？

Answer 1

要获得第一个节点，您只需从根开始并尽可能向左走。

从任何节点到下一个节点：

如果节点有右child，则向右走，然后尽量向左走
否则，跟随 parent 指针向上，直到到达右侧的祖先（即，您从左侧 child 到达那里）

当你从根向上时，你就完成了。

Answer 2

这是一个小例子。

Map<TreeNode,TreeNode> parent; // available 

Set<TreeNode> set = new HashSet<>(); // maintain visited nodes

TreeNode curr = root;

while(curr!=null){

  if(!set.contains(curr.left) && curr.left!=null){
     curr = curr.left;
  }else if(!set.contains(curr.right) && curr.right!=null){
     System.out.print(curr.value+" ");
     curr = curr.right;
  }else{
     if(curr.right==null){
        System.out.print(curr.value+" ");
     }
     set.add(curr); // mark it as completely visited
     curr = parent.get(curr);
  }
}

Answer 3

在遍历过程中跟踪前一个节点，这将有助于决定下一步要走的路。

在 C# 中：

class Node {
    /* ... */
    public void inorder() {
        Node curr = this;
        Node prev = null;
        Node next = null;
        while (curr != null) {
            if (curr.right != null && prev == curr.right) {
                next = curr.parent;
            } else if (curr.left == null || prev == curr.left) {
                Console.WriteLine(curr.data);  // <-- visit the node.
                next = curr.right != null ? curr.right : curr.parent;
            } else {
                next = curr.left;
            }
            prev = curr;
            curr = next;
        }
    }
};

在 C++ 中它可能如下所示：

void inorder(Node* root) {
    Node * curr = root;
    Node * prev = NULL;
    Node * next = NULL;
    while (curr != NULL) {
        if (curr->right != NULL && prev == curr->right) {
            next = curr->parent;
        } else if (curr->left == NULL || prev == curr->left) {
            cout << curr->data << " ";  // <-- visit the node.
            next = curr->right != NULL ? curr->right : curr->parent;
        } else {
            next = curr->left;
        }
        prev = curr;
        curr = next;
    }
    cout << "\n";
}

无需递归或附加数据结构的二叉搜索树中序遍历

Binary Search Tree In-order traversal without recursion or additional data structures

algorithm

traversal