树
树是一种层次关系,在日常生活非常常见,比如社会关系,亲缘关系,文件管理。
一棵树是一些节点的集合,这个集合可以是空集,若非空,则一棵树由称作为根的节点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.所有的树叶都在相同的深度上
堆
当我们直接说堆这个词的时候,一般指的都是二叉堆,是一颗完全二叉树。
大顶堆,所有的父节点大于或者等于它的孩子节点,同样有一种被称为小顶堆的堆,它的所有的父节点都要小于或者登陆它的孩子节点。
一个堆可以用简单一维数组来实现
你可能还喜欢下面这些文章
根据如何学习一门新的语言这篇文章的指导,现在的步骤就是学习这门语言的流程控制了。通常来讲,流程控制有顺序,选择,循环这几种。python也不例外,也有这三种流程控制。下面的一一学习。顺序顺序语句很简单,从上往下依次顺序执行。如:a = 1b = 2print(a+b)上面的语句就是顺序执行的语句。选择选择通常使用if和switch,但python中只有if这一个选择语句。语法是:if 满足条件1: 语句1elif 不满足条件1满足1条件2 语句2else 都不满足 语句3比如用一个实际的例子a = 1b = 2if a > b: print(‘a>b’)el
赞赏微信赞赏
支付宝赞赏