首页 > 代码库 > 马程序员学习笔记——红黑树解析三

马程序员学习笔记——红黑树解析三

---------------------- ASP.Net+Unity开发.Net培训、期待与您交流! ----------------------

六、树的前序、中序、后序

前序遍历(根左右): 
    1.访问根节点 
    2.前序遍历左子树 
    3.前序遍历右子树 
中序遍历(左根右): 
    1.中序遍历左子树 
    2.访问根节点 
    3.中序遍历右子树 
后序遍历(左右根): 
    1.后序遍历左子树 
    2.后序遍历右子树 
    3.访问根节点


扩展:已知前序、中序遍历,求后序遍历?

例:

前序遍历: GDAFEMHZ

中序遍历: ADEFGHMZ

分析:第一步:因为前序遍历的规则是根左右,所以前序的第一个元素必定是根元素,此例中为G

第二步:再看中序遍历,由第一步中得到的根G,可以把中序分成两部分,左子树(ADEF)和右子树(HMZ)

第三步:再根据前序遍历,可以得到左子树的前序为(DAFE),那么这个根D必定是之前树根G的左孩子,然后左子树中序为(ADEF)(第二步得到),这样就形成了一组新的前序和中序。

第四步:同理,右子树的前序(MHZ)的根节点M为之前根G的右孩子,也同样有一组新的前序和中序。

第五步:上面的过程其实可以递归调用——

1.先找到根节点,然后划分左子树和右子树,

2.左子树递归

3.右子树递归

4.加上根节点

本例答案:
后序:AEFDHZMG

note:这三者中,已知两个,可以求得另一个(也就是说,已知两个便可确定一个树的布局)。


七、前趋和后继

这里讨论的是中序前趋和中序后继。

因为前序、中序和后序中,一般都只是用中序(因为中序是从小到大排序)。

定义:

元素N的前趋:整个树中只比N小的那个元素。

元素N的后继:整个树中只比N大的那个元素。

在二叉搜索树中(包含红黑树),一个节点的前趋,只能在两个地方:

1.该节点左子树中的最大元素,即左子树中的最右节点

2.如果该节点左子树为空,那么它的前趋是它祖先节点中第一个为右分支的节点。

示例:下图中F的中序前趋为B



后继的情况和前趋刚好对称。

note:在红黑树的删除操作中,如果被删元素有两非空儿子,那么其实真正删除的其实是它的前趋元素了。


八、树的遍历

通过了解六和七中的中序、前趋和后继,那么,要遍历一个红黑树就很简单了。

首先,找到树中的最小元素(整棵树的最左节点),然后一步一步求它的后继就可以了,直到整个树的最右节点,就结束


至此为止,通过红黑树解释的三篇文章,我们已经详细分析了一棵红黑树的建立,插入元素,删除元素,遍历元素,

希望能给初学者一点帮助,如果有什么理解不当之处,欢迎指正。

至于红黑树的java实现,请关注小弟的下一篇文章。




本文参考:

红黑树算法的实现与剖析:http://blog.csdn.net/v_JULY_v/article/details/6109153

红黑树的介绍和实现(一):http://saturnman.blog.163.com/blog/static/5576112010969420383



---------------------- ASP.Net+Unity开发.Net培训、期待与您交流! ----------------------详细请查看:http://edu.csdn.net