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

Question

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

Answer 1

这里有一个小例子。

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 2

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

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

• 如果节点有一个右子节点，则向右移动，然后尽可能向左移动

当你从根部向上爬的时候，你就完成了。

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";
}