c - 不使用递归的二叉树遍历

Question

任何人都可以帮助创建一个二叉树并在 c 中对二叉树进行非递归前序遍历吗？

Answer 1

您可以使用 threaded binary tree 的变体;使用叶节点的 right 链接指向遍历中的下一个节点，类似于

                    +---+
                    | A |
                    +---+
                   /     \
              +---+       +---+
              | B |       | E |
              +---+       +---+
             /     \      ^
        +---+       +---+ |
        | C |       | D | |
        +---+       +---+ |
            |       ^   | |
            +-------+   +-+

叶节点C显式指向D，即前序遍历的下一个节点，D显式指向E。这使得插入和删除操作更加痛苦，但它为您提供了一种简单的前序遍历，无需递归且无需辅助堆栈。