数据结构学习笔记:树

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

节点

没有儿子的节点称为叶子(leaf)

节点的深度

根到一个节点的唯一路径长,根的深度为0

节点的高

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

节点定义

typedef struct TreeNode *PtrToNode;

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

对树进行遍历

先序遍历(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的关键字值。

AVL 树(Adelson- Velskii 和 Landis)

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

图为一颗AVL树

B-树

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

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

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

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

赞赏

微信赞赏支付宝赞赏

发表评论

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