树的定义、表示和二叉树及存储结构

1 前言

       最近又看了一遍浙大的数据结构视频课程《浙江大学数据结构慕课》，感觉讲得很不错。为方便以后复习及查阅，现把树的定义、表示和二叉树及存储结构的这两节的内容以图片的形式摘录至此。

2 树的定义及树的表示

2.1 树的定义

2.3 树的表示

       由于树中的每个结点的度不统一，所以显然，首先我们想到的是结构体加链表的形式对其进行表示。

       我们知道，当一棵树具有n个节点时，它具有n-1条边，而上述的表示方式则需要3n（因为树的度为3）个存储单元来存放树的边。这样一样，2n＋1个存储单元就被浪费了。因此为了减少上述浪费，实际编码时我们一般采用儿子-兄弟的表示方法：树的结构体中包含：一个存放结点元素的单元，一个指向第一个儿子的指针和一个指向第一个兄弟的指针。这样一来，我们表示一颗树，则只需要2n个存储单元来存储树的边，仅仅浪费n+1个存储单元。

       当我们把上述树进行旋转45度时，发现这就是一颗二叉树了，因此大部分的树都可以转化为二叉树的形式进行表示。综上所述，树的算法大多围绕二叉树进行。

3 二叉树及存储结构

3.1 二叉树的定义

3.2 特殊二叉树

3.3 二叉树的重要性质

3.4 二叉树的抽象数据类型

3.5 二叉树的存储结构

4 参考资料

[1] 浙江大学数据结构慕课

[2]树与树的表示