直接回答你的問題,我認爲這個數字是不準確,你的情況的第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