精华内容
下载资源
问答
  • 首先,先序遍历的顺序是根据 根-左孩子-右孩子 的顺序遍历的,那么我们可以率先确认的是先序遍历序列的第一个数就是根节点,然后中序遍历是根据 左孩子-根-右孩子 的顺序遍历的。我们通过先序遍历确认了根节点,那么...
  • 以前大学学数据结果的时候,我们就知道,根据一棵树的先序遍历和中序遍历,或者后序遍历和中序遍历序列,都可以唯一地确定一棵树。
  • 以下是对先序遍历二叉树的递归实现与非递归实现进行了详细的分析介绍,需要的朋友可以过来参考下
  • C++先序遍历的顺序建立二叉链表,
  • 数据结构C++二叉链表的先序遍历、中序遍历和后序遍历实现
  • int NInorderTraverse(BiTree &Tint*visit(char e) { InitStack(S; Push(S,T;//根指针入栈 while!StackEmpty(S)//在树不空的情况下 { while(GetTop(S,p&p) Push(S,p->lchild;//向左走到头 Pop(S,p;...
  • 在前面一文,说过二叉树的递归遍历算法(二叉树先根(先序遍历的改进),此文主要讲二叉树的非递归算法,采用栈结构 总结先根遍历得到的非递归算法思想如下: 1)入栈,主要是先头结点入栈,然后visit此结点 2)...
  • 主要介绍了python先序遍历二叉树问题,简单分析了问题,然后向大家分享了代码示例,具有一定参考价值,需要的朋友可以了解下。
  • 主要介绍了C#非递归先序遍历二叉树的实现方法,具有一定参考借鉴价值,需要的朋友可以参考下
  • 数据结构二叉树链式结构的前序遍历,中序遍历,后序遍历用递归的方法,层级遍历采用队列结构
  • 用户以先序遍历的方式键入二叉树各结点的数据域值(字符型),程序建立二叉树,然后分别用递归和非递归算法对二叉树进行遍历。每访问一个结点即打印该结点的数据域值。
  • 已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及先序遍历结果,要求输出其后序遍历结果...
  • 既然DOM树是一个树结构,那么我们就可以使用遍历树结构的相关方法来对DOM树进行遍历,同时DOM2中的”Traversal”模块又提供了两种新的类型,从而可以很方便地实现DOM树的先序遍历。 注:本文中的5种方法都是对DOM的...
  • 二叉树的先序遍历

    2012-11-07 14:51:38
    c语言中关于二叉树的先序遍历,链表的创建
  • 输入为:二叉树的先序遍历结果(用&代表空指针的遍历结果) 例如:①输入a&&则返回的指针指向的二叉树应该就是仅有一个节点,值为a. ②输入12&&3&&则返回的指针指向的二叉树应该就是,根节点(1),左子树只有一...
  • 给出先序遍历和中序遍历,求后续遍历,要求: 函数头如下: bool getPostOrder(const char* perOrder, const char* inOrder, char* postOrder); 返回值是一个布尔 代表是否有这样的二叉树 用法: char* perorder ...
  • 二、深入理解 BFS 1.1 什么是 BFS 1.2 二叉树的层次遍历的原理 2.3 BFS (二叉树层次遍历代码实现) 三、深入理解 DFS 3.1 什么是 DFS 3.2 二叉树的 三种遍历方式以及代码实现 3.2.1 先序遍历 递归实现先序遍历 非...

    一、二叉树的性质

    本期的 DFS 与 BFS 搜索算法,我将围绕二叉树来讲解,所以在了解什么是 BFS 与 DFS 之前,我们先来回顾一下二叉树 的基本概念

    1.1 二叉树的特性

    学过 数据结构与算法 的同学在接触二叉树的时候,一定遇到过 二叉树的遍历问题,因为二叉树的 本质 就是一个链表,我们可以看看一个二叉树的样子(PS:二叉树还可以使用数组来存储,当然仅限 完全二叉树

    在这里插入图片描述
    通过上图,我们可以看出二叉树有如下特点:

    1. 它有且只有一个根节点,则是权值为 1 的节点
    2. 每个父节点有两个儿子节点,也可以只有一个节点
    3. 每个节点的儿子数量都是两个,这样的二叉树叫做 完全二叉树
    4. 每个节点的孩子可以分为 左孩子右孩子

    1.2 二叉树的遍历方式

    在这里我们已二叉树为例,我们知道二叉树的遍历方式有如下四种,如果不理解前三种遍历,后面在 DFS 中,我会深入的讲解

    1. 先序遍历(先遍历根节点,然后左节点,右节点)
      遍历结果 1 2 3 4 5 6 7
    2. 中序遍历(先遍历左节点,然后根节点,然后右节点)
      遍历结果 3 2 4 1 6 5 7
    3. 后续遍历(先遍历左右节点,然后遍历根节点)
      遍历结果 3 4 2 6 7 5 1
    4. 层次遍历(每层从左到右遍历节点)
      遍历结果为:1 2 5 3 4 6 7

    但是从 宏观 角度来看,二叉树的遍历方式分为如下两种

    1. 深度优先遍历(DFS)
    2. 广度优先比例(BFS)

    1.3 二叉树是如何存储的呢?

    二叉树的存储方式也可以分为 线性存储链式存储,这里我们以 链式存储 为例。

    从上面的图中我们可以分析出,二叉树每个节点至少是有一个数据域,然后还有两个子节点,所以可以构建出如下数据结构

    在这里插入图片描述
    数据结构用代码实现如下

    public class TreeNode {
    	int val;
    	TreeNode left,right;
    	public TreeNode(int x) {
            val = x;
            left = null;
            right = null;
        }
    }
    

    二、深入理解 BFS

    1.1 什么是 BFS

    BFS(Breadth First Search) 即广度优先搜索,在数和图中非常常见的一种搜索算法。所谓层次遍历,就是从一个点,向其周围所有的点进行搜索,类似走迷宫,我们在一个点可以进行上下左右的进行选择走。在上面的二叉树中,BFS 是实质就是层次遍历

    1.2 二叉树的层次遍历的原理

    二叉树按照从根节点到叶子节点的层次关系,一层向一层横向遍历各个节点。但是二叉树中横向的节点是没有关系的。因此需要借助一个数据结构来辅助工作,这个数据结构是 队列

    在这里插入图片描述
    我们需要借助队列来完成层次遍历的工作,因此

    1. 节点 A 入队,得到子节点 B,D ,[A]
    2. A 出队,第一个节点是 A ,B、D 入队,得到 [D、B] —— A
    3. B 出队,其子节点 C 入队 [C、D] —— A、B
    4. D 出队,其子节点 E、F 入队 [C、E、F] —— A、B、D
    5. C、E、F 都没有子节点,于是都出队得到 —— A、B、D、C、E、F

    2.3 BFS (二叉树层次遍历代码实现)

        public static void cenciTraverseWithQueue(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>(); // 创建队列
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll(); // 元素出队即打印
                System.out.println(node.val); // 打印出队的元素
                if (root.leftNode != null) {
                    queue.offer(node.leftNode);
                }
                if (root.rightNode != null) {
                    queue.offer(node.rightNode);
                }
            }
        }
    

    三、深入理解 DFS

    3.1 什么是 DFS

    DFS 即深度优先搜索,同 BFS,在树和图中也是非常常见的。深度优先,就是从一个端点一直查找到另一个端点,“一头深入到底”,在上面的二叉树的遍历中。先序遍历,中序遍历,后序遍历。

    3.2 二叉树的 三种遍历方式以及代码实现

    给定如下二叉树
    在这里插入图片描述

    3.2.1 先序遍历

    递归实现先序遍历

    二叉树的先序遍历

    1. 优先访问根节点
    2. 然后访问左孩子节点
    3. 然后访问右孩子节点。
    4. 如果访问的节点既没有左孩子,也没有右孩子,这就说明了到头了,那么就会回到它的父节点,再判断父节点是否有右孩子,依次类推

    按照定义:

    1. 我们先遍历根节点,即 A
    2. 然后判断 A 节点是否有左孩子,即 A B
    3. 然而 B节点有孩子节点,所以 B 就作为当前的 根节点, C就作为其左孩子节点,得到 A B C
    4. 遍历到 C节点发现到头了,越是往回走,到 B节点,但是发现 B节点也没有 右节点,然后会根节点,发现有右节点,所以得到 A B C D
    5. 现在 D作为当前根节点,继续往下走 E,即 A B C D E
      10.E 节点也到头了,所以往回到 D 节点,然后找到 F。即得到 A B C D E F

    代码实现:

    使用递归我们可以很快的就实现了先序遍历

    public class TreeNode {
        // 节点的权
        int val;
        // 左儿子
        TreeNode leftNode;
        // 右儿子
        TreeNode rightNode;
        
        // 前序遍历
        public void frontShow() {
            // 遍历当前节点的内容 (中左右)
            System.out.print(val + " ");
    
            // 左节点
            if (leftNode != null) {
                leftNode.frontShow();
            }
    
            // 右节点
            if (rightNode != null)
                rightNode.frontShow();
        }
    }
    
    非递归方式实现先序遍历 (栈)

    走完一遍递归的节点遍历方式,接下来我们走一遍非递归 的先序遍历。但是我们要使用哪种数据结构来实现 BFS 呢?

    答:我们使用递归可以解决的问题,那么就一定有非递归的方法解决问题,在上述的 “遍历过程中” ,有一个重要的点就是,当我们的一个节点访问到头了(这个节点没有子节点),就需要回溯 到上一个节点,然后完成剩下的遍历任务。能够完成回溯任务的是 。因此得到一个结论,栈 和 递归都具有回溯的特征。

    我们使用栈的后进先出,先进后出的特性

    1. 先进入的元素,就可以保存遍历的路径
    2. 元素出栈,就实现了回溯到上一个节点
    3. 栈保存的就是当前遍历过的所有节点
        // 先序遍历的非递归实现
        public static void preOrderTraverseWithStack(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode treeNode = root;
            while (treeNode!=null || !stack.isEmpty()) {
                // 迭代访问节点左孩子,并入栈
                while (treeNode != null) {
                    System.out.print(treeNode.val);
                    stack.push(treeNode); // 节点入栈
                    treeNode = treeNode.leftNode;
                }
                // 如果没有左孩子,则弹出栈顶节点
                if (!stack.isEmpty()) {
                    treeNode = stack.pop();
                    treeNode = treeNode.rightNode;
                }
            }
        }
    

    3.2.2 中序遍历

    原理是一样的,所以就不解释了

    递归实现中序遍历
        // 中序遍历 (左根右)
        public void midShow() {
            // 左节点
            if (leftNode != null) {
                leftNode.midShow();
            }
    
            // 遍历当前节点的内容 (中左右)
            System.out.print(val + " ");
    
            // 右节点
            if (rightNode != null)
                rightNode.midShow();
        }
    
    非递归实现中序遍历
        public static void midOrderTraverseWithStack(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode treeNode = root;
            while (treeNode!=null || !stack.isEmpty()) {
                // 迭代访问节点左孩子,并入栈
                while (treeNode != null) {
                    stack.push(treeNode); // 节点入栈
                    treeNode = treeNode.leftNode;
                }
                // 如果没有左孩子,则弹出栈顶节点
                if (!stack.isEmpty()) {
                    treeNode = stack.pop();
                    System.out.print(treeNode.val); // 中序遍历
                    treeNode = treeNode.rightNode;
                }
            }
        }
    

    3.2.3 后序遍历

    递归实现后续遍历
        public void afterShow() {
            // 左节点
            if (leftNode != null) {
                leftNode.afterShow();
            }
    
            // 右节点
            if (rightNode != null)
                rightNode.afterShow();
    
            // 遍历当前节点的内容 (中左右)
            System.out.print(val + " ");
        }
    
    非递归实现后序遍历

    参考文章
    使用辅助栈实现

        // 后续遍历,左节点,右节点,根节点
        public static void backOrderTraverseWithStack(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> markStack = new Stack<>(); // 使用辅助栈
            TreeNode treeNode = root;
            while (treeNode!=null || !stack.isEmpty()) {
    
                while (treeNode != null ) {
                    stack.push(treeNode);
                    treeNode = treeNode.leftNode;
                }
    
                while (!markStack.isEmpty() && markStack.peek() == stack.peek()) {
                    markStack.pop();
                    System.out.println(stack.pop().val); // stack 此时出栈的值即为后序遍历的结果
                }
    
                if (!stack.isEmpty()) {
                    treeNode = stack.peek();
                    markStack.push(treeNode);
                    treeNode=treeNode.rightNode;
                }
            }
        }
    
    展开全文
  • 二叉树的遍历方式主要有:先序遍历、中序遍历、后序遍历、层次遍历。先序、中序、后序其实指的是父节点被访问的次序。若在遍历过程中,父节点先于它的子节点被访问,就是先序遍历;父节点被访问的次序位于左右孩子...

    概述

    二叉树的遍历是一个很常见的问题。二叉树的遍历方式主要有:先序遍历、中序遍历、后序遍历、层次遍历。先序、中序、后序其实指的是父节点被访问的次序。若在遍历过程中,父节点先于它的子节点被访问,就是先序遍历;父节点被访问的次序位于左右孩子节点之间,就是中序遍历;访问完左右孩子节点之后再访问父节点,就是后序遍历。不论是先序遍历、中序遍历还是后序遍历,左右孩子节点的相对访问次序是不变的,总是先访问左孩子节点,再访问右孩子节点。而层次遍历,就是按照从上到下、从左向右的顺序访问二叉树的每个节点。

    在介绍遍历算法之前,先定义一个二叉树的结构体。使用的是 C++ 语言。

    //filename: BinTreeNode.h
    template <typename T> struct BinTreeNode {
        T data; //数据域
        BinTreeNode * LeftChild; //左孩子节点指针
        BinTreeNode * RightChild; //右孩子节点指针
        BinTreeNode * parent; //父节点指针
    };
    

    先序遍历

    递归

    使用递归,很容易写出一个遍历算法。代码如下:

    //filename: BinTreeNode.h
    template <typename T>
    void travPre_R(BinTreeNode<T> * root) {//二叉树先序遍历算法(递归版)
        if (!root) return;
        cout << root->data;
        travPre_R(root->LeftChild);
        travPre_R(root->RightChild);
    }
    

    迭代

    在之前的文章中,我不止一次地说过,递归是很耗费计算机资源的,所以我们在写程序的时候要尽量避免使用递归。幸运的是,绝大部分递归的代码都有相应的迭代版本。那么我们就试着将上述递归代码改写成迭代的版本。改写之后,代码如下:

    //filename: BinTreeNode.h
    template <typename T>
    void travPre_I1(BinTreeNode<T> * root) {//二叉树先序遍历算法(迭代版#1)
        Stack<BinTreeNode<T>*> s; //辅助栈
        if (root) //如果根节点不为空
            s.push(root); //则令根节点入栈
        while (!s.empty()) { //在栈变空之前反复循环
            root = s.pop(); cout << root->data; //弹出并访问当前节点
    
            //下面左右孩子的顺序不能颠倒,必须先让右孩子先入栈,再让左孩子入栈。
            if (root->RightChild)
                s.push(root->RightChild); //右孩子先入后出
            if (root->LeftChild)
                s.push(root->LeftChild); //左孩子后入先出
        }
    }
    

    下面我们通过一个实例来了解一下该迭代版本是如何工作的。

    PS:黑色的元素表示已经被弹出并访问过。

    结合代码,该二叉树的先序遍历过程如下:

    1. 初始化一个空栈。
    2. 根节点入栈,此时将 a 入栈。
    3. 循环开始,弹出并访问栈顶元素,此时栈顶元素是 a。
    4. 如果 a 有右孩子,则将其右孩子节点入栈;如果 a 有左孩子,则将其左孩子节点入栈。此时栈中有 b、c 两个元素。
    5. 这时进入下一轮循环。弹出并访问栈顶元素,此时栈顶元素是 b。经检查,b 没有右孩子,也没有左孩子,进入下一轮循环。
    6. 弹出并访问栈顶元素,此时栈顶元素是 c。c 的右孩子是 f,左孩子是 d,故分别将 d、f 入栈。进入下一轮循环。
    7. 此时栈中的元素是 d、f。
    8. 弹出并访问栈顶元素,此时栈顶元素是 d。d 的右孩子是 e,d 没有左孩子,故将 e 入栈。进入下一轮循环。
    9. 此时栈中的元素是 e、f。
    10. 弹出并访问栈顶元素,此时栈顶元素是 e。e 没有左右孩子,进入下一轮循环。
    11. 弹出并访问栈顶元素,此时栈顶元素是 f。f 没有左右孩子,进入下一轮循环。
    12. 此时栈为空,退出循环。遍历结束。

    这个迭代的遍历算法非常简明,但是很遗憾,这种算法并不容易推广到我们接下来要研究的中序遍历和后序遍历。因此我问需要寻找另一种策略。

    第 2 种迭代方式

    我们来看一个规模更大、更具一般性的二叉树:

    这个二叉树的先序遍历序列是:idcabhfeglkjnmpo,也就是遵循了下图所示的顺序:

    再进一步,我们把二叉树抽象成下面这个样子,


    L_0 ~ L_d 是二叉树的左侧链上的节点, R_0 ~ R_d 分别是 L_0 ~ L_d 的右孩子,T_0 ~ T_d 分别是 L_0 ~ L_d 的右子树。不难发现,二叉树的先序遍历就是先自上而下访问左侧链上的节点,再自下而上访问左侧链上的节点的右子树。而我们的遍历算法,就是根据这样一个思路来进行设计。

    首先需要实现一个子方法,就是访问二叉树左侧链上的节点:

    //从当前节点出发,沿左分支不断深入,直至没有左分支的节点;沿途节点遇到后立即访问
    template <typename T> //元素类型、操作器
    static void visitAlongLeftBranch ( BinTreeNode<T>* x, Stack<BinTreeNode<T>*>& S ) {
       while ( x ) {
          cout << x->data; //访问当前节点
          if( x->RightChild )
               S.push ( x->RightChild ); //右孩子入栈暂存(可优化:通过判断,避免空的右孩子入栈)
          x = x->LeftChild;  //沿左分支深入一层
       }
    }
    

    然后是主方法,在主方法中,通过迭代,不断地调用上面这个子方法,从而实现完整的二叉树先序遍历。

    template <typename T> //元素类型、操作器
    void travPre_I2 ( BinTreeNode<T>* root) { //二叉树先序遍历算法(迭代版#2)
       Stack<BinTreeNode<T>*> S; //辅助栈
       while ( true ) {
          visitAlongLeftBranch ( root, S ); //从当前节点出发,逐批访问
          if ( S.empty() ) break; //直到栈空
          root = S.pop(); //弹出下一批的起点
       }
    }
    

    中序遍历

    递归

    与先序遍历类似,递归版的中序遍历算法很容易实现,代码如下:

    template <typename T>
    void travIn_R(BinTreeNode<T> * root) {//二叉树先序遍历算法(递归版)
        if (!root)
            return;
        travPre_R(root->LeftChild);
        cout << root->data;
        travPre_R(root->RightChild);
    }
    

    递归代码不仅容易实现,也很好理解,这里不再做过多解释。

    迭代

    参照迭代式先序遍历版本 2 的思路,在宏观上,我们可以将中序遍历的顺序抽象为,先访问二叉树的左侧链上的最底部的节点,然后访问该节点的右子树(如果有的话),然后访问该节点的父节点,然后访问该节点的父节点的右子树(如果有的话)……直至全部节点被访问完毕。如下图所示:

    按照以上思路,可以实现迭代版中序遍历算法如下:

    template <typename T> //从当前节点出发,沿左分支不断深入,直至没有左分支的节点
    static void goAlongLeftBranch ( BinTreeNode<T> * x, Stack<BinTreeNode<T> * >& S ) {
        while (x) { S.push(x); x = x->LeftChild; } //当前节点入栈后随即向左侧分支深入,迭代直到无左孩子
    }
    

    template <typename T> //元素类型、操作器
    void travIn_I(BinTreeNode<T> root) {//二叉树先序遍历算法(迭代版)
    Stack<BinTreeNode<T> > S; //辅助栈
    while ( true ) {
    goAlongLeftBranch ( root, S ); //从当前节点出发,逐批入栈
    if ( S.empty() ) break; //直至所有节点处理完毕
    root = S.pop();
    cout << root->data; //弹出栈顶节点并访问之
    root = root->RightChild; //转向右子树
    }
    }

    也可以对代码稍加改进,将这两个方法写成一个方法:

    template <typename T> //元素类型
    void travIn_I2 ( BinTreeNode<T> root ) { //二叉树中序遍历算法(迭代版#2)
    Stack<BinTreeNode<T>> S; //辅助栈
    while ( true )
    if ( root ) {
    S.push ( root ); //根节点进栈
    root = root->LeftChild; //深入遍历左子树
    } else if ( !S.empty() ) {
    root = S.pop(); //尚未访问的最低祖先节点退栈
    cout << root->data; //访问该祖先节点
    root = root->RightChild; //遍历祖先的右子树
    } else
    break; //遍历完成
    }

    后序遍历

    递归

    与前两个一样,二叉树的后序遍历算法可以很容易地用递归的方式实现。

    template <typename T>
    void travPost_R(BinTreeNode<T> root) {//二叉树先序遍历算法(递归版)
    if (!root)
    return;
    travPost_R(root->LeftChild);
    travPost_R(root->RightChild);
    cout << root->data;
    }

    迭代

    但是要想用迭代的方式实现后序遍历算法,则有一定的难度,因为左、右子树的递归遍历均严格地不属于尾递归。不过,仍可继续套用此前的思路和技巧,考虑一下,后序遍历中,首先访问的是哪个节点?答案就是二叉树的最高最左侧的叶子节点。

    由于最高最左侧的叶子节点 V 可能是左孩子节点,也可能是右孩子节点,所以 V 与其父节点之间的联接用竖直的线表示。考查联接于 V 与树根之间的唯一通路(以粗线示意)。与先序与中序遍历类似地,自底而上地沿着该通路,整个后序遍历序列也可以分解为若干个片段。每一片段,分别起始于通路上的一个节点,并包括三步:访问当前节点,遍历以其右兄弟(若存在)为根的子树,以及向上回溯至其父亲节点(若存在)并转入下一片段。

    基于以上理解,即可写出迭代式后序遍历算法。

    template <typename T> //在以S栈顶节点为根的子树中,找到最高左侧叶节点
    static void gotoHLVFL ( Stack<BinTreeNode<T>>& S ) { //沿途所遇节点依次入栈
    while ( BinTreeNode<T>* x = S.top() ) //自顶而下,反复检查当前节点(即栈顶)
    if ( x->LeftChild ) { //尽可能向左
    if ( x->RightChild ) S.push ( x->RightChild ); //若有右孩子,优先入栈
    S.push ( x->LeftChild ); //然后才转至左孩子
    } else //实不得已
    S.push ( x->RightChild ); //才向右
    S.pop(); //返回之前,弹出栈顶的空节点
    }

    template <typename T>
    void travPost_I ( BinTreeNode<T> root ) { //二叉树的后序遍历(迭代版)
    Stack<BinTreeNode<T>> S; //辅助栈
    if ( root ) S.push ( root ); //根节点入栈
    while ( !S.empty() ) {
    if ( S.top() != root->parent ) //若栈顶非当前节点之父(则必为其右兄),此时需
    gotoHLVFL ( S ); //在以其右兄为根之子树中,找到HLVFL(相当于递归深入其中)
    root = S.pop(); cout << root->data; //弹出栈顶(即前一节点之后继),并访问之
    }
    }

    层次遍历

    在文章开头我们已经对层次遍历做了介绍,层次遍历严格按照自上而下、自左向右的顺序访问树的节点。所以我们需要用队列作为辅助,具体代码如下:

    template <typename T> //元素类型
    void travLevel ( BinTreeNode<T> root ) { //二叉树层次遍历算法
    Queue<BinTreeNode<T>> Q; //辅助队列
    Q.enqueue ( root ); //根节点入队
    while ( !Q.empty() ) { //在队列再次变空之前,反复迭代
    BinTreeNode<T>* x = Q.dequeue(); cout << x->data; //取出队首节点并访问之
    if ( x->LeftChild ) Q.enqueue ( x->LeftChild ); //左孩子入队
    if ( x->RightChild ) Q.enqueue ( x->RightChild ); //右孩子入队
    }
    }

    好了,以上就是二叉树的几种常见的遍历方式。

    展开全文
  • 文章目录先序遍历中序遍历后序遍历层序遍历遍历应用例子 先序遍历 遍历过程为: ① 访问根结点;② 先序遍历其左子树; ③ 先序遍历其右子树。 void PreOrderTraversal( BinTree BT ) { if( BT ) { printf(“%d”,...

    (笔记总结自浙江大学数据结构)

    先序遍历

    遍历过程为:
    ① 访问根结点;② 先序遍历其左子树; ③ 先序遍历其右子树。

    void PreOrderTraversal( BinTree BT ) {
     if( BT ) {
     printf(%d”, BT->Data);
     PreOrderTraversal( BT->Left );
     PreOrderTraversal( BT->Right );  
     } }
    

    在这里插入图片描述
    A(B D F E )(C G H I)
    先序遍历=> A B D F E C G H I

    中序遍历

    遍历过程为:
    ① 中序遍历其左子树; ② 访问根结点; ③ 中序遍历其右子树。

    void InOrderTraversal( BinTree BT ) {
     if( BT ) {
     InOrderTraversal( BT->Left );
     printf(%d”, BT->Data);
     InOrderTraversal( BT->Right );
     } }
    

    在这里插入图片描述

    (D B E F) A (G H C I)
    中序遍历=> D B E F A G H C I

    举例:中序遍历非递归遍历算法
    遇到一个结点,就把它压栈,并去遍历它的左子树;
    当左子树遍历结束后,从栈顶弹出这个结点并访问它;
    然后按其右指针再去中序遍历该结点的右子树。

    void InOrderTraversal( BinTree BT ) { BinTree T=BT;
    Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/
    while( T || !IsEmpty(S) ){
     while(T){ /*一直向左并将沿途结点压入堆栈*/
     Push(S,T);
     T = T->Left;
     }
     if(!IsEmpty(S)){
     T = Pop(S); /*结点弹出堆栈*/
     printf(%5d”, T->Data); /*(访问)打印结点*/
     T = T->Right; /*转向右子树*/
     } } }
    

    后序遍历

    遍历过程为:
    ① 后序遍历其左子树; ② 后序遍历其右子树; ③ 访问根结点。

    void PostOrderTraversal( BinTree BT ) {
     if( BT ) {
     PostOrderTraversal( BT->Left );
     PostOrderTraversal( BT->Right);
     printf(%d”, BT->Data);
     } }
    

    在这里插入图片描述
    (D E F B )( H G I C) A
    后序遍历=> D E F B H G I C A

    先序、中序和后序遍历过程:遍历过程中经过结点的路线一样,只是访问各结点的时机不同。
    图中在从入口到出口的曲线上用×、★ 和△三种符号分别标记出了先序、中序和后序访问各结点的时刻。
    在这里插入图片描述
    前中后源代码汇总:

    void InorderTraversal( BinTree BT )
    {
        if( BT ) {
            InorderTraversal( BT->Left );
            /* 此处假设对BT结点的访问就是打印数据 */
            printf("%d ", BT->Data); /* 假设数据为整型 */
            InorderTraversal( BT->Right );
        }
    }
     
    void PreorderTraversal( BinTree BT )
    {
        if( BT ) {
            printf("%d ", BT->Data );
            PreorderTraversal( BT->Left );
            PreorderTraversal( BT->Right );
        }
    }
     
    void PostorderTraversal( BinTree BT )
    {
        if( BT ) {
            PostorderTraversal( BT->Left );
            PostorderTraversal( BT->Right );
            printf("%d ", BT->Data);
        }
    }
     
    void LevelorderTraversal ( BinTree BT )
    { 
        Queue Q; 
        BinTree T;
     
        if ( !BT ) return; /* 若是空树则直接返回 */
         
        Q = CreatQueue(); /* 创建空队列Q */
        AddQ( Q, BT );
        while ( !IsEmpty(Q) ) {
            T = DeleteQ( Q );
            printf("%d ", T->Data); /* 访问取出队列的结点 */
            if ( T->Left )   AddQ( Q, T->Left );
            if ( T->Right )  AddQ( Q, T->Right );
        }
    }
    

    层序遍历

    二叉树遍历的核心问题:二维结构的线性化
    队列实现:遍历从根结点开始,首先将根结点入队,然后开始执行循环:结点出队、访问该结点、其左右儿子入队
    在这里插入图片描述
    在这里插入图片描述
    层序遍历 =>A B C D F G I E H

    层序基本过程:先根结点入队,然后:
    1.从队列中取出一个元素;
    2.访问该元素所指结点;
    3.若该元素所指结点的左、右孩子结点非空,则将其左、右孩子的指针顺序入队。

    void LevelOrderTraversal ( BinTree BT ) { Queue Q; BinTree T;
    if ( !BT ) return; /* 若是空树则直接返回 */ 
    Q = CreatQueue( MaxSize ); /*创建并初始化队列Q*/
    AddQ( Q, BT );
    while ( !IsEmptyQ( Q ) ) {
     T = DeleteQ( Q );
    printf(%d\n”, T->Data); /*访问取出队列的结点*/
    if ( T->Left ) AddQ( Q, T->Left );
    if ( T->Right ) AddQ( Q, T->Right ); } }
    

    遍历应用例子

    【例】遍历二叉树的应用:输出二叉树中的叶子结点。
    在二叉树的遍历算法中增加检测结点的“左右子树是否都为空”。

    void PreOrderPrintLeaves( BinTree BT ) {
     if( BT ) {
     if ( !BT-Left && !BT->Right )
     printf(%d”, BT->Data );
     PreOrderPrintLeaves ( BT->Left );
     PreOrderPrintLeaves ( BT->Right );
     } }
    

    【例】求二叉树的高度。
    在这里插入图片描述Height=max(HL, HR)+1

    int PostOrderGetHeight( BinTree BT ) { int HL, HR, MaxH;
     if( BT ) {
     HL = PostOrderGetHeight(BT->Left); /*求左子树的深度*/
     HR = PostOrderGetHeight(BT->Right); /*求右子树的深度*/
     MaxH = (HL > HR)? HL : HR; /*取左右子树较大的深度*/
     return ( MaxH + 1 ); /*返回树的深度*/
     }
     else return 0; /* 空树深度为0 */
    }
    

    【例】 二元运算表达式树及其遍历
    在这里插入图片描述

    三种遍历可以得到三种不同的访问结果:
    先序遍历得到前缀表达式:+ + a * b c * + * d e f g
    中序遍历得到中缀表达式:a + b * c + d * e + f * g(中缀表达式会受到运算符优先级的影响)
    后序遍历得到后缀表达式:a b c * + d e * f + g * +

    【例】 由两种遍历序列确定二叉树
    (必须要有中序遍历)

    先序和中序遍历序列来确定一棵二叉树:
    1 根据先序遍历序列第一个结点确定根结点;
    2 根据根结点在中序遍历序列中分割出左右两个子序列;
    3 对左子树和右子树分别递归使用相同的方法继续分解。
    在这里插入图片描述
    类似地,后序和中序遍历序列也可以确定一棵二叉树。

    问:假定只有四个结点A、B、C、D的二叉树,其前序遍历序列为ABCD,则下面哪个序列是不可能的中序遍历序列?(D)
    A.ABCD
    B.ACDB
    C.DCBA
    D.DABC
    (D选项,首先根据中序,A在中间,所以左子树的节点只有一个D,而右子树节点是B和C,但根据前序遍历的规则,打印出A以后应该接着打印B,但若D在左子树,B在右子树,则前序遍历不可能先打印出B再打印出D。)

    展开全文
  • DLR--先序遍历(根在前,从左往右,一棵树的根永远在左子树前面,左子树又永远在右子树前面 ) 根-左-右(从上往下一层一层看) LDR--中序遍历(根在中,从左往右,一棵树的左子树永远在根前面,根永远在右子...

    DLR--先序遍历(根在前,从左往右,一棵树的根永远在左子树前面,左子树又永远在右子树前面 )

    根-左-右(从上往下一层一层看)

    在这里插入图片描述

     

    LDR--中序遍历(根在中,从左往右,一棵树的左子树永远在根前面,根永远在右子树前面)

    左-根-右(从下往上,一层一层)

     

    LRD--后序遍历(根在后,从左往右,一棵树的左子树永远在右子树前面,右子树永远在根前面)

    左-右-根(从下往上,一层一层)

     

    展开全文
  • 二叉链表的先序遍历

    2021-06-21 00:14:40
    二叉树的先序遍历(C语言) 以完全二叉树为例,其中的先序遍历函数也可以运用到别的树。 //先序遍历的非递归算法(函数) int PreOrder(BiTree T) { BiTree p, stack[MAXSIZE]; int top=0; p=T; if(T=NULL) { ...
  • 先序遍历中序遍历还原二叉树

    千次阅读 2019-07-22 23:00:59
    先序遍历二叉树结果的第一个节点是根节点 中序遍历二叉树结果中左子树右子树又以根节点隔开 假定: 先序遍历结果为: A B D F G H I E C 中序遍历结果为: F D H G I B E A C 第一次考虑 毫无疑问通过先序遍历可以...
  • 假设现在有某二叉树的先序遍历和中序遍历,我们应该如何建树? 基本思路: 分别求得根节点的左子树和右子树的先序遍历序列与中序遍历序列 分别以左子树和右子树为新树进行第一步操作 直至没有子树为止 那么我们...
  • 先序建立二叉树、非递归实现先序遍历和中序遍历、队列实现层次遍历 先序建立二叉树,#表示空结点。 使用栈,实现非递归先序遍历和中序遍历。 使用队列实现层次遍历。 直接上代码,寒假完善注释,甚至从头到尾把...
  • 先序遍历(非递归)

    2021-03-25 16:48:50
    试写出先序遍历(非递归算法) 分析: 和中序遍历大同小异,唯一的差别在于每次先访问节点,在判断有没有左孩子,有则入栈,然后出栈,往右走。直至栈空 代码如下: struct biTree {//树的结构体 char data; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 60,981
精华内容 24,392
关键字:

先序遍历