直接回答你的问题,我认为这个数字是不准确,你的情况的第1步,从节点“80”边缘节点“60”不应该被删除。步骤1中唯一的改变是将节点“70”的右点重定向到节点“80”(参见步骤1),这指示算法经过节点“80”的左子树之后的返回路径。
步骤1:
80
/^ \
60 | 100
\ | /
70 90
/
65
/
63
\
64
添加来自节点“70”返回路径到节点“80”,作为当前节点“60”的左侧点之后为NULL,则当前节点将被设置作为节点“70”。同时,节点“65”的右侧点将被重定向到节点“70”
步骤2:
80
/^ \
60 | 100
\ | /
70 90
/^
/|
65
/
63
\
64
详情莫里斯的序遍历的代码被列为如下。
假设我们有一个节点结构等:
/* A binary tree tNode has data, pointer to left child
and a pointer to right child */
struct tNode
{
int data;
struct tNode* left;
struct tNode* right;
};
和遍历是:
/* Function to traverse binary tree without recursion and
without stack */
void MorrisTraversal(struct tNode *root)
{
struct tNode *current,*pre;
if(root == NULL)
return;
current = root;
while(current != NULL)
{
/* This means there is no left sub-tree for current node,
then just print current node, and go to the right "child" node.
The right "child" node may be either its true child node,
or the returning path for "60" sub-tree (like "70" to "80") */
if(current->left == NULL)
{
printf(" %d ", current->data);
current = current->right;
}
else
{
/* before going to the left sub-tree, we need to find a returning path
to current node (such as when current node is "80", and we want to
go to "60", so we need to save the returning path from left sub-tree
to "80"). It is easy to imagine that we need to return to the current
node when we arriving the right-most node of current left sub-tree.
Therefore, we just go to the right-most node (the first condition in
while) and set the returning path at "pre->right == NULL" block, as
well as updating the current node. Another situation is that when we
arrive at the left-most leaf node (if not exist, it means current->left
is NULL, and we won't go into this block), we have already set the right
point of left-most leaf node as the returning node (it un-satisfies the
second condition of while loop), and then we will recover the right
point of this leaf node in the next "else" block.
*/
pre = current->left;
while(pre->right != NULL && pre->right != current)
pre = pre->right;
/* Make current as right child of its inorder predecessor */
if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}
/* Revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else `enter code here`
{
pre->right = NULL;
printf(" %d ",current->data);
current = current->right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */
}
我用于编码序遍历,而不是莫里斯序遍历而不同这样的事实它使用线程而不是堆栈或递归。我想问你,如果你明白基本的inorder遍历,或者你只能使用morris版本。 –
@Setilă我很好地理解inorder遍历,并且我刚刚完成了对添加,删除,搜索方法的Threaded树的编码。我为morris inorder遵循的代码如上。 – ChrisOdney