数据结构学习笔记:树

树是一种层次关系,在日常生活非常常见,比如社会关系,亲缘关系,文件管理。

一棵树是一些节点的集合,这个集合可以是空集,若非空,则一棵树由称作为根的节点r以及0个或者多个非空的(子)树组成,这些子树中的每一棵都是被来自根r的一条有向的边所连接。

一种数据结构需要包含一些操作,树这种数据结构有增加,删除,查找,修改。

节点

节点的度:节点子树的个数。

叶子节点:没有儿子的节点,也就是度为0的节点。

节点的层次:规定跟节点在1层,其他节点的层次为父节点的层次加1。

节点的高:节点的高为从这个节点到叶子的最长路径,所有树叶的高都是0。

节点的深度:从跟节点到该节点的唯一路径长,根的深度为0。

节点定义

typedef struct TreeNode *PtrToNode;

struct TreeNode
{
    ElementType Element;
    PtrToNode FitstChild;
    PtrNode NextSibling;
}

(更多…)