树
树是一种层次关系，在日常生活非常常见，比如社会关系，亲缘关系，文件管理。
一棵树是一些节点的集合，这个集合可以是空集，若非空，则一棵树由称作为根的节点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
赞赏
微信赞赏
支付宝赞赏
