数据结构学习笔记:树

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

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

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

节点

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

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

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

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

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

节点定义

typedef struct TreeNode *PtrToNode;

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

树的一些概念

除了根节点之外,每一个节点都有往上的一条边。

N个节点的树有N-1条边。

除了根节点,每一个节点有且仅有一个父节点。

树的度:树中所有节点中最大的度。

路径和路径的长度:从节点\(n_1\)到\(n_k\)的序列\(n_1, n_2, …, n_k\)。路径的长度为这些节点序列的边的个数。

树的高:树的高为根的高。

树的深度:树的深度为最深叶子节点的深度。

对树进行遍历

先序遍历(preorder traversal)

对节点处理工作是在它的诸儿子节点被处理之前(pre)进行的,也叫先根遍历,遍历顺序为根->左->右。常见的应用有遍历文件目录。

后序遍历(postorder traversal)

在一个节点处的工作是在它的诸儿子节点被计算后(post)进行的,也叫后根遍历,遍历顺序为左->右->根。常见的应用是目录中所有文件大小总和。

中序遍历

也叫中根遍历,遍历顺序为左->根->右。

二叉树

binary tree,每个节点都不能有多于两个儿子。

typedef struct TreeNode *PtrToNode;
typedef struct PtrToNode Tree;

struct
{
    ElementType Element;
    Tree Left;
    Tree Right;
}

表达式树

表达式树的树叶是操作数,其他节点为操作符。

二叉查找树

使得一颗二叉树成为二叉查找树的性质是,对于树中的每个节点X,它的左子树中所有的关键字值小于X的关键字值,而它的右子树中所有的关键字值大于X的关键字值。

红黑树

一种二叉查找树,在每一个节点中,除了含有Left,Right,Element信息之外,还有一个Color字段表示颜色信息,有红和黑两种,故称之为红黑树。

AVL 树(Adelson- Velskii 和 Landis)

AVL树是带有平衡条件的二叉查找树,一颗AVL树是其每一个节点的左子树和右子数的高度最多相差1的二叉查找树。

图为一颗AVL树

B-树

一种常用的查找树,阶为M的B-树有如下特性

1.树的跟或者一片树叶,或者其儿子数在2和M之间

2.除根外,所有的非树叶节点都在ceil(M/2)和M之间.

3.所有的树叶都在相同的深度上

当我们直接说堆这个词的时候,一般指的都是二叉堆,是一颗完全二叉树。

大顶堆,所有的父节点大于或者等于它的孩子节点,同样有一种被称为小顶堆的堆,它的所有的父节点都要小于或者登陆它的孩子节点。

一个堆可以用简单一维数组来实现

 

赞赏

微信赞赏支付宝赞赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注