树&二叉树&&满二叉树&&完全二叉树&&完满二叉树

目录

名称 作用
树的顶端结点
孩子 当远离根(Root)的时候,直接连接到另外一个结点的结点被称之为孩子(Child);
双亲 相应地,另外一个结点称为孩子(child)的双亲(parent);
兄弟 具有同一个双亲(Parent)的孩子(Child)之间互称为兄弟(Sibling)。
祖先 结点的祖先(Ancestor)是从根(Root)到该结点所经分支(Branch)上的所有结点。
子孙 反之,以某结点为根的子树中的任一结点都称为该结点的子孙(Ancestor)。
叶子(终端结点) 没有孩子的结点(也就是度为0的结点)称为叶子(Leaf)或终端结点。
分支(非终端结点) 至少有一个孩子的结点称为分支(Branch)或非终端结点。
结点所拥有的子树个数称为结点的度(Degree)。
一个结点和另一个结点之间的连接被称之为边(Edge)。
层次 结点的层次(Level)从根(Root)开始定义起,根为第0层,根的孩子为第1层。以此类推,若某结点在第i层,那么其子树的根就在第i+1层。
结点的高度 结点的高度是该结点和某个叶子之间存在的最长路径上的边的个数。
结点的深度 结点的深度是从树的根结点到该结点的边的个数。 (注:树的深度指的是树中结点的最大层次。)

二叉树

定义 : 每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒
性质 :
(1)若二叉树的层次从0开始,则在二叉树的第i层至多有2^i个结点(i>=0)。
(2)高度为k的二叉树最多有2^(k+1) – 1个结点(k>=-1)。 (空树的高度为-1)
(3)对任何一棵二叉树,如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1。

完美二叉树(又名满二叉树)(Perfect Binary Tree)

一个深度为k(>=-1)且有2^(k+1) – 1个结点的二叉树称为完美二叉树。 (注: 国内的数据结构教材大多翻译为”满二叉树”)

例如:
《树&二叉树&&满二叉树&&完全二叉树&&完满二叉树》

完全二叉树(Complete Binary Tree)

完全二叉树从根结点到倒数第二层满足完美二叉树,最后一层可以不完全填充,其叶子结点都靠左对齐。

例如:
《树&二叉树&&满二叉树&&完全二叉树&&完满二叉树》

完满二叉树(Full Binary Tree)

所有非叶子结点的度都是2

例如:
《树&二叉树&&满二叉树&&完全二叉树&&完满二叉树》

    原文作者:Chicago_01
    原文地址: https://www.cnblogs.com/Chicago/p/9539714.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞