数据结构:图文详解二叉树(遍历、类型、操作)


前言

  • 二叉树是一种特殊的树结构,应用广泛
  • 下面,我将详细介绍 二叉树的相关知识,希望你们会喜欢。

目录

示意图

1. 简介

示意图

2. 性质

示意图

3. 存储结构

二叉树的存储结构包括:顺序存储结构 & 链式存储结构

示意图

注:上述的链式存储方式,即为树结构中的孩子兄弟表示法。具体如下:

示意图

大多数情况下,二叉树的建立会采用 链式存储结构


4. 二叉树的建立

建立的核心:
数据结构 = 链表 、实现方式 = 递归 / 非递归 算法

4.1 数据结构

采用链表的方式,也称为:二叉链表

  1. 为了确保每个结点都有左右孩子,所以空指针 = 虚结点 = #
  2. 这种处理也称:扩展二叉树
示意图
  • 节点结构 & 树的定义如下
   /**
     * 设置结点结构
     */
    public static class TreeNode<T> {
        T val; // 二叉树的结点数据
        TreeNode<T> leftNode; // 二叉树的左子树(左孩子)
        TreeNode<T> rightNode; // 二叉树的右子树(右孩子)

        public TreeNode(T data,TreeNode<T> left,TreeNode<T> right) {
            this.val = data;
            this.leftNode = left;
            this.rightNode = right;
        }


        // 获得 & 设置二叉树的结点数据
        public T getData(){
            return val;
        }

        public void setData(T data){
            this.val = data;
        }

        // 获得 & 设置二叉树的左子树(左孩子)
        public TreeNode getLeftNode(){
            return leftNode;
        }

        public void setLeftNode(TreeNode leftNode){
            this.leftNode = leftNode;
        }

        // 获得 & 设置二叉树的右子树(右孩子)
        public TreeNode getRightNode(){
            return rightNode;
        }
        public void setRightNode(TreeNode rightNode){
            this.rightNode = rightNode;
        }
    }


/**
 * 作用:构造二叉树
 * 注:必须逆序建立,即:先建立子节点,再逆序往上建立
 * 原因:非叶子节点会使用到下面的节点,而初始化是按顺序初始化的,不逆序建立会报错
 */ 
public Node init(){
    // 结构如下:(由下往上建立)
    //            A
    //       B         C
    //    D         E     F
    //  G   H         I
    Node I = new Node("I", null, null);
    Node H = new Node("H", null, null);
    Node G = new Node("G", null, null);
    Node F = new Node("F", null, null);
    Node E = new Node("E", null, I);
    Node D = new Node("D", G, H);
    Node C = new Node("C", E, F);
    Node B = new Node("B", D, null);
    Node A = new Node("A", B, C);
    return A;  // 返回根节点
}

4.2 递归 算法

  • 通过 递归方式 构造出整个二叉树
  • 构造过程 = 将遍历算法的输出结点操作 替换成: 生成结点 & 赋值操作 即可

关于遍历算法,下节会详细说明


5. 二叉树的遍历

5.1 定义

从根节点出发,按照某种次序访问二叉树中的所有结点,使得每个结点被访问1次 且 只被访问1次

5.2 遍历方式

二叉树的遍历方式包括:

  1. 前序遍历(深度优先遍历)
  2. 中序遍历
  3. 后序遍历
  4. 层序遍历(广度优先遍历)

5.3 遍历实现

遍历的实现方式分为:递归 & 非递归方式,下面会详细说明

5.3.1 前序遍历

也称 深度优先遍历

  • 简介
示意图
  • 递归实现
   /**
     * 内容:前序遍历
     * 方式:递归
     */
     public void preOrder(Node root){
        // 1. 判断二叉树结点是否为空;若是,则返回空操作
        if(root ==null)
            return;

        // 2. 访问根节点(显示根结点)
        printNode(root);

        // 3. 遍历左子树
        preOrder(root.getLeftNode());

        // 4. 遍历右子树
        preOrder(root.getRightNode());

    }
示意图
  • 非递归实现
    主要采用 栈实现
    流程图
/**
  * 方式:非递归(栈实现)
  */
    public static void preOrder_stack(Node root){

        Stack<Node> stack = new Stack<Node>();

        // 步骤1:直到当前结点为空 & 栈空时,循环结束
        while(root != null || stack.size()>0){

            // 步骤2:判断当前结点是否为空
              // a. 若不为空,执行3
              // b. 若为空,执行5
              if(root != null){

                // 步骤3:输出当前节点,并将其入栈
                printNode(root);
                stack.push(root);

                // 步骤4:置当前结点的左孩子为当前节点
                // 返回步骤1
                root = root.getLeftNode();

            }else{

                // 步骤5:出栈栈顶结点
                root = stack.pop();
                // 步骤6:置当前结点的右孩子为当前节点
                root = root.getRightNode();
                  // 返回步骤1
            }
        }
    }
示意图

5.3.2 中序遍历

  • 简介
示意图
  • 递归实现
/**
  * 方式:递归
  */
    public void InOrder(Node root){
    
        // 1. 判断二叉树结点是否为空;若是,则返回空操作
        if(root ==null)
            return;

        // 2. 遍历左子树
        InOrder(root.getLeftNode());

        // 3. 访问根节点(显示根结点)
        printNode(root);

        // 4. 遍历右子树
        InOrder(root.getRightNode());

    }
示意图
  • 非递归实现
    主要采用 栈实现
流程图
/**
  * 方式:非递归(栈实现)
  */
    public static void InOrder_stack(Node root){

        Stack<Node> stack = new Stack<Node>();

        // 1. 直到当前结点为空 & 栈空时,循环结束
        while(root != null || stack.size()>0){

            // 2. 判断当前结点是否为空
            // a. 若不为空,执行3、4
            // b. 若为空,执行5、6
            if(root != null){

                // 3. 入栈当前结点
                stack.push(root);

                // 4. 置当前结点的左孩子为当前节点
                // 返回步骤1
                root = root.getLeftNode();

            }else{

                // 5. 出栈栈顶结点
                root = stack.pop();
                // 6. 输出当前节点
                printNode(root);
                // 7. 置当前结点的右孩子为当前节点
                root = root.getRightNode();
                // 返回步骤1
            }
        }

5.3.3 后序遍历

  • 简介
示意图
  • 递归实现
/**
  * 方式:递归
  */
    public void PostOrder(Node root){
        // 1. 判断二叉树结点是否为空;若是,则返回空操作
        if(root ==null)
            return;

        // 2. 遍历左子树
        PostOrder(root.getLeftNode());

        // 3. 遍历右子树
        PostOrder(root.getRightNode());

        // 4. 访问根节点(显示根结点)
        printNode(root);

    }
示意图
  • 非递归实现
    主要采用 栈实现
示意图
/**
  * 方式:非递归(栈实现)
  */
    public void PostOrder_stack(Node root){

        Stack<Node> stack = new Stack<Node>();
        Stack<Node> output = new Stack<Node>();

        // 步骤1:直到当前结点为空 & 栈空时,循环结束——> 步骤8
        while(root != null || stack.size()>0){

            // 步骤2:判断当前结点是否为空
            // a. 若不为空,执行3、4
            // b. 若为空,执行5、6
            if(root != null){

                // 步骤3:入栈当前结点到中间栈
                output.push(root);

                // 步骤4:入栈当前结点到普通栈
                stack.push(root);

                // 步骤4:置当前结点的右孩子为当前节点
                // 返回步骤1
                root = root.getRightNode();

            }else{

                // 步骤5:出栈栈顶结点
                root = stack.pop();
                // 步骤6:置当前结点的右孩子为当前节点
                root = root.getLeftNode();
                // 返回步骤1
            }
        }

        // 步骤8:输出中间栈的结点
        while(output.size()>0){
            printNode(output.pop());

        }

    }
示意图

5.3.4 层序遍历

  • 简介
示意图
  • 实现思路
    非递归实现,采用 队列
示意图
  • 算法流程图


    示意图
/**
  * 方式:非递归(采用队列)
  */
    public void levelTravel(Node root){
        // 创建队列
        Queue<Node> q=new LinkedList<Node>();

        // 1. 判断当前结点是否为空;若是,则返回空操作
        if(root==null)
            return;
        // 2. 入队当前结点
        q.add(root);

        // 3. 判断当前队列是否为空,若为空则跳出循环
        while(!q.isEmpty()){

            // 4. 出队队首元素
            root =  q.poll();

            // 5. 输出 出队元素
            printNode(root);

            // 6. 若出队元素有左孩子,则入队其左孩子
            if(root.getLeftNode()!=null) q.add(root.getLeftNode());

            // 7. 若出队元素有右孩子,则入队其右孩子
            if(root.getRightNode()!=null) q.add(root.getRightNode());
        }
    }
示意图

5.4 遍历方式总结

示意图

6. 二叉树的类型

  • 上述讲解的是基础的二叉树
  • 根据不同的需求场景,二叉树分为许多类型,主要有:
示意图
  • 下面,我将详细讲解各种二叉树的类型

6.1 线索二叉树

  • 简介
示意图
  • 示意图


    示意图
  • 特别注意

    • 问:如何区别该指针 = 指向左(右)孩子 or 前驱(后继)
    • 答:增设标志域:Ltag 和 Rtag
示意图

6.2 二叉排序树

也称:二叉查找树、二叉搜索树

  • 特点


    示意图
  • 作用 & 应用场景

示意图

6.3 平衡二叉排序树(AVL树)

属于 二叉搜索树的一种特殊类型

  • 特点
示意图
  • 具体介绍
示意图

6.4 红黑树

属于 二叉搜索树的一种特殊类型

示意图

6.5 赫夫曼树

  • 简介
示意图
  • 哈夫曼树算法
    即,如何找出哈弗曼树。具体算法请看下图
算法描述
示意图

更加详细请看文章:http://www.cnblogs.com/mcgrady/p/3329825.html

  • 哈夫曼编码
示意图

更加详细请看文章:http://blog.csdn.net/lfeng_coding/article/details/47782141

6.6 其他类型(特殊形态)

包括:斜树、满二叉树 & 完全二叉树

示意图

6.7 总结

示意图

7. 总结

  • 本文主要讲解了数据结构中的二叉树
  • 下面我将继续对 数据结构进行讲解,有兴趣可以继续关注Carson_Ho的简书

欢迎关注Carson_Ho的简书!

不定期分享关于安卓开发的干货,追求短、平、快,但却不缺深度


请点赞!因为你的鼓励是我写作的最大动力!

相关文章阅读
Android开发:最全面、最易懂的Android屏幕适配解决方案
Android事件分发机制详解:史上最全面、最易懂
Android开发:史上最全的Android消息推送解决方案
Android开发:最全面、最易懂的Webview详解
Android开发:JSON简介及最全面解析方法!
Android四大组件:BroadcastReceiver史上最全面解析
Android四大组件:Service服务史上最全面解析

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 202,980评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,178评论 2 380
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 149,868评论 0 336
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,498评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,492评论 5 364
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,521评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,910评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,569评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,793评论 1 296
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,559评论 2 319
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,639评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,342评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,931评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,904评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,144评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,833评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,350评论 2 342

推荐阅读更多精彩内容