乐趣区

数据结构树基本术语

数据结构—树和二叉树

定义:树是 n (n≥0) 个结点的有限集。在一棵非空树中,有且 仅有唯一的根(root)结点 ,当 n>1 时,除根结点外其余结点可分为 m (m>0) 个互不相交的有限集 ,它们本身也是一棵树,称为根的 子树(subtree)

  • 树的一些基本术语:

树的结点:使用树结构存储的每一个数据元素都被称为“结点”。例如,A 中,数据元素 A 就是一个结点

结点的度(degree):结点所拥有的子树的数目。

叶子结点(leaf– 又称终端结点 terminal node 结点的度为 0 的结点。例如结点 K、L、F、G、M、I、J

分支结点(branch node) 结点的度不为 0 的结点。

孩子(child– 也称儿子 son) 结点的子树的根称为结点的孩子。例如 B,C,D 是 A 的孩子 (先找子树,再找子树的根)

兄弟(sibling) 同一父母的所有孩子互称兄弟。例如 B、C、D 来说,它们都有相同的双亲结点,所以它们互为兄弟结点。

双亲(parent) 结点是其孩子的双亲。例如 A 为 B,C,D 双亲

祖先(forefather) 从树根到双亲的所有结点称为该结点的祖先。

子孙(progeny) 以结点为根的子树的所有结点称为该结点的子孙。

层次 (level) 树根为第一层,其孩子为第二层,孙子为第三层,以此类推。

堂兄弟(cousin) 双亲在同一层的结点互称堂兄弟。

深度(depth) 树中结点最大的层次

有序树(ordered tree)&& 无序树(unordered tree)

森林

退出移动版