【数据结构】什么是树?

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境:Visual Studio 2022

📌树的定义

📌树的相关概念

📌线性结构与树结构的对比

📌树的抽象数据类型

📌树的存储结构

🎏双亲表示法

🎏孩子表示法

🎏孩子兄弟表示法

结语

📌树的定义

树(Tree)是n(n≥0)个结点的有限集.n=0时称为空树.

在任意一颗非空树中:

有且仅有一个特定的称为根(Root)的结点;
当n>1时,其余结点可分为m(m>0)个互不相交的有限集 $T_{1},T_{2},......,T_{m}$ ,其中每一个集合本身又是一颗树,并且称为根的子树(SubTree),如下图:

有关树的定义我们还需强调两点:

n>0时根节点是唯一的,不可能存在多个根节点.
m>0时,子树的个数没有限制,但它们一定是互不相交的.下图的两个结构就不符合树的定义,因为它们都有相交的子树:

📌树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6.
叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I、K、L、...等节点为叶节点.
非终端节点或分支节点：度不为0的节点；如上图：D、E、F、G、J等节点为分支节点.
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点.
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点.
兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点.
树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6.
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；如上图：树的高度为4.
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点.
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先.
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙.
森林:由m(m>0)棵互不相交的树的集合称为森林.

📌线性结构与树结构的对比

线性结构

第一个数据元素:无前驱
最后一个数据元素:无后继
中间元素:一个前驱一个后继

树结构

根节点:无双亲且唯一
叶节点:无孩子,可以存在多个
中间节点:一个双亲多个孩子

📌树的抽象数据类型

这里我们给出了一些树的基本常用操作:

ADT 树(tree)
Data
    树是由一个根结点和若干棵子树构成。树中结点具有相同数据类型及层次关系。
Operation
    InitTree(*T):构造空树T。
    DestroyTree(*T):销毁树T。
    CreateTree(*T,definition):按definition中给出树的定义来构造树。
    ClearTree(*T):若树T存在,则将树T清为空树。
    TreeEmpty(*T):若树T为空树,返回true,否则返回false。
    TreeDepth(*T):返回树T的深度。
    Root(T):返回T的根结点。
    Value(T,cur_e):cur_e是树T中一个结点,返回此结点的值。
    Assign(T,cur_e,value):给树T的结点cur_e赋值为value。
    Parent(T,cur_e):若cur_e是树T中的非根结点,则返回它的双亲,否则返回空。
    LeftChild(T,cur_e):若cur_e是树T的非叶结点,则返回它的最左孩子,否则返回空。
    RightSibling(T,cur_e):若cur_e有右兄弟,则返回它的右兄弟,否则返回空。
    InsertChild(*T,*p,i,c):其中p指向树T的某个结点,i为所指结点p的度加上1,
               非空树c与T不相交,操作结果为插入c为树T中p指结点的第i棵子树。
    DeleteChild(*T,*p,i): 其中p指向树T的某个结点, i为所指结点p的度,操作
                结果为删除T中p所指结点的第i棵子树。
endADT