c - 如何使用 while 循环遍历二叉树？

Question

我只是想知道如何使用 while 循环遍历二叉树(不是递归完成的)。

我有我的树:

typedef struct Node *BSTree;
typedef struct Node {
   int  key;
   BSTree left, right;
} Node;

我只想知道如何在 while 循环中访问每个节点。有人可以告诉我吗？我无法理解它。

Answer 1

您需要引用父节点。

如果 root != null 将 root 存储在当前。如果 current 有左 child ，则将 current 设置为左​​ child 。如果没有左 child ，有右 child ，就把右 child 存入current。如果current中没有当前节点的左右子store parent。

如果你采用这种方式，你将陷入无限循环，但如果你将前一个存储在当前节点之前，并比较当前节点和最后一个节点之间的关系，你就可以遍历整棵树。

这不是完整的答案，但它会有所帮助。