树

ADT

Note

ADT 树(tree) Data

tree是一种n(n >= 0)个节点的有限集。当n = 0时成为空树,在任意一颗非空树中

• 有且仅有一个特定称为**根(root)**的节点
• 当n > 1时,其节点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一个集合本身又是一棵树,并成为跟的子树(Subtree)

Operation

endADT

注意:

• n > 0时，根节点唯一，不可能存在多个节点。
• m > 0时，子树个数没有限制，但它们一定互不相交

节点的分类

• 节点拥有的子树称为结点的度(Degree)，树的度取树内各节点的度的最大值。
• 度为零的节点称为**叶结点(Leaf)**或终端节点
• 度不为零的节点称为分支节点或非终端节点，除根结点外，分支节点也称为内部节点。

节点间的关系

• 节点的子树的根称为节点的孩子(Child),相应的,该节点称为孩子的双亲(Parent),同一双亲的孩子之间互称兄弟(Sibling)。
• 节点祖先(ancestor)\是从跟到该节点所经分支上的所有节点
• 双亲不同但祖父母相同的节点称为堂兄弟(cousin)

结点的层次

• 结点的层次(Level)\从根开始定一起,根为第一层,跟的孩子为第二层。
• 树结点最大层次称树深度(Depth)\或高度(但高度定义是从根节点出发到最远节点长度)

其他概念

• 如果将树中节点的各子树看成从左至右有次序不能替换,则该树称为有序树,否则称为无序树
• 森林(Forest)\是m(m>0)棵互不相交的树的集合。对树中每个节点而言,其子树的集合即为森林。

树图解

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

D

B

A

C

E

2度

叶结点

根节点

内部节点

2度

0度

指向原始笔记的链接

树的优势

• 存储天然为层次化的数据
• 组织数据快速删改查O(logn)

树的各种类型

二叉树 AVL树 堆

具体实现

---

树体

• 双亲表示法

#define MAX_TREE_SIZE 100
 
typedef int ElemType;
 
typedef struct PTNode
{
    ElemType data; //节点数据
    int parent; //双亲位
}PTNode;
 
typedef struct
{
    PTNode nodes[MAX_TREE_SIZE];
    int r; //根位置
    int n; //节点数目
}PTree;

• 孩子表示法 略，看结合表示法

• 双亲孩子结合表示法

#define MAX_TREE_SIZE 100
 
typedef int ElemType;
 
//孩子节点
typedef struct CTNode
{
    int child; //孩子位
    struct CTNode *next; //指向下一个孩子节点的指针
}*ChildPtr;
 
//表头结构
typedef struct
{
    ElemType data; //节点数据
    int parent;
    ChildPtr firstchild;
}CTBox;
 
typedef struct
{
    CTBox nodes[MAX_TREE_SIZE];
    int r; //根位置
    int n; //节点数目
}CPTree;