数据结构与算法】树的概念及孩子兄弟表示法"/>
【数据结构与算法】树的概念及孩子兄弟表示法
树的概念
树是 n 个结点的有限集。 n=0 时称为空树。
有且仅有一个特定的称为根的结点
当 n>1 时,其余节点可分为 m 个不相交的有限集 T1,T2…
强调:
n>0时 根节点是唯一的
m>0时 子树个数没有限制,但是一定不会相交。
如图:根节点为A
左子树根节点为B,右子树根节点为C
结点的度:结点拥有的子树数称为结点的度。如A的度为2,B的度为1。
度为0的结点称为叶结点(Leaf)或终端结点,度不为0的结点称为非终端结点或分支结点,除根节点之外,分支结点也称为内部结点。
树的度是树内各结点度的最大值。
结点之间的关系: A是B和C的双亲,B和C是A的孩子,同一双亲的孩子之间互称为兄弟,结点的祖先是从根到该结点所经分支上的所有结点。反之,都是他的子孙。
层次:根为第一层,根的孩子为第二层…
其双亲在同一层的结点互为堂兄弟。如D,E,F。
深度:树中结点最大层次称为深度或高度,上图深度为4。
有序树,无序树:如果将树中结点的各子树看成从左至右是有次序的,不能互换,则为有序树,否则是无序树。
森林:m棵互不相交的树的集合。
对比
线性结构 | 树结构 |
---|---|
第一个数据元素:无前驱 | 根结点:无双亲,唯一 |
最后一个个数据元素:无后驱 | 无孩子,可以多个 |
中间元素:一个前驱,一个后驱 | 中间结点:一个双亲或多个孩子 |
树的储存结构:
最常用的是 孩子兄弟表示法将其转为二叉树来实现(图丑抱歉)
任意一棵树,它的结点的第一个孩子如果就是唯一的,它的右兄弟如果存在也是唯一的。因此,我们设置俩个指针,分别指向该结点的第一个孩子和此结点的右兄弟。
先把树转成二叉树
代码实现
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val=x;}
}
更多推荐
【数据结构与算法】树的概念及孩子兄弟表示法
发布评论