数据结构笔记——树、森林的遍历

水深无声 2023-02-17 02:13 4阅读 0赞

**目录**

一、树的逻辑结构

二、树的先根遍历

三、树的后根遍历

四、树的层次遍历

五、森林的先序遍历

六、森林的中序遍历

七、总结

## **一、树的逻辑结构** ##

树是n个结点的有限集合，n=0时，称为空树。在任意一棵非空树中应满足：

1）有且仅有一个特定的称为根的结点。

2）当n>1时，其余结点可分为m个互不相交的有限集合T1,T2...Tm，其中每个集合本身又是一棵树，并且称为根节点的子树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70][]

## **二、树的先根遍历** ##

先根遍历：若树非空，先访问根节点，再依次对每棵子树进行先根遍历。（深度优先遍历）

void PreOrder(TreeNode *R){
        if(R != NULL){
            visit(R);
            while(R还有下一个子树T)
                PreOrder(T);
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1][]![20200610180251901.png][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2][]

**先根遍历序列：** A B E K F C G D H I J

注：树的先根遍历序列与这棵树相应二叉树的先序序列相同。

## **三、树的后根遍历** ##

后根遍历：若树非空，先依次对每棵子树进行后根遍历，最后再访问根节点。

void PostOrder(TreeNode *R){
        if(R != NULL){
            while(R还有下一个子树T)
                PostOrder(T);
            visit(R);
        }
    }

**后根遍历序列：**K E F B G C H I J D A

注：树的后根遍历序列与这棵树相应二叉树的中序序列相同。

## **四、树的层次遍历** ##

层次遍历（用队列实现）

①若树非空，则根节点入队

②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队

③重复②直到队列为空

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3][]

![20200610183438875.png][]

## **五、森林的先序遍历** ##

森林：森林是m棵互不相交的树的集合。每棵树去掉根节点后，其各个子树又组成森林。

先序遍历森林：

访问森林中第一棵树的根节点。

先序遍历第一棵树中根节点的子树森林。

先序遍历除去第一棵树之后剩余的树构成的森林。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 4][]

**森林先序遍历序列：**B E K L F C G D H M I J

效果等同于依次对各个树进行先根遍历

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 5][]

**先序遍历序列：**B E K L F C G D H M I J

效果等同于依次对二叉树的先序遍历

## **六、森林的中序遍历** ##

中序遍历森林：

中序遍历森林中第一棵树的根节点的子树森林。

访问第一棵树的根节点。

中序遍历除去第一棵树之后剩余的树构成的森林。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 4][]

**森林中序遍历序列：**K L E F B G C M H I J D

效果等同于依次对各个树进行后根遍历

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 5][]

**中序遍历序列：**K L E F B G C M H I J D

效果等同于依次对二叉树的中序遍历

## **七、总结** ##

## ![20200610184255844.png][] ##

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200610175601920.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200610180015511.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200610180251901.png]: https://img-blog.csdnimg.cn/20200610180251901.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200610180328851.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020061018345231.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200610183438875.png]: https://img-blog.csdnimg.cn/20200610183438875.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200610183651931.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200610183930785.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200610184255844.png]: https://img-blog.csdnimg.cn/20200610184255844.png