数据结构与算法——二叉树（上）

xeblog 发布于2019-08-16 16:13 / 1286人阅读

摘要：什么是树前面说到的几种数据结构都是线性的，例如链表栈队列等，今天就来学习一种非线性的数据结构树。在上图中的几种二叉树中，有两个是比较特殊的，分别是满二叉树和完全二叉树。除了使用数组存储二叉树外，最常用的便是使用链表法来储存二叉树了。

1. 什么是树？

前面说到的几种数据结构都是线性的，例如链表、栈、队列等，今天就来学习一种非线性的数据结构——树。先来看看几种树的结构：

有没有发现，其实树这种结构跟我们现实生活中的“树”非常的相似，像上图中的这棵“树”，节点 A 称作 B 和 C 的父节点，节点 B 和 C 在同一级，叫做兄弟节点。没有父节点的 A 节点叫做根节点，没有子节点的节点叫做叶子节点或叶节点，例如图中的 D E F G。

树的节点还涉及到三个概念，分别是高度、深度、层。

节点高度：节点到叶子节点的最长路径

节点深度：根节点到这个节点所经历的边的个数

节点的层：节点深度 + 1

树的高度：根节点的高度

结合下面的图你就能够理解了，高度是从下到上数的，深度是从上到下数的：

2. 二叉树

树的形态多种多样，但是我们平常最常用的还是二叉树，顾名思义，二叉树就是每个节点最多只有两个子节点的树。

在上图中的几种二叉树中，有两个是比较特殊的，分别是满二叉树和完全二叉树。

满二叉树：树的叶子节点全在最底层，并且除了叶子节点，每个节点都有左右两个子节点，例如上图中的树 2。

完全二叉树：叶子节点都在最底下两层，最底层的节点全都靠左排列，并且除了最后一层，其他层的节点都必须有左右两个节点，例如上图中的树 3。

完全二叉树的概念有点不太好理解，你可以多思考一下，其实满二叉树就是完全二叉树的一种特殊情况。完全二叉树的这种特性是为了方便其在数组中的存储，不至于浪费太多的内存空间，等后面说到堆的时候你就更能理解了。
除了使用数组存储二叉树外，最常用的便是使用链表法来储存二叉树了。下面说到的二叉树的遍历便是这种存储方法。

3. 二叉树的遍历

二叉树的一种常见操作就是需要遍历得到树种的全部数据，最常用的遍历方式有三种：前序遍历、中序遍历、后序遍历。

前序遍历：对于树中的任意节点来说，先遍历这个节点，然后遍历这个节点的左子节点，最后遍历这个节点的右子节点。（父左右）

中序遍历：对于树中的任意节点来说，先遍历这个节点的左子节点，然后遍历这个节点本身，最后遍历这个节点的右子节点。（左父右）

后序遍历：对于树中的任意节点来说，先遍历这个节点的左子节点，然后遍历这个节点的右子节点，最后遍历这个节点本身。（左右父）

其实树的遍历是一种很典型的递归操作，代码也可以使用递归来实现，你可以看看我实现的代码。

    //1.前序遍历
    public void preOrder(Node head){
        if (head == null) return;
        System.out.print(head.getData() + "  ");
        preOrder(head.left);
        preOrder(head.right);
    }

    //2.中序遍历
    public void midOrder(Node head){
        if (head == null) return;
        midOrder(head.left);
        System.out.print(head.getData() + "  ");
        midOrder(head.right);
    }

    //3.后序遍历
    public void postOrder(Node head){
        if (head == null) return;
        postOrder(head.left);
        postOrder(head.right);
        System.out.print(head.getData() + "  ");
    }

GPU云服务器云服务器二叉树算法最优二叉树算法图二叉树的存储结构 c语言二叉树输入数据

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73977.html

数据结构与算法:二叉树算法

摘要：因此，根据题目给出的先序遍历和中序遍历，可以画出二叉树选参考数据结构与算法描述实现二叉树算法浅谈数据结构二叉树慕课网实现二叉树算法前端树控件腾讯软件开发面试题内容衔接上一章数据结构与算法:常见排序算法内容提要什么是树　　- 为什么使用树二叉树二叉查找树红黑树Ｂ、Ｂ＋树堆伸展树树可以点击链接感受下笔者用d3.js画的tree https://codepen...

Little_XM 2019-08-22 11:09 评论0 收藏0
Java数据结构与算法——二叉树及操作(包括二叉树遍历)

摘要：本篇主要介绍二叉树的概念二叉树的表示二叉树的操作三种遍历方式实现求二叉树的子树求节点的父节点二叉树高度，可能是考试中的，也可能是面试中的。通常二叉树的遍历根据根节点的遍历次序分为先根遍历中根遍历后根遍历。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本篇主要介绍二叉树的概念、二叉树的表示、二叉树的操作（三种遍历...

muddyway 2019-08-16 11:15 评论0 收藏0
Javascript 数据结构与算法——二叉树

摘要：一个节点可以有多个子节点二叉树二叉树是一种特殊的树，子节点数不超过个。以某种特定的顺序访问树中所有的节点称为树的遍历树的层数称为树的深度一个父节点的两个子节点分别称为左节点和右节点二叉查找树又称二叉排序树是一种特殊的二叉树。原文地址：http://www.brandhuang.com/article/1564967352592 1、树一棵树最上面的节点：根结点一个节点下面连接多个...

shengguo 2019-08-26 10:33 评论0 收藏0
数据结构与算法——二叉树(下)

摘要：所以，如果中序遍历二叉搜索树，会得到一个有序的数据，时间复杂度是，所以二叉搜索树又叫做二叉排序树。所以，我们需要一种方式来维持二叉树的平衡，最好是将其维持为满二叉树或者完全二叉树，这就是后面会说到的平衡二叉查找树，常见的有树，红黑树。 1. 概述前面的文章说到了二叉树，其实今天讲的二叉搜索(查找)树就是二叉树最常用的一种形式，它支持高效的查找、插入、删除操作，它的定义是这样的：对于树...

Awbeci 2019-08-16 16:17 评论0 收藏0