数据结构之初识树

大家好，我是1z，从这篇文章开始我将带着大家走近’树’的世界。作为数据结构中不可缺少的一环，它又有哪些耐人寻味的故事呢？

当我第一次听数据结构这门课的时候，提到‘树’这个概念的时候。难免会看向窗外，满眼的郁郁葱葱。

在没有抽象这棵‘树’之前，脑子里思考的是如何将这抹绿意搬到IDEA中。随着学习的深入，后才知道数据结构中的树和现实中的树其实有着一定的相似之处，却有些不同。

1:初识树？

在正式学习树这种结构之前，我先举出生活中的几个例子。

大家可以看着上面两张图，然后把画面倒转180°，就会发现最下面的单个节点不断向上进行发散。就像一棵真正的树，从底端的“根”，一直不断向上延伸。所以，这就是为什么将这种结构称为 ‘树’。

ps: 关于文章中出现关于节点和结点的问题，统一使用节点表示。

此部分为概念，如果有缺漏的地方，大家可以自行百度，谷歌..

如果存在两个节点node1 和 node2，存在唯一一条边连接node1,node2,且方向为 node1 -> node2，则称node1 是node2的父节点，node2是node1的子节点
如果在一棵树中，每个节点最多只允许有两个子节点，称该树为 ‘二叉树（binary tree）
如果不同的节点 node1,node2有着相同的父节点，则称呼node1,node2彼此为兄弟节点
两个节点直接连接的线，称为’边’（edge）
根节点到任何节点之间，存在着唯一的路径，路径经历的边数(可能含有权值)，称为’路径的长度’
根节点到达任意一个节点的路径长度，称之为该节点的‘深度’（深度是从上向下看）
从某个节点的最深处叶子节点到该节点的路径长度，称为该节点的高度（高度是从下向上看）
节点拥有的子树数量称为节点的度，当前树中节点度的最大值称为该树的度

tip: 为了明确上述定义，这里我将绘制一棵简单的树，同时对应着上述的定义绘制表格。

概念名称	说明	示例
父节点	唯一路径连接的起始端	A是B的父节点
子节点	唯一路径连接的末端	B是A的子节点
兄弟节点	拥有相同父节点，位于同一级的节点	B和C
二叉树	每个节点最多拥有两个节点	当前绘制的为二叉树
边	两个节点直接相连的线	edge1,edge2…
路径	根节点到达某一子节点经过的边
路径长度	根节点到达某一子节点经过的边之和（注意是否累加权值）	A节点为root，路径长度为0，B节点路径长度为1，D节点路径长度为2
深度	根节点到达任意一个节点的路径长度	A节点深度为0，B节点深度为1
高度	从某个节点的最深处叶子节点到该节点的路径长度	A节点高度为2，B节点高度为1
度	节点拥有的子树数量称为节点的度，当前树中最大节点的度称为该树的度	B节点度为2，A节点度为2，D节点度为0（叶子节点）二叉树的度为2

此处总结自<<大话数据结构>> 6.4 树的存储结构，大家在阅读之余可以去查阅原著，获得更多收获。

树在保存时，当前节点除了保存数据域，也要表示父节点的位置

class Node{
  int val;
  Node parent = null;
  public Node(int val){
    this.val = val;
  }
}

树在保存时，节点除了保存数据域，也要表示孩子的位置

//这里以二叉树为例
class Node{
  int val;
  Node left = null;//左子树引用
  Node right = null;//右子树引用
  public Node(int val){
    this.val = val;    
  }
}

class Node{
  int val;
  Node firstNode;
  Node nextBro;
  public Node(int val){
    this.val = val;
  }
}

那有没有什么好的思路解决可以快速查询父节点和兄弟节点呢？

这篇文章讲述了关于树的基础知识，其中包括对树的概念，一些基础名词，树的表示方法等，同时也是树这一系列内容的第一篇。接下来会逐渐深入，从介绍二叉树的一些内容，递归非递归遍历过渡到bst，dfs，哈夫曼编码，再到关于AVL树，B树，B+树，红黑树的具体应用等。

希望可以模拟从一个对树完全陌生的同学，逐渐去深入这一复杂的数据结构所经历的流程。那么，今天的内容就到这，我是1z，咱们下期再见吧!

往期推荐：

我们是FingerDance，欢迎加入我们！

原文始发于微信公众号（FingerDance）：数据结构之初识树

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/26699.html