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个结点的二叉树。也就是说， 除了叶子结点之外的每一个结点都有两个孩子，每一层(当然包含最后一层)都被完全填充。
如下图所示：
完美二叉树.png
2.1.2 完全二叉树
英文：
CBT(Complete Binary Tree)。
定义：
从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。
如下图所示：
完全二叉树.png
2.1.3 完满二叉树
英文：
FBT(Full Binary Tree)，又称为：Strictly Binary Tree。
定义：
所有非叶子结点的度都是2。换句话说，只要你有孩子，你就必然是有两个孩子。
如下图所示：
完满二叉树.png
2.2 二叉树遍历
2.2.1 前序遍历
2.2.2 中序遍历
2.2.3 后序遍历
2.3 二叉树实现的计算器
按照这个要求来看，需要做到的有：
* 能够含有( )、+、-、*、/ 等运算符的实数表达式计算功能
* 能够处理小数和负数
* 能够处理求余运算符（%）
* 能够处理乘方（^）
* 能够处理exp、sin、cos、tan、ctan等常见函数
* 能够打印包含括号的中缀表达式
网友评论