文档介绍：严蔚敏数据构造复习完好版
严蔚敏数据构造复习完好版
1 / 55
严蔚敏数据构造复习完好版
对各种操作的时间复杂性的解析。
主若是链表，树，排序等简单一些的解析。
解析的时候，从简单
, i>=1 ；
深度为 h 的二叉树最多有 2^h-1 个结点 (h>=1) ，最稀有 h 个结点；
严蔚敏数据构造复习完好版
严蔚敏数据构造复习完好版
7 / 55
严蔚敏数据构造复习完好版
(3) 关于任意一棵二叉树，若是其叶结点数为 N0=N2+1 ；
N0，而度数为 2 的结点总数为
N2，则
严蔚敏数据构造复习完好版
严蔚敏数据构造复习完好版
55 / 55
严蔚敏数据构造复习完好版
拥有 n 个结点的的深度为
(5)有 N 个结点的各结点若是用次序方式储藏，则结点之间有以下关系：
若 I 为结点编号则 若是 I>1 ，则其父结点的编号为 I/2；
若是 2*I<=N ，则其左儿子 （即左子树的根结点） 的编号为 2*I ；若 2*I>N ，则无左儿子；
若是 2*I+1<=N ，则其右儿子的结点编号为 2*I+1 ；若 2*I+1>N ，则无右儿子。
(6)给定 N 个节点，能组成 h(N) 种不同样的二叉树。 h(N) 为的第 N 项。h(n)=C(2*n ，n)/(n+1) 。
（ 7）设有 i 个枝点， I 为全部枝点的道路长度总和， J 为叶的道路长度总和 J=I+2i
储藏构造
次序储藏表示
二叉树能够用或线性表来储藏， 而且若是这是， 这种方法不会浪费空间。 用这种紧凑排列，若是一个结点的索引为 i，它的子结点能在索引 2i+1 和 2i+2 找到，而且它的父节点 （若是有）能在索引 floor((i-1)/2) 找到（假设根节点的索引为 0）。这种方法更有利于紧凑储藏和更好的， 特别是在前序遍历中。但是， 它需要连续的， 这样在储藏高度为 h 的 n 个结点组成的一般一般树时将会浪费好多空间。 一种最极坏的状况下若是深度为 h 的二叉树每个节点只有右孩子需要占用 2 的 h 次幂减 1，而本质却只有 h 个结点，空间的浪费太大，这是次序储藏构造的一大缺点。
严蔚敏数据构造复习完好版
严蔚敏数据构造复习完好版
9 / 55
严蔚敏数据构造复习完好版
/*
二叉树的次序储藏表示
*/
严蔚敏数据构造复习完好版
严蔚敏数据构造复习完好版
55 / 55
严蔚敏数据构造复习完好版
#define MAX_TREE_SIZE 100 /*
二叉树的最大节点数
*/
严蔚敏数据构造复习完好版
严蔚敏数据构造复习完好版
55 / 55
严蔚敏数据构造复习完好版
typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0 号单元储藏根节点 */
typedef struct
{
int level,order; /* 节点的层，本层序号 ( 按满二叉树计算 ) */ }position;
二叉链表储藏表示
/* 二叉樹的二叉鏈表存儲表示 */
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild; /* 左右孩子指針 */
}BiTNode,*BiTree;
遍历算法
二叉树的遍历三种方式，以下：
（1）前序遍历（ DLR ），第一接见根结点，尔后遍历左子树，最后遍历右子树。简记根 -左-右。
（2）中序遍历（ LDR ），第一遍历左子树，尔后接见根结点，最后遍历右子树。简记左 -根-右。
（3）后序遍历（ LRD ），第一遍历左子树，尔后遍历右子树，最后接见根