Aloha～！又是我少女人妻Uerica！这阵子家人住院，从急诊到加护病房再到普通病房，看到形形色色的病人，不免让我不停思考人生追求是什麽，每个生病的人都长一样，一样的病人服、一样的病床、一样的不舒服，完全看不出这些人有多少财富或多高的成就。但我能看到的是他跟家人或朋友感情好不好，有没有好好对待自己的身体，所以要好好爱自己还有身边的人啊！

好的来进入主题吧～！

树 (Tree)

树是一种阶层关系的资料结构，分支型的结构就像树干与树枝的关系一样。生活中常见的例子有家族族谱、决策模型等。

树的定义与特性

树是由一个根节点(Root)开始发展，在树状结构中的最基本单位，称为节点
(Node)，而分支出去的节点称为子节点(Child)。树是没有环的结构，且任意两节点间只有一个唯一路径，若随意删除其中一个枝 (Branch)，就会变两个树。

• 节点 (Node)：树状结构中每一个资料元素都称为节点。
• 枝 (Branch)：节点向下延伸扩展的所用到的枝。
• 根节点 (Root)：根节点具有唯一性，是整个树状结构最上层的树根。
• 叶节点 (Leaf)：节点之下都没有子节点称为叶节点(像树叶的叶子)。
• 非终端点 (Non-terminal Nodes)：除了叶节点外的其他节点。
• 祖先节点 (Ancenstors) 与子孙节点 (Descendant)：一个节点往上走一直到根节点之前，所经过的节点都称为祖先节点。一个节点往下走，到叶节点前，每个经过的节点都称为子孙节点。
• 父节点 (Parent)与子节点 (Child)：被分支的节点上方一个节点称为此节点的父节点，而节点向下分支出的节点称为子节点。如同父子关系般，父节点通常只有一个，子节点可以有一个或多个。
• 兄弟节点 (Siblings)：同一个父节点的其他节点，称为兄弟节点。
• 分支度 (Dregree)：每个节点所拥有的子节点数。
• 阶层 (Level)：从树根开始，向下延伸的层级。
• 树深 (Depth)：节点与节点间的距离。根节点深度为 0 。

树的类型

一般的树都是有序树 (OrderedTree)，指树中任意节点与子节点之间是有顺序关系的，每个节点的子节点是从左到右有次序的，另外还有无序树（UnoderedTree），又称「自由树」，树中任意节点的子节点之间没有顺序关系。以下介绍的都属於有序树。

二元树（Binary tree）

树依照不同的分支度可以区分成很多种类，但在资料结构中最广泛使用的树状结构是二元树。二元树是指树中的每一个节点 (Node) 最多只分支出2个子节点，，即分支度小於或等於 2 。二元树的节点所分支的子节点，在左边的称为左子树 (Left Sub-tree)、右边则称为右子树 (Right Sub-tree)。

依照分支与节点的不同，还有下列几种表示：

歪斜树(Skewed Tree)
树的每个节点的分支都只有左节点，或都只有右节点。

严格二元树 (Strictly binary tree)
指的是每个节点的子节点只能是 0 或 2 的二元树，简单来说就是除了叶节点以外，每个节点都有两个子节点。

完满二元树 (Full Binary Tree)
又称 Perfect Binary Tree ，如果树的高度是 k 节点，那节点的个数就是 2 的 k - 1 次方，是具有最多节点的二元树。除了叶节点外，每个节点都有两个子节点。

完整二元树 (Complete Binary Tree)
指的是在一个树中，除了最後一层外，其余的节点都有两个子节点，且遵循由上而下、由左至右排列。

二元搜寻树（Binary Search Tree）

二元搜寻数其实也算二元树的一种，只是在节点的资料排列上有些需遵循的特性。二元树搜寻树的每一个节点值都不相同，而每一个节点的资料大於左边的子节点、小於右子节点的资料值。若左右都没有子节点则是该层的最大或最小值。

AVL树 (Adelson-Velsky and Landis Tree)

AVL树是属於二元搜寻树的一种，所以符合二元搜寻树的所有特性。但除了二元搜寻树的特性外，AVL还必须符合每一个节点的的左边子节点的高度-右边子节点的高度只能是 -1、0、1，所以 AVL树 也是平衡树的一种，此特性让整个树不会长歪，在搜寻时的速度会更快。

红黑树（Red–black tree）

红黑树也是二元搜寻树的一种，且与 AVL 树的作用类似，也是为了要保持树状结构的平衡，而红黑树遵循以下特性：

• 树上的每个节点 (node) 只能是红色或黑色
• 根节点 (root) 一定要是黑色
• 叶节点 (leaf) 一定要是黑色的空值 (NULL)
• 红色节点的两个子节点 (child) 一定要是黑色 (亦即不能有两个红色节点相连，注意：黑色节点的子节点颜色没有限制)
• 从任何节点出发，其下至叶节点所有路径的黑色节点数目要相同

参考资料：

[资料结构] CH8. AVL Trees

用JavaScript学习资料结构与演算法 8：树、 二元搜寻树

树状结构_维基百科

资料结构的树与二元树（Trees and Binary Trees）

演算法笔记:Tree

Red-Black Tree / 红黑树

红黑树（Red Black Tree）介绍

Binary Tree: Intro(简介)

JavaScript 学演算法（十二）- 树 & 二元树

好的今天就到这边啦～记得多关心身边的人喔～明天见啦掰掰！