二叉树遍历 订阅
所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一,是二叉树上进行其它运算之基础。 展开全文
所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一,是二叉树上进行其它运算之基础。
信息
外文名
Binary Tree Traversal
一棵非空的二
由根结点及左、右子树这三个基本
叉    树
部分组成
中文名
二叉树遍历
在任一给定结
可以按某种次序执行三个操作
二叉树遍历算法实现
从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:⑴访问结点本身(N),⑵遍历该结点的左子树(L),⑶遍历该结点的右子树(R)。以上三种操作有六种执行次序:NLR、LNR、LRN、NRL、RNL、RLN。注意:前三种次序与后三种次序对称,故只讨论先左后右的前三种次序。根据访问结点操作发生位置命名:① NLR:前序遍历(Preorder Traversal 亦称(先序遍历))——访问根结点的操作发生在遍历其左右子树之前。② LNR:中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。③ LRN:后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。注意:由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。1.先(根)序遍历的递归算法定义:若二叉树非空,则依次执行如下操作:⑴ 访问根结点;⑵ 遍历左子树;⑶ 遍历右子树。2.中(根)序遍历的递归算法定义:若二叉树非空,则依次执行如下操作:⑴遍历左子树;⑵访问根结点;⑶遍历右子树。3.后(根)序遍历得递归算法定义:若二叉树非空,则依次执行如下操作:⑴遍历左子树;⑵遍历右子树;⑶访问根结点。用二叉链表做为存储结构,中序遍历算法可描述为:void InOrder(BinTree T){ //算法里①~⑥是为了说明执行过程加入的标号① if(T) { // 如果二叉树非空② InOrder(T->lchild);③ printf("%c",T->data); // 访问结点④ InOrder(T->rchild);⑤ }⑥ } // InOrder计算中序遍历拥有比较简单直观的投影法,如图 除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。
收起全文
精华内容
下载资源
问答
  • 2021-07-28 14:28:25

    一  概念

    1 二叉树的3个基本组成单元:根节点、左子树和右子树。

    2 先序遍历

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

    1. 访问根节点;
    2. 先序遍历左子树;
    3. 先序遍历右子树;

    3 中序遍历:

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

    1. 中序遍历左子树;
    2. 访问根节点;
    3. 中序遍历右子树;

    4 后序遍历:

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

    1. 后序遍历左子树;
    2. 后序遍历右子树;
    3. 访问根节点;

    二 代码

    1 声明根节点

    public class TreeNode {
    	public int data;
        public TreeNode leftChild;
        public TreeNode rightChild;
    
        public TreeNode(int data){
            this.data = data;
        }
    }

    2 创建二叉树

    public static TreeNode createBinaryTree(LinkedList<Integer> list){
            TreeNode node = null;
            if(list == null || list.isEmpty()){
                return null;
            }
            Integer data = list.removeFirst();
            if(data!=null){
                node = new TreeNode(data);
                node.leftChild = createBinaryTree(list);
                node.rightChild = createBinaryTree(list);
            }
            return node;
        }

    3  二叉树先序遍历

    public static void preOrderTraveral(TreeNode node){
            if(node == null){
                return;
            }
            System.out.print(node.data+" ");
            preOrderTraveral(node.leftChild);
            preOrderTraveral(node.rightChild);
        }

    4 二叉树中序遍历

        public static void inOrderTraveral(TreeNode node){
            if(node == null){
                return;
            }
            inOrderTraveral(node.leftChild);
            System.out.print(node.data+" ");
            inOrderTraveral(node.rightChild);
        }

    5 二叉树后序遍历

    public static void postOrderTraveral(TreeNode node){
            if(node == null){
                return;
            }
            postOrderTraveral(node.leftChild);
            postOrderTraveral(node.rightChild);
            System.out.print(node.data+" ");
        }

    6 测试

    二叉树:

     

    public static void main(String[] args) {
            
            LinkedList<Integer> inputList1 = new LinkedList<>(Arrays.asList(new Integer[]{1,2, 3, null, null, 4,5, null, 6,null,  null, 7,null,null}));
            
            TreeNode treeNode = createBinaryTree(inputList1);
            System.out.println("前序遍历:");
            preOrderTraveral(treeNode);
            System.out.println("\n"+"中序遍历:");
            inOrderTraveral(treeNode);
            System.out.println("\n"+"后序遍历:");
            postOrderTraveral(treeNode);
    
        }

     7 结果

    前序遍历:
    1 2 3 4 5 6 7 
    中序遍历:
    3 2 5 6 4 7 1 
    后序遍历:
    3 6 5 7 4 2 1 

    ps:借鉴链接:二叉树的前中后序遍历(递归遍历)

    更多相关内容
  • 易语言二叉树遍历

    2020-07-21 17:17:12
    易语言二叉树遍历源码,二叉树遍历,二叉树_取下级树,内存_读整数内存,读整数内存_
  • 二叉树_二叉树遍历_

    2021-10-04 07:03:48
    1.二叉树的基本操作实现【问题描述】建立一棵二叉树,用递归方法实现二叉树的如下基本操作:(1)按先序序列构造一棵二叉链表表示的二叉树T;...ABCDEFG【选做内容】采用非递归算法实现二叉树遍历
  • 实验三 二叉树遍历与路径查找(二叉树实验) 实现功能:建立二叉树存储结构、求二叉树的先序遍历、求二叉树的中序遍历、求二叉树的后序遍历、求二叉树的层次遍历、求根到给定结点的路径。 主控菜单: 1.建立二叉树...
  • 主要内容 二叉树的遍历 二叉树的创建 二叉树遍历的应用 叉树的遍历 叉树的遍历是指按一定次序访问二叉树中的每 个结点,且每个结点仅被访问一次 在二叉树的遍历过程中不要将整棵树看成是由多 个结点组成,而要看成是由...
  • python代码:包括二叉树的构造、二叉树的前序、中序、后序遍历(包括递归和非递归实现)
  • 本文实例讲述了php实现的二叉树遍历算法。分享给大家供大家参考,具体如下: 今天使用php来实现二叉树的遍历 创建的二叉树如下图所示 php代码如下所示: <?php class Node { public $value; public $child_...
  • C/C++实现二叉树遍历与路径查找,包括源代码和实验报告。程序实现了二叉树的建立,修改,先序、中序、后序遍历,可以查看二叉树的层次结构,求根到指定结点的路径。
  • 基于C语言编写的递归与非递归方法的二叉树先中后序遍历
  • 主要介绍了PHP实现的线索二叉树及二叉树遍历方法,结合实例形式较为详细的分析了线索二叉树的定义,创建,判断与遍历等技巧,需要的朋友可以参考下
  • 二叉树遍历实验报告

    2017-01-09 11:35:28
    实现了二叉树的前中后遍历,以及层次遍历,求出了二叉树的深度,叶子个数。 实验报告还包含目录,所有遍历方法的解释,以及结果展示和结论改进
  • 二叉树遍历 二叉树遍历
  • 本文详细讲述了C++实现二叉树遍历序列的求解方法,对于数据结构与算法的学习有着很好的参考借鉴价值。具体分析如下: 一、由遍历序列构造二叉树    如上图所示为一个二叉树,可知它的遍历序列分别为:  先序遍历...
  • 二叉树遍历

    2018-11-04 23:28:49
    1、二叉树遍历是指从根节点出发,按照某种次序依次访问二叉树中的所有结点,使得每个节点被访问依次且仅被访问一次。 2、前序遍历: 规则是若二叉树为空,则空操作返回,否则先访问根节点,然后前序遍历左子树,...
  • 问题一 二叉树遍历 1. 问题描述 设输入该二叉树的前序序列为 ABC#DE#G#F#HI#J#K# #代表空子树 请编程完成下列任务 请根据此输入来建立该二叉树 并输出该二叉树的前序 中序和后序序列 按层次遍历的方法来输出该二叉树...
  • 二叉树遍历,c语言 实现数据结构二叉树遍历
  • 数据结构之二叉树 实 验 报 告 题目:二叉树遍历和子树交换 指导老师:杨政宇 班级通信1202 姓名:徐江 学号0909121127 需求分析 演示程序分别用多种遍历算法遍历二叉树并把数据输出 输入字符序列递归方式建立二叉树 ...
  • 二叉树遍历详解

    千次阅读 2021-01-16 13:29:51
    二叉树遍历方式是最基本,也是最重要的一类题目,我们将从「前序」、「中序」、「后序」、「层序」四种遍历方式出发,总结他们的递归和迭代解法。 一、二叉树定义 二叉树(Binary tree)是树形结构的一个重要...

    二叉树的遍历方式是最基本,也是最重要的一类题目,我们将从「前序」、「中序」、「后序」、「层序」四种遍历方式出发,总结他们的递归和迭代解法。

    一、二叉树定义
          二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树,且有左右之分。简单来说,就是一个包含节点,以及它的左右孩子的一种数据结构

    假设二叉树的节点定义如下

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    
        public TreeNode() {
        }
    
        public TreeNode(int val) {
            this.val = val;
        }
    
        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    二、层序遍历

    层序遍历比较简单,按照从上到下,从左到右的顺序逐次遍历。此处借用队列的先入先出特性来实现,具体代码如下

    public static void levelTraverse(TreeNode root) {
            if (root == null) {
                return;
            }
            Queue<TreeNode> queue = new LinkedList<>();
    
            //初始化时把root放入队列
            queue.offer(root);
    
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
    
                //打印节点的值
                System.out.print(node.val + " ");
    
                //队列是先入先出,所以此处先遍历左节点
                if (node.left != null) {
                    queue.offer(node.left);
                }
    
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }

    三、前序遍历(根节点,左子树,右子树)

    1、递归实现:二叉树遍历的递归形式比较容易实现,直接按照根节点,左子树,右子树的顺序 逐次遍历即可

    private static void preOrderTraversal0(TreeNode root) {
            if (root == null) {
                return;
            }
    
            //打印根节点
            System.out.print(root.val + " ");
    
            //打印左节点
            preOrderTraversal0(root.left);
    
            //打印右节点
            preOrderTraversal0(root.right);
        }

    2、迭代实现

    2.1 迭代解法一

    过程如下:

    • 初始化栈,并将根节点入栈;
    • 当栈不为空时:
      弹出栈顶元素 node,并将值添加到结果中;
      如果 node 的右子树非空,将右子树入栈;
      如果 node 的左子树非空,将左子树入栈;
      由于栈是“先进后出”的顺序,所以入栈时先将右子树入栈,这样使得前序遍历结果为 “根->左->右”的顺序。

    经过上面图的讲解,代码就比较简单,代码如下:

    private static void preOrderTraversal1(TreeNode root) {
            if (null == root) {
                return;
            }
    
            //定义一个栈方便后续遍历
            Stack<TreeNode> stack = new Stack<>();
    
            //初始化
            stack.push(root);
            while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
    
                //每一次出栈都打印节点的值
                System.out.print(node.val + " ");
    
                //栈是先进后出的,所以先处理右子树入栈,再左子树入栈
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
            }
        }

    2.2 迭代解法二

    (1)思路稍有不同,先定义一个节点cur指向root节点,先将cur节点和所有的左孩子入栈同时打印出cur节点的值,直至 cur 为空,用一个 while 循环实现。

    (2)随后出栈一个节点,定义为node,执行 cur = node.right,随后继续执行 操作(1)

    经过上面分析,代码中的(1)和(2)分别对应上述的描述,代码如下:

    private static void preOrderTraversal2(TreeNode root) {
            if (root == null) {
                return;
            }
            Stack<TreeNode> stack = new Stack<>();
            //定义一个cur指向root
            TreeNode cur = root;
            while (!stack.isEmpty() || cur != null) {
                //(1)只要cur!=null,则打印值,同时cur入栈,同时设置cur = cur.left
                while (cur != null) {
                    System.out.print(cur.val + " ");
                    stack.push(cur);
                    cur = cur.left;
                }
    
                //(2)如果cur == null,则出栈一个节点,同时设置cur = node.right,同时继续执行(1)
                TreeNode node = stack.pop();
                cur = node.right;
            }
        }

    四、中序遍历(左子树,根节点,右子树)

    1、递归实现:二叉树遍历的递归形式比较容易实现,直接按照(左子树,根节点,右子树)的顺序 逐次遍历即可

    //中序遍历
        private static void inOrderTraversal0(TreeNode root) {
            if (root == null) {
                return;
            }
    
            //打印左节点
            inOrderTraversal0(root.left);
    
            //打印根节点
            System.out.print(root.val + " ");
    
            //打印右节点
            inOrderTraversal0(root.right);
        }

    2、迭代解法:(左子树,根节点,右子树)

    (1)与前序遍历的逻辑差不多,前序遍历是入栈的时候打印值,但是中序遍历是先处理左节点,再处理根节点,最后遍历右节点,所以遍历时不打印值,出栈时打印值,先定义一个节点cur指向root节点,先将cur节点和所有的左孩子入栈 直至 cur 为空,用一个 while 循环实现。

    (2)随后出栈一个节点,定义为node,打印节点的值,执行 cur = node.right,随后继续执行 操作(1)

    经过上面处理后 root 节点的左子树处理完毕,接下来继续处理右子树,也是重复的过程,经过上面分析,代码如下:

    private static void inOrderTraversal1(TreeNode root) {
            if (root == null) {
                return;
            }
            TreeNode cur = root;
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || cur != null) {
                //(1)如果cur不等于空,一直入栈,同时执行cur = cur.left,目的是找到最左节点
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
    
                //(2)如果cur为空,则出栈一个元素,同时打印值,接下来处理右子树,右子树也是调用(1)同步处理
                TreeNode node = stack.pop();
                System.out.print(node.val + " ");
                cur = node.right;
            }
        }

    五、后续遍历(左子树,右子树,根节点)

    1、递归实现:二叉树遍历的递归形式比较容易实现,直接按照(左子树,右子树,根节点)的顺序 逐次遍历即可

    private static void postOrderTraversal0(TreeNode root) {
            if (root == null) {
                return;
            }
    
            //打印左节点
            postOrderTraversal0(root.left);
    
            //打印右节点
            postOrderTraversal0(root.right);
    
            //打印根节点
            System.out.print(root.val + " ");
    
        }

    2、迭代实现:(二叉树的后续遍历,先左子树,右子树,最后根结点),可以定义两个辅助栈,一个栈用于辅助遍历,一个栈用于存放结果,从root开始遍历时先遍历到跟结点,但是根节点又需要最后输出,所以可以借助栈的(先进后出的)特性实现先进入的节点最后输出

    经过上面的图解代码如下:

    public static void postOrderTraversal(TreeNode root) {
            if (root == null) {
                return;
            }
            Stack<TreeNode> stack1 = new Stack<TreeNode>();
    
            //起始时root入栈
            stack1.push(root);
    
            //定义一个result栈
            Stack<TreeNode> result = new Stack<TreeNode>();
            while (!stack1.isEmpty()) {
                TreeNode node = stack1.pop();
                result.push(node);
                //先左节点入栈
                if (node.left != null) {
                    stack1.push(node.left);
                }
                //再右节点入栈
                if (node.right != null) {
                    stack1.push(node.right);
                }
            }
    
            //最后result栈中依次出栈即为结果
            while (!result.isEmpty()) {
                System.out.print(result.pop().val + " ");
            }
        }

    上面仅记录个人的理解。有错误麻烦指正,感谢。

    展开全文
  • Python:二叉树遍历

    2022-04-15 13:25:43
    二叉树遍历

    二叉树遍历共有四种方法,分别是前序遍历、中序遍历、后序遍历和层次遍历。

    前序遍历: 父节点——左孩子——右孩子

    中序遍历:左孩子——父节点——右孩子

    后序遍历:左孩子——右孩子——父节点

    层次遍历:利用队列解决,父节点出队,左右孩子进队

    #二叉树遍历
    #建立二叉树
    from collections import deque
    class Tree():
        def __init__(self,data):
            self.data=data
            self.lchild=None
            self.rchild=None
    
    a=Tree("A")
    b=Tree("B")
    c=Tree("C")
    d=Tree("D")
    e=Tree("E")
    f=Tree("F")
    g=Tree("G")
    
    e.lchild=a
    e.rchild=g
    a.rchild=c
    c.lchild=b
    c.rchild=d
    g.rchild=f
    
    #第一种方法:前序遍历
    def pre_read(root):
        if root:
            print(root.data,end=' ')
            pre_read(root.lchild)
            pre_read(root.rchild)
    print("1.前序遍历")
    pre_read(e)
    ##第二种方法:中序遍历
    def mid_read(root):
        if root:
            mid_read(root.lchild)
            print(root.data,end=' ')
            mid_read(root.rchild)
    print("\n2.中序遍历")
    mid_read(e)
    #第三种方法:后序遍历
    def back_read(root):
        if root:
            back_read(root.lchild)
            back_read(root.rchild)
            print(root.data,end=' ')
    print("\n3.后序遍历")
    back_read(e)
    ##第四种方法:层次遍历
    ##利用队列解决,父节点出队,左右孩子进队】
    def cengci_read(root):
        queue=deque()
        if root:
            queue.append(root)
            while len(queue)>0:
                node=queue.popleft()
                print(node.data,end=' ')
                if node.lchild:
                    queue.append(node.lchild)
                if node.rchild:
                    queue.append(node.rchild)
    print("\n层次遍历")
    cengci_read(e)

    展开全文
  • 二叉树遍历 简介: 本文主要涉及二叉树的先中后序列遍历 文章并未涉及代码,仅仅提供思路 reference: 学堂在线-数据结构 引言: 在学习链表和数组这两种线性的数据结构的时候,元素之间的次序是十分容易看出的,...

    二叉树遍历

    简介:

    本文主要涉及二叉树的先中后序列遍历

    文章并未涉及代码,仅仅提供思路
    reference:
    学堂在线-数据结构

    引言:

    在学习链表和数组这两种线性的数据结构的时候,元素之间的次序是十分容易看出的,毕竟元素的位置就是排着队的,自带次序关系,如果想要遍历整个数据结构,无非就是选择倒着遍历还是正着遍历。

    image-20211001234303668

    但是在学习二叉树这种半线性结构的时候,也想要遍历整棵树,可是树没有数组、链表这么天然的次序关系,所以需要人为的定义次序关系,即先中后序(VLR,LVR,LRV),这一个过程本质上就是将树的半线性结构转换成线性结构,以方便后继通过选择不同的遍历二叉树的方式设计常用的算法框架。

    1. 节点本身记作V
    2. 左孩子记作L
    3. 右孩子记作R

    根据节点V在其中的优先级可得到三种不同访问优先级的遍历方式(左孩子优先级永远高于右孩子)

    1. 先序遍历:右孩子 < 左孩子 < 节点本身
    2. 中序遍历:右孩子 < 节点本身 < 左孩子
    3. 后序遍历:节点本身 < 右孩子 < 左孩子

    其实这里可以看出:

    1. 如果是先序遍历,那么节点本身的优先级最高
    2. 如果是中序遍历,那么节点本身的优先级第二
    3. 如果是后序遍历,那么节点本身的优先级最低

    这是一棵只有三个节点的二叉树,三种序列如下:

    image-20211002002338208

    而对于任意一个树节点,选择先中后序中的任意一种遍历方式,就等于将这个树节点和它的左右孩子的顺序给出

    下面举例说明,这是一颗二叉树。由整体思维可以将这个二叉树看成三个大的结点

    image-20211002002806847

    即蓝红紫结点,按照我们人为规定的次序,先序,中序,后序整体的进行排序

    image-20211002003011553

    这个时候整体上就将一棵二叉树排好序了。

    那么现在需要局部的排序。

    局部的排序也需要按照实现人为规定的次序。

    由于蓝色结点只有一个元素,所以前中后序都只有他自己一个,就不必排序

    所以下面只需要看红色和紫色。

    红色子树局部排序:

    image-20211002003214305

    紫色子树局部排序:

    image-20211002003307016

    最后将局部排序结果和相同顺序的整体结果组合。

    先序遍历:

    image-20211002003440782

    中序遍历:

    image-20211002003519064

    后序遍历:

    image-20211002003545903

    经过我们人为的规定二叉树结点之间的关系后,二叉树就可以从一个半线性结构转化为线性结构,从而可以遍历整棵树。

    展开全文
  • 二叉树遍历及其应用

    2011-12-08 20:50:41
    数据结构课程设计--二叉树遍历及其应用、对树的先序遍历、后序遍历、中序遍历、层序遍历、二叉树的深度及其叶子树、并打印树形。
  • 二叉树的遍历及应用(栈和队列实现二叉树遍历) 案例树 代码 #include <stdio.h> #include <malloc.h> #include <stdlib.h> #define OK 1 #define ERROR 0 typedef int Status; //(1)二叉树...
  • 这篇文章主要在JS中实现二叉树遍历。 一个二叉树的例子 var tree = { value: 1, left: { value: 2, left: { value: 4 } }, right: { value: 3, left: { value: 5, left: { value: 7 }, right: { ...
  • 二叉树遍历算法

    千次阅读 2019-10-27 01:02:12
    二叉树遍历方式有很多,所以如下介绍的遍历方式,我们约定从左往右进行遍历。 我们需要遍历的树结构如下: 下面的遍历算法用Python实现,不会Python的同学不用担心,因为算法逻辑很简单。 先看下我们的节点对象的定...
  • 课程设计报告数据结构二叉树遍历演示
  • 本程序主要实现的是二叉树的先序,中序,后序遍历算法
  • 二叉树的迭代前中后序遍历 和非迭代的遍历 获取二叉树的高度和结点数
  • 数据结构--二叉树遍历(详细过程)

    千次阅读 2022-04-21 13:35:54
    二、二叉树遍历 先序遍历 DLR (依次遍历:根结点,左子树,右子树) 中序遍历 LDR (依次遍历:左子树,根结点,右子树) 后序遍历 LRD (依次遍历:左子树,右子树,根结点) 看不懂?不急,直接上图。(二叉树就像...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 303,808
精华内容 121,523
关键字:

二叉树遍历