树-数据结构

树是计算机科学中常用的数据结构之一,常见的地方有，Java 的继承树等。

还有一些基于树的特殊数据结构，比如二叉树，B 树，等等。

本篇会讲述一些关于简单关于树的操作。

树的定义

树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点有零个或多个子节点

没有父节点的节点称为根节点

每一个非根节点有且只有一个父节点

除了根节点外，每个子节点可以分为多个不相交的子树

节选自树(数据结构)

定义数据结构

前序遍历

先遍历根节点。在遍历孩子节点。

循环版

递归版

后序遍历

先遍历孩子节点，最后遍历根节点。

循环版

递归版

层次遍历

按层遍历节点。

循环版

求树的深度

计算树的最大深度。

求树的结点数

计算树一共有多少节点。

求树的叶子数

计算书中有多少没有孩子的节点。

求两个结点的最低公共祖先结点

首先需要在树中找到两个结点。

保存找到两个节点的链表。

遍历两个链表的最长公共节点，就能找到最低的公共祖先节点。

求任意两结点距离

首先需要在树中找到两个结点。

保存找到两个节点的链表。

在判断剩余的长度

综述

以上就是和树有关联的简单代码。

以上代码也在 Github 上发布tree， 如有差错，欢迎提交 Issue 或 PR。