1 学习的内容
在之前分析finsh shell的时候，看到siblings，随手一搜，发现这个是在二叉树中提到的，所以学习一下。
二叉树，分为完美二叉树、完全二叉树和完满二叉树。
2 树
我抄一个定义，链接
树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。
这里面提到的结点，在finsh shell中同样也提到过，也就是node。这里还是要区分一下：
节点和结点：
- joint和connection为节点。"节点"是物理概念，是对实际结构中的一个"节段"与另一个"节段"物理连接区的统称。
- node是结点。"结点"是力学概念，是在力学模型上根据分析需要所设置的标识点或计算点。
姑且可以参考：链接
也将树的一些概念性内容贴出来：
| 英文 | 中文 | 含义 |
|---|---|---|
| root | 根 | 树的顶端结点 |
| child | 孩子 | 当远离根(Root)的时候，直接连接到另外一个结点的结点被称之为孩子(Child) |
| parent | 双亲 | 相应地，另外一个结点称为孩子(child)的双亲 |
| siblings | 兄弟 | 具有同一个双亲(Parent)的孩子(Child)之间互称为兄弟 |
| ancestor | 祖先 | 结点的祖先(Ancestor)是从根（Root）到该结点所经分支(Branch)上的所有结点 |
| descendant | 子孙 | 反之，以某结点为根的子树中的任一结点都称为该结点的子孙(Ancestor) |
| leaf | 叶子 | 没有孩子的结点(也就是度为0的结点)称为叶子(Leaf)或终端结点 |
| branch | 分支 | 至少有一个孩子的结点称为分支(Branch)或非终端结点 |
| degree | 度 | 结点所拥有的子树个数称为结点的度(Degree) |
| edge | 边 | 一个结点和另一个结点之间的连接被称之为边 |
| path | 路径 | 连接结点和其后代的结点之间的(结点,边)的序列 |
| level | 层次 | 结点的层次(Level)从根(Root)开始定义起，根为第0层，根的孩子为第1层。以此类推，若某结点在第i层，那么其子树的根就在第i+1层 |
| Height of node | 结点的高度 | 结点的高度是该结点和某个叶子之间存在的最长路径上的边的个数 |
| Height of tree | 树的高度 | 树的高度是其根结点的高度 |
| Depth of node | 结点的深度 | 结点的深度是从树的根结点到该结点的边的个数 |
| Forest | 森林 | 森林是n(>=0)棵互不相交的树的集合 |
2.1 二叉树
每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒
其具有以下的性质：
- 若二叉树的层次从0开始，则在二叉树的第i层至多有2^i个结点(i>=0)。
- 高度为k的二叉树最多有2^(k+1) - 1个结点(k>=-1)。 (空树的高度为-1)
- 对任何一棵二叉树，如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1。
2.1.1 完美二叉树
英文：
PBT(perfect binary tree)。
定义：
一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树。也就是说， 除了叶子结点之外的每一个结点都有两个孩子，每一层(当然包含最后一层)都被完全填充。
如下图所示：
2.1.2 完全二叉树
英文：
CBT(Complete Binary Tree)。
定义：
从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。
如下图所示：
2.1.3 完满二叉树
英文：
FBT(Full Binary Tree)，又称为：Strictly Binary Tree。
定义：
所有非叶子结点的度都是2。换句话说，只要你有孩子，你就必然是有两个孩子。
如下图所示：
2.2 二叉树遍历
2.2.1 前序遍历
2.2.2 中序遍历
2.2.3 后序遍历
2.3 二叉树实现的计算器
按照这个要求来看，需要做到的有：
* 能够含有( )、+、-、*、/ 等运算符的实数表达式计算功能
* 能够处理小数和负数
* 能够处理求余运算符（%）
* 能够处理乘方（^）
* 能够处理exp、sin、cos、tan、ctan等常见函数
* 能够打印包含括号的中缀表达式
