本文共 1055 字,大约阅读时间需要 3 分钟。
一、常用术语:
1)树的节点
2)节点路径:
从根节点到该节点所经历的节点和分支的顺序。
3)路径长度:
节点路径包含的分支数。
4)节点的度:
节点拥有的子树的数目。
5)树的度:
所有节点的度 中 的最大值。
6)叶子节点(终端节点)
树中 节点的度为0的节点。
7)分支节点(非终端节点)
树中 节点的度不为0的节点。树中除了叶子节点的其他节点。
8)孩子节点(子节点)
一个节点的子节点是指 该节点 子树的根结点。
9)双亲节点(父节点)
如果一个节点有子节点,那么他就是这个子节点的父节点。
10)子孙节点
一个节点的子孙节点是指这个节点的所有子树中的任意节点。
11)祖先节点
一个节点的祖先节点是指该节点的路径中除此节点之外的所有节点。
12)兄弟节点
具有同一双亲的节点。
13)节点层次
根结点层次为 0,其他节点层次为 父节点层次 +1。
14)树的深度
所有节点中层次数最大值 +1。
15)有序树
各节点的所有子树之间从左到右有严格的次序关系,不能互换。
16)无序树
各节点的所有子树之间没有严格的次序关系。
17)森林
m(m>=0)棵互不相交的树所构成的集合。
二、二叉树(特殊的树)
1、每个节点最多有两棵子树,并且子树也是二叉树。
2、二叉树允许只有右子树;一般树中不允许。
3、满二叉树
4、完全二叉树
5、单分支树
1)定义:所有节点没有右孩子或没有左孩子。
2)例如
三、二叉树的性质
1、二叉树中第i(i>=0)层上的节点数最多为2的i次幂。
2、深度为h(h>=1)的二叉树最多有2^h -1 个节点
3、叶子节点为n0,度为2的节点个数为n2则 n0 = n2 +1。
4、具有n个节点的完全二叉树,其深度为log2(n)+ 1 或者 log2(n+1)
5、对于具有n个节点的完全二叉树,节点从0开始编号。
1)i = 0 二叉树的根结点;i>1,i节点的双亲编号(i-1)/2。
2)若2i+1>=n,i节点无左孩子,否则 2i+1 为其左孩子
3)若2i+2>=n,i节点无右孩子,否则 2i+2 为其右孩子
4、二叉树 与 树 、森林的转换
1)二叉树与树的转换
树 —>二叉树
(1)断右子(加线)
(2)连兄弟(断线)
(3)顺转45‘
二叉树 —> 树
(1)逆转45’(加线)
(2)断兄弟(断线)
(3)找双亲
2)二叉树 《=》树《=》 森林
森林 —> 树
方法:第一棵树根结点 为 树的根结点,其他树为右孩子
反之亦然
森林 <—> 二叉树
转载地址:https://lipenglin.blog.csdn.net/article/details/50068517 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!