数据结构:树的定义和基本概念

一、树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中:(1)有且仅有一个特定的称为根(root)的结点。

(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,....,Tm, 其中每一个集合本身又是一棵树,并且称为根的子树(SubTree),如图1所示:

图1

树的定义之中还用到了树的概念,即递归定义。如图2中的子树T1和T2就是根结点A的子树。当然D,G,H,I 组成的的树又是B结点的子树,E,J 组成的树是C结点的子树。

图2

对于树的定义还需要注意两点:

1.n>0时根结点是唯一的,不可能存在多个根结点。

2.m>0时,子树的个数没有限制,但它们一定是互不相交的。如图3中的两个结构就不符合树的定义,因为它们都有相交的子树。

图3

二.树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的度(Degree)。度为0的结点称为叶结点(Leaf)或终端结点;度不为0的结点称为非终端结点或分支结点,除根结点之外,分支结点也称为内部结点。树的度是树内各结点的度的最大值。如图4,因为这棵树结点的度的最大值是结点D的度3,所以树的度也为3。

图4

结点的子树的根称为该结点的孩子(Child),相应地,该结点称为孩子的双亲(Parent),同一个双亲的孩子之间互称为兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。所以对于H来说,D,B,A都是它的祖先。反之,以某结点为根的子树中的任一结点都称为该结点的子孙。B的子孙有D,G,H,I,如图5所示。

图5

三、结点的层次(Level)从根开始定义起,根为第一层,根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。显然在图6中D,E,F都是堂兄弟,而

G,H,I 与 J也是堂兄弟。树中结点的 最大层次称为树的深度(Depth)或高度,当前树的深度为4(注:也有一些书是定义为branches的个数,此时认为

深度为3)。

图6

若将树中每个结点的各子树看成是从左到右有次序的(即不能互换),则称该树为有序树(OrderedTree);否则称为无序树(UnorderedTree)。注意:若不特别指明,一般讨论的树都是有序树。

森林(Forest)是m(m≥0)棵互不相交的树的集合。对树中每个结点而言,其子树的集合即为森林。对于图1的树而言,图2的两棵子树其实就可以理解为森林。树和森林的概念相近。删去一棵树的根,就得到一个森林;反之,加上一个结点作树根,森林就变为一棵树。

对比线性表与树的结构,它们有很大不同,如图7所示。

图7

参考:《大话数据结构》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏kevindroid

leetcode110 Balanced Binary Tree

15950
来自专栏郭耀华‘s Blog

数据结构二叉树知识点总结

术语  1. 节点的度:一个节点含有的子树的个数称为该节点的度; 2. 叶节点或终端节点:度为零的节点;  3. 非终端节点或分支节点:度不为零的节点;  4....

334130
来自专栏机器学习从入门到成神

数据结构之树、森林和二叉树的转换

树转换为二叉树 (1)加线。在所有兄弟结点之间加一条连线。 (2)去线。树中的每个结点,只保留它与第一个孩子结点的连线,删除它与其它孩子结点之间的连线。...

19220
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题39二叉树的深度

题目:输入一颗二叉树的根结点,求该树的深度。从根结点到叶结点一次经过的结点形成树的一条路径,最长路径的长度为树的深度。 分析:本题是一道典型的“分治法”。要...

32850
来自专栏用户画像

4.5.2 平衡二叉树

为了避免树的高度增长过快,降低二叉排序树的性能,我们规定在插入和删除二叉树结点时,要保证任意结点的左、右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树...

9220
来自专栏撸码那些事

【图解数据结构】 树

15130
来自专栏Android机动车

数据结构——树、森林和二叉树的转换

森林是由若干棵树组成的,所以可以完全理解为,森林中的每一棵树都是兄弟,可以按照兄弟的处理办法来操作。步骤不如:

9620
来自专栏C/C++基础

求二叉树的深度和宽度

题目: 输入一个二叉树的根节点,求该树的深度。从根节点到叶子节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度包含的节点数为为树的深度,即二...

24120
来自专栏编程理解

数据结构(六):红黑树

级别的查询、插入和删除节点复杂度。相对于 AVL 树单纯的对每个节点的平衡因子进行判断,红黑树给节点赋予了颜色属性,并通过对树中节点的颜色进行限制,来保持整棵...

21320
来自专栏WD学习记录

哈夫曼树(Huffman Tree)

给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带...

24540

扫码关注云+社区

领取腾讯云代金券