写在前面:
本文前面部分介绍相关概念,后面部分是程序。
点击下面链接查看更多!
一、二叉树的概念
1.1 相关术语
①结点:包含一个数据元素及若干指向子树分支的信息 。
②结点的度:一个结点拥有子树的数目称为结点的度。
③叶子结点:也称为终端结点,没有子树的结点或者度为零的结点。
④分支结点:也称为非终端结点,度不为零的结点称为非终端结点。
⑤树的度:树中所有结点的度的最大值。
⑥结点的层次:从根结点开始,假设根结点为第1层,根结点的子节点为第2层,依此类推,如果某一个结点位于第L层,则其子节点位于第L+1层 。
⑦树的深度:也称为树的高度,树中所有结点的层次最大值称为树的深度 。
⑧有序树:如果树中各棵子树的次序是有先后次序,则称该树为有序树。
⑨无序树:如果树中各棵子树的次序没有先后次序,则称该树为无序树 。
⑩森林:由m(m≥0)棵互不相交的树构成一片森林。如果把一棵非空的树的根结点删除,则该树就变成了一片森林,森林中的树由原来根结点的各棵子树构成 。
1.2 相关性质
性质1:二叉树的第i层上至多有