文档章节

2叉数的遍历

i
 itgangan
发布于 2014/02/26 17:04
字数 1939
阅读 244
收藏 10

该文主要介绍2叉数的基本遍历的实现,在此之前,首先应该知道2叉数有哪些遍历?


先序遍历:根-->左-->右    即先访问根结点,然后访问左子树,最后访问右子树。在遍历左、右子树时,仍然如此。

上图遍历结果:A,B,D,E,C,F,G。

中序遍历:左-->根-->右    即先访问左子树,然后访问根结点,最后访问右子树。在遍历左、右子树时,仍然如此。

上图遍历结果:D,B,E,A,F,C,G。

后序遍历:左-->右-->根    即先访问左子树,然后访问右子树,最后访问根结点。在遍历左、右子树时,仍然如此。

上图遍历结果:D,E,B,F,G,C,A。

层次遍历:1层,2层,3层,依次访问下来,如果某一层元素超过两个,那么从先左后右访问。

上图遍历结果:A,B,C,D,E,F,G。(这个已经简单不行了)

深度遍历:首先访问根结点(A),然后沿着它的左结点依次访问(B,D),至到访问到最后一层(也就是D),再返回到它的父亲(B),访问他的右结点(E)。然后这样重复地访问完所有结点。

上图遍历结果:A,B,D,E,C,F,G。

备注:

    1.上面的先、中、后序遍历,主要看的就是根在访问顺序中所在的位置。“根左右”,根在前,所以叫先序遍历。“左根右”,根在中,所以叫中序遍历。

    2.在中序遍历中,有一种很快得出其遍历的结果的方法。叫做投影法。(你以为我会把这个方法的链接放在这里么?No,我只会告诉你,请百度百科“中序遍历”,这里有我想给你看的“投影法”。)

如何实现

    先序遍历:首先访问根,然后递归访问左子树,再递归访问右子树即可。

    中/后序遍历:类似于先序遍历。等下看源码就明白了。

层次遍历

    首先将根入队列(先进先出),然后就循环判断这个队列是否为空。只要队列不为空,就取出队列中的一个结点,访问这个结点的值,再将这个结点的左结点入队列,再将这个队列的右结点入队列。

层次遍历详细解释

    以上图的2叉数为例,首先将根A结点入队列,现在用while来循环判断队列是否为空。很明显,不为空。所以取出队列中的结点(A)来访问,然后,这个结点(A)的左结点(B)不为空,入队列,这个结点的右结点(C)也不为空,入队列。所以现在队列中就又有了B、C两个结点,所以循环继续。拿出B,访问B,再将B的左右结点D、E入队列。现在队列中就有了C、D、E了。队列不为空,所以循环继续,拿出C,访问C,再将F,G入队列。现在队列中就是D、E、F、G了。队列不为空,拿出D访问,D没有子结点,那么没有新的结点入队列,但队列还没有为空,所以接着拿出E来访问,E也没有子结点,所以也没有新的结点入队列,但队列还没有为空,接着再拿队列中的F来访问,依次类推了。(写得很罗嗦,希望能把这个过程解释清楚。)

深度遍历

     首先将根入栈(先进后出),然后就循环判断这个栈是否为空。只要栈不为空,就取出栈中的一个结点,访问这个结点的值,再将这个结点的右结点入栈,再将这个结点的左结点入栈。(很类似于层次遍历的实现,只是所用的数据结构由队列变成了栈,入队列是先左后右,入栈的顺序是先右后左)

深度遍历详细解释

    这个很类似于层次遍历的详细解释,我简单得说一下。首先根A入栈,然后循环判断栈是否为空,现在栈里有结点A,所以不为空,所以取出A,访问A,将C、B入栈(也就是将A的右结点入栈,然后左结点入栈,和层次遍历时是相反的)。再判断栈是否为空,现在栈中有C、B。由于栈是后进先出的结构,所以这里是B弹出栈,访问B,再将B的子结点E、D入栈,那现栈中就有了C、E、D。判断栈不空,又弹出D,访问D,将D的子结点入栈。这样类推下去,就完成了遍历。

java代码如下:(有点多,不过该代码可测试运行)

package com.cdu.binaryTree;

import java.util.LinkedList;

public class MyBinaryTree {
    public static void main(String[] args) {
        //初始化一棵2叉数
        BinaryTree binaryTree = BinaryTree.initBinaryTree();

        // 先序遍历
        System.out.println("先序遍历:");
        binaryTree.preOrderTraversal(binaryTree);
        System.out.println("\n");
        
        // 中序遍历
        System.out.println("中序遍历:");
        binaryTree.midOrderTrversal(binaryTree);
        System.out.println("\n");
        
        // 后序遍历
        System.out.println("后序遍历:");
        binaryTree.postOrderTrversal(binaryTree);
        System.out.println("\n");
        
        // 层次遍历
        System.out.println("层次遍历:");
        binaryTree.levelTraversal(binaryTree);
        System.out.println("\n");
        
        // 深度遍历
        System.out.println("深度遍历:");
        binaryTree.depthTraversal(binaryTree);
        System.out.println("\n");
    }
}

class BinaryTree{
    private int data;                    //结点值 
    private BinaryTree left;             //左子结点
    private BinaryTree right;            //右子结点
    
    public BinaryTree(int data){
        this.data = data;
    }
    
    /**
     * @Description 初始化二叉数
     * @param 
     * @return 得到如下所示的二叉数
     *                             1
     *                          *      *
     *                     2                3
     *                  *   *               *   *    
     *                 4       5          6        7
     *                  *     * *
     *                   9   10 11
     *                       *    
     *                      8
     * 
     * 先序遍历结果:1,2,4,9,5,10,8,11,3,6,7
     * 中序遍历结果:4,9,2,8,10,5,11,1,6,3,7
     * 后序遍历结果:9,4,8,10,11,5,2,6,7,3,1
     * 层次遍历结果:1,2,3,4,5,6,7,9,10,11,8
     * 深度遍历结果:1,2,4,9,5,10,8,11,3,6,7
     */
    public static BinaryTree initBinaryTree(){
        BinaryTree root = new BinaryTree(1);
        BinaryTree node2 = new BinaryTree(2);
        BinaryTree node3 = new BinaryTree(3);
        BinaryTree node4 = new BinaryTree(4);
        BinaryTree node5 = new BinaryTree(5);
        BinaryTree node6 = new BinaryTree(6);
        BinaryTree node7 = new BinaryTree(7);
        BinaryTree node8 = new BinaryTree(8);
        BinaryTree node9 = new BinaryTree(9);
        BinaryTree node10 = new BinaryTree(10);
        BinaryTree node11 = new BinaryTree(11);
        
        root.setLeft(node2);
        root.setRight(node3);
        
        node2.setLeft(node4);
        node2.setRight(node5);
        
        node3.setLeft(node6);
        node3.setRight(node7);
        
        node4.setRight(node9);
        
        node5.setLeft(node10);
        node5.setRight(node11);
        
        node10.setLeft(node8);
        
        return root;
    }
    
    /**
     * @Description 先序遍历
     * @param binaryTree 二叉数
     * @return
     */
    public void preOrderTraversal(BinaryTree binaryTree){
        // 当2叉数为空时,递归结束。
        if (binaryTree == null){
            return ;
        }else{
            System.out.print(binaryTree.getData() + ",");            //访问结点
            preOrderTraversal(binaryTree.getLeft());                 //递归遍历左子树
            preOrderTraversal(binaryTree.getRight());                //递归遍历右子树
        }
    }
    
    /**
     * @Description 中序遍历
     * @param binaryTree 二叉数
     * @return
     */
    public void midOrderTrversal(BinaryTree binaryTree){
        if (binaryTree == null){
            return ;
        }else{
            midOrderTrversal(binaryTree.getLeft());
            System.out.print(binaryTree.getData() + ",");
            midOrderTrversal(binaryTree.getRight());
        }
    }
    
    /**
     * @Description 后序遍历
     * @param binaryTree 二叉数
     * @return
     */
    public void postOrderTrversal(BinaryTree binaryTree){
        if (binaryTree == null){
            return ;
        }else{
            postOrderTrversal(binaryTree.getLeft());
            postOrderTrversal(binaryTree.getRight());
            System.out.print(binaryTree.getData()+ ",");
        }
    }
    
    /**
     * @Description 层次遍历:先将根节点入队列,然后判断只要队列不为空,
     *         那么就从队列中poll一个结点来访问,然后再将该结点的左结点入队列,然后再将右结点入队列
     * @param 
     * @return
     */
    public void levelTraversal(BinaryTree binaryTree){
        LinkedList<BinaryTree> queue = new LinkedList<BinaryTree>();
        if (binaryTree != null){
            queue.offer(binaryTree);
        }
        
        // 只要队列不为空,则遍历队列中结点
        while (!queue.isEmpty()){
            BinaryTree node = queue.poll();
            System.out.print(node.getData() + ",");
            
            // 若结点有子结点,那么将该结点的左、右结点存入队列
            if (node.getLeft() != null){
                queue.offer(node.getLeft());
            }
            if (node.getRight() != null){
                queue.offer(node.getRight());
            }
        }
    }
    
    /**
     * @Description 深度遍历:先将根节点入队列,然后判断只要栈不为空,
     *         那么就在栈中pop一个结点来访问,然后再将该结点的右结点压栈,然后再将左结点压栈
     * @param 
     * @return
     */
    public void depthTraversal(BinaryTree binaryTree){
        LinkedList<BinaryTree> stack = new LinkedList<BinaryTree>();
        if (binaryTree != null){
            stack.push(binaryTree);
        }
        
        // 只要栈不为空,则遍历栈中结点
        while(!stack.isEmpty()){
            BinaryTree node = stack.pop();
            System.out.print(node.getData() + ",");
            
            // 若结点有子结点,那么将该结点的右、左结点存入队列
            if (node.getRight() != null){
                stack.push(node.getRight());
            }
            if (node.getLeft() != null){
                stack.push(node.getLeft());
            }
        }
    }
    
    /*--------------getter and setter--------------------*/
    
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public BinaryTree getLeft() {
        return left;
    }
    public void setLeft(BinaryTree left) {
        this.left = left;
    }
    public BinaryTree getRight() {
        return right;
    }
    public void setRight(BinaryTree right) {
        this.right = right;
    }
}


    



© 著作权归作者所有

i
粉丝 1
博文 15
码字总数 9743
作品 0
成都
私信 提问
加载中

评论(3)

陈亦
陈亦

引用来自“itgangan”的评论

引用来自“陈一回”的评论

树的遍历很复杂。先序、中序、后序写起来很简单,但是要分析遍历的过程简直就是个噩梦17

你是指它的递归过程吗?

是的,递归过程以及栈的变化。
i
itgangan 博主

引用来自“陈一回”的评论

树的遍历很复杂。先序、中序、后序写起来很简单,但是要分析遍历的过程简直就是个噩梦17

你是指它的递归过程吗?
陈亦
陈亦
树的遍历很复杂。先序、中序、后序写起来很简单,但是要分析遍历的过程简直就是个噩梦17
数据结构分析之二叉树

概述 在分析树形结构之前,先看一下树形结构在整个数据结构中的位置 数据结构 当然,没有图,现在还没有足够的水平去分析图这种太复杂的数据结构,表数据结构包含线性表跟链表,也就是经常说...

wustor
2017/11/06
0
0
【javascript实现】几道题目带你学习二叉搜索树

二叉树大家都知道,二叉搜索树满足以下特征: 节点的左子树只包含小于当前节点的数 节点的右子树只包含大于当前节点的数 所有左子树和右子树自身必须也是二叉搜索树 二叉搜索树也叫二叉排序树...

陈小俊
2018/11/27
0
0
每周一练 之 数据结构与算法(Tree)

这是第六周的练习题,最近加班比较多,上周主要完成一篇 GraphQL入门教程 ,有兴趣的小伙伴可以看下哈。 下面是之前分享的链接: 1.每周一练 之 数据结构与算法(Stack) 2.每周一练 之 数据...

pingan8787
05/20
0
0
树与二叉表达树

树基础 定义 数的定义 可以使用递归的方法定义:一棵树是一些节点的集合。一棵树由根节点和0~多个非空树(即子树)组成。这些子树中的每一颗根节点都被来自母树跟的一条有向边链接。母树的根...

月见樽
2017/12/12
0
0
Tommy Yang/BinaryTree

二叉树(Binary Tree)定义: 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。 二...

Tommy Yang
2017/03/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx学习之模块

1、 stub_status模块: 用于展示nginx处理连接时的状态。 配置语法如下: Syntax:stub_status;Default:默认没有配置Context:server、location 可以编辑default.conf,加上如下配置: ...

码农实战
54分钟前
4
0
MySQL,必须掌握的6个知识点

目录 一、索引B+ Tree 原理 MySQL 索引 索引优化 索引的优点 索引的使用条件 二、查询性能优化使用 Explain 进行分析 优化数据访问 重构查询方式 三、存储引擎InnoDB MyISAM 比较 四、数据类...

李红欧巴
58分钟前
5
0
堆”和“栈

C++作为一款C语言的升级版本,具有非常强大的功能。它不但能够支持各种程序设计风格,而且还具有C语言的所有功能。我们在这里为大家介绍的是其中一个比较重要的内容,C++内存区域的基本介绍。...

SibylY
今天
4
0
总结:Https

一、介绍 简单理解,https即在http协议的基础上,增加了SSL协议,保障数据传输的安全性。 它由以前的http—–>tcp,改为http——>SSL—–>tcp;https采用了共享密钥加密+公开密钥加密的方式 ...

浮躁的码农
今天
6
0
数据库表与表之间的一对一、一对多、多对多关系

表1 foreign key 表2 多对一:表 1 的多条记录对应表 2 的一条记录 利用foreign key的原理我们可以制作两张表的多对多,一对一关系 多对多: 表1的多条记录可以对应表2的一条记录 表2的多条记...

Garphy
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部