【数据结构】二叉树的遍历

举报
陶然同学 发表于 2022/09/25 01:17:37 2022/09/25
【摘要】 文章目录 5.3 二叉树的遍历 5.3.1 概述 5.3.2 遍历方式【重点】 5.3.3 遍历方式:递归实现【重点】 5.3.4 遍历方式:非递归实现 5.3 二叉树的遍历 5.3.1 概述 二叉树的遍历:沿着某条搜索路径对二叉树中的结点进行访问,使得每个结点均被访问一次,而且仅被访问一次。“访问”的含义较为广泛,例...

文章目录

5.3 二叉树的遍历

5.3.1 概述

5.3.2 遍历方式【重点】

5.3.3 遍历方式:递归实现【重点】

5.3.4 遍历方式:非递归实现

5.3 二叉树的遍历

5.3.1 概述

  • 二叉树的遍历:沿着某条搜索路径对二叉树中的结点进行访问,使得每个结点均被访问一次,而且仅被访问一次。“访问”的含义较为广泛,例如:输出结点信息。

  • 二叉树有3条搜索路径:

    1. 先上后下

    2. 先左后右

    3. 先右后左

  • 对应3条搜索路径,二叉树有7种遍历方式:

    • 先上后下

      1. 层次遍历

    • 先左后右 (D data根、 L left左、R right 右)

      1. DLR (先根遍历、先序遍历、先根序遍历)

      2. LDR (中根遍历、中序遍历、中根序遍历)

      3. LRD (后根遍历、后序遍历、后根序遍历)

    • 先右后左

      1. DRL

      2. RDL

      3. RLD

  • 需要遍历的二叉树

     

    A

    B

    C

    D

    E

    F

    G

    H

    K

5.3.2 遍历方式【重点】

1) 层次遍历

  • 若二叉树为空,则为空操作;否则,按自上而下先访问第0层的根节点,然后再从左到右依次访问各层次中的每一个结点。

  • 层次遍历序列

    ABECFDGHK

2)先根(序)遍历 DLR

  • 若二叉树为空,则为空操作,否则

    1. 访问根节点

    2. 先根遍历左子树

    3. 先根遍历右子树

    4.  

  • 先根遍历序列

    ABCDEFGHK

3)中根(序)遍历 LDR

  • 若二叉树为空,则为空操作;否则

    1. 中根遍历左子树

    2. 访问根节点

    3. 中根遍历右子树

  • 中根遍历序列

    BDCAEHGKF

 

4)后根(序)遍历LRD

  • 若二叉树为空,则为空操作;否则

    1. 后根遍历左子树

    2. 后根遍历右子树

    3. 访问根节点

  • 后根遍历序列

    DCBHKGFEA

 

5)练习

  • 练习1:

 

先根序遍历:ABDEGCFH

中根序遍历:DBGEAFHC

后根序遍历:DGEBHFCA

  • 练习2:

     

    先根序遍历:ABDEGJHCFIKL

    中根序遍历:DBJGEHACKILF

    后根序遍历:DJGHEBKLIFCA

  • 练习3:

     

    先根序遍历:ABCDEFGHK

    中根序遍历:BDCAEHGKF

    后根序遍历:DCBHKGFEA

5.3.3 遍历方式:递归实现【重点】

1)算法:先根(序)遍历 DLR

public void preRootTraverse(BiTreeNode T) {
    if(T != null) {
        System.out.print(T.data);       //输出根元素
        preRootTraverse(T.lchild);      //先根遍历左子树
        preRootTraverse(T.rchild);      //先根遍历右子树
    }
}

2)算法:中根(序)遍历 LDR

public void inRootTraverse(BiTreeNode T) {
    if(T != null) {
        inRootTraverse(T.lchild);       //中根遍历处理左子树
        System.out.print(T.data);       //访问根节点
        inRootTraverse(T.rchild);       //中根遍历处理右子树
    }
}

3)算法:后根(序)遍历LRD

public void postRootTraverse(BiTreeNode T) {
    if(T != null) {
        postRootTraverse(T.lchild);     //后根遍历左子树
        postRootTraverse(T.rchild);     //后根遍历右子树
        System.out.print(T.data);       //访问根结点
    }
}

4)动画演示:后根遍历

 

5.3.4 遍历方式:非递归实现

1)分析:先根(序)遍历 DLR

  • 借助一个==栈==来记录当前被访问结点的右孩子结点,以便遍历完一个结点的左子树后,可以继续遍历该结点的右子树。

  • 实现思想:

    1. 将根节点压栈

    2. 从栈顶获得需要遍历的结点A,并访问结点A。

    3. 此时结点A有左孩子直接访问,结点A有右孩子压入栈顶

    4. 同时沿着左子树继续搜索,重复步骤3

    5. 当左子树访问完成后,重复步骤2依次访问对应的右子树

2)算法:先根(序)遍历 DLR【重点】

public void preRootTraverse() {
    BiTreeNode T = root;
    if( T != null ) {
        LinkStack S = new LinkStack();      // 创建栈记录没有访问过的右子树
        S.push(T);                          // 将根节点压入栈顶
        while(!S.isEmpty()) {               // 栈中只要有数据,表示继续遍历
            T = S.pop();                    // 弹出栈顶数据
            System.out.print(T.data);       // 结点被访问
            while(T != null) {              // T指针,访问每一个左孩子
                if(T.lchild != null) {      // 输出左孩子
                    System.out.print(T.lchild.data);
                }
                if(T.rchild != null) {      // 将右孩子压栈
                    T.push(T.rchild);
                }
                T = T.lchild;               // 访问下一个左孩子
            }
        }
    }
}

3)分析:中根(序)遍历 LDR

  • 借助一个==栈==来记录遍历过程中所经历的而未被访问的所有结点,以便遍历完左子树后能顺利的返回到它的父节点。

  • 实现思想

    1. 从非空二叉树的根节点出发

    2. 沿着该结点的左子树向下搜索,在搜索过程中将遇到的每一个结点依次压栈,直到二叉树中最左下结点压栈为止,

    3. 然后从栈中弹出栈顶结点并对其进行访问,访问完成后再进入该结点的右子树,

    4. 并用上述相同的方法去遍历该结点的右子树,直到二叉树中所有的结点都被访问。

4)算法:中根(序)遍历 LDR

public void inRootTraverse() {
    BiTreeNode T = root;
    if(T != null) {
        LinkStack S = new LinkStack();
        S.push(T);                          //将根节点压入到栈顶
        while( !S.isEmpty() ) {             //栈中有数据,表示遍历未完成
            //1 将所有的左孩子压栈
            while(S.peek() != null) {       //栈顶的元素不为空,注意:不是弹栈
                // 获得栈顶,
                BiTreeNode temp = (BiTreeNode)S.peek();
                // 并将左孩子压入栈顶
                S.push(temp.lchild);
            }
            S.pop();                        //将栈顶的空元素弹出
            
            //2 依次弹出栈,访问当前节点,如果有右孩子继续压栈
            if(! S.isEmpty()) {
                T = (BiTreeNode)S.pop();
                System.out.print(T.data);       //访问栈顶
                S.push(T.rchild);
            }
        }
    }
}

5)分析:后根(序)遍历LRD

  • 借助一个栈用记载遍历过程中所经历而未被访问的所有结点。

    • 确定顶点结点是否能访问,需要知道该结点的右子树是否被遍历完成。

    • 引入两个变量,一个访问标记变量flag和一个结点指针p

      • flag永不标记当前栈顶结点是否被访问

      • p指向当前遍历过程中最后一个被访问的结点。

  • 实现思想

    1. 从非空二叉树的根节点出发

    2. 将所有的左孩子相继压栈,

    3. 然后获得栈中每个结点A,如果该结点A没有右孩子或右孩子已经访问过,将访问结点A

    4. 如果结点A有右孩子或右孩子未被访问过,继续压栈

    5. 通过标记,使程序开始出了新添加进入的结点。

6)算法:后根(序)遍历LRD

public void postRootTraverse() {
    BiTreeNode T = root;
    if( T != null) {
        LinkStack S = new LinkStack();
        S.push(T);
        // 声明两个变量
        Boolean flag;               //用于记录是否被访问
        BiTreeNode p;               //用于记录上一次处理的结点
        while(! S.isEmpty() ) {
            //1 将所有的左孩子压栈
            while(S.peek() != null) {       //栈顶的元素不为空,注意:不是弹栈
                // 获得栈顶,
                BiTreeNode temp = (BiTreeNode)S.peek();
                // 并将左孩子压入栈顶
                S.push(temp.lchild);
            }
            S.pop();                        //将栈顶的空元素弹出
            while( !S.isEmpty() ) {
                T = (BiTreeNode) S.peek();
                if(T.rchild == null || T.rchild == p) {  // 没有右孩子 或 已经访问过
                    System.out.print(T.data);
                    S.pop();                    //弹出
                    p = T;                      //记录刚才访问过的
                    flag = true;            //没有新元素,继续访问
                } else {
                    S.push(T.rchlid);
                    flag = false;           //新右子树添加
                }
                if(!flag) {
                    break;              //如果有右子树,需要重新开始
                }
            }
        }
    }
}

文章来源: blog.csdn.net,作者:陶然同学,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/weixin_45481821/article/details/126794643

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。