算法导论 习题10.4-5 二叉树的遍历(非递归,O(1)存储)

时间:2023-02-03 19:46:02

看了别人的解答,自己整理的成果。

毫无疑问,这个题目需在有指向父节点的指针存在的情况下才能解决。

为了遍历整棵树,我们得保存结点之间的联系才能进行跳转,访问某个子结点时,需要考虑的因素有:

  1. 它有可能是某个结点的左孩子结点,也有可能是其右孩子结点;
  2. 如果这个结点是在树(包括子树)的左部,我们如何自底向上的找到根结点以访问树的右部,同时又访问了其后代结点;
  3. 结点的关键值输出放在什么位置保证只该结点只输出一次。

非递归和有限的额外存储空间是这个问题的难点。

首先一点很明确,访问结点有先后关系,通常遍历都是从根结点开始自上而下的。由上面的分析可知道,无论怎么访问,都得考虑从当前正在访问的结点返回到其父亲结点上。也就是说,我们可以考虑一种类似“中序”遍历的思想:访问某个结点,马*问其左孩子子树,接着输出自己的值,再访问其右孩子子树,最后借助自己返回到父亲结点。

其次要考虑的就是怎么在访问某个结点的后代结点时,还能够“回去访问”该结点的祖先结点。这就要利用当前正在访问的结点和前一个访问的结点之间的关系了。当前结点和前一个已访问的结点不外乎有三种关系:

  1. 如果已访问结点是当前访问的结点的父亲,说明我们刚刚移动到这个结点,接下来要继续访问它的左孩子结点;
  2. 如果已访问结点是当前访问的结点的左孩子,说明当前节点的左孩子已经被访问,需要继续要访问它的右孩子;
  3. 如果已访问结点是当前访问结点的右孩子,说明当前结点的两棵子树均已遍历完毕,下一步直接访问其父亲节点。
总结一下:其实就是根据最近访问的两个结点的关系决定下一个访问结点;结点的关键值在访问左子树之后、访问右子树之前输出即可。

代码如下:
Binary_Search_Tree(Node* node)
{
Node* prev = root;
Node* cur = root->left;
Node* next = NULL;
while(cur != NULL)
{
if(prev == cur->parent) //前一个结点是当前结点的父亲结点
{
next = cur->left;
if(next == NULL)
{
cout<<cur->value<<endl;
next = cur->right;
if(next == NULL)
{
next = cur->parent;
}
}
}
else
{
if(prev == cur->left) //前一个结点是当前结点的左孩子结点
{
cout<<cur->value<<endl;
next = cur->right;
if(next == NULL)
{
next = cur->parent;
}
}
else //前一个结点是当前结点的右孩子结点
next = cur->parent;
}
prev = cur;
cur = next;
}
}