CWYAlpha

Just another WordPress.com site

Thought this was cool: 数据结构重读 – 线索二叉树

leave a comment »


我们在二叉树上的先序、中序、后序遍历都是递归或者非递归完成的。

我们只能找到左、右孩子,而不能找到先、中、后序遍历序列下,元素的前驱和后继。

为此,我们可以设计线索二叉树,定义如下:

struct BiTreeThd
{
    int data;
    bool lflag, rflag;
    struct BiTreeThd* lchild, *rchild;
};

如上,多了lflag和rflag:
(1)当有左/右孩子的时候,lflag/rflag为0。此时lchild和rchild指向左孩子和右孩子。
(2)当没有左/右孩子的时候,lflag/rflag为1。此时lchild表示结点的前驱,而rchild表示结点的后继。

这里的前驱和后继,是相对于树的先、中、后序遍历而言的。

一句话:线索二叉树是为了在前、中、后序遍历时能方便找到某个结点的前驱和后继

树和 森林的遍历

To be continued.
from 四号程序员四号程序员: http://www.coder4.com/archives/3202

Written by cwyalpha

五月 24, 2012 在 7:23 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: