一、用思维导图串接知识点
二、概念阐述
1.树
a.树的基本概念
树的基本知识：
讲解树的有关节点
1.根：最上方的结点；叶子：没有子结点的结点；只有一个结点的树，该结点既是根又是叶子。
2.树的结点数为n，则去掉根结点后有n-1个子结点，即n-1条边；
3.若此树的度为k，则具有kn个指针，其中n-1个已用，剩余(k-1)n+1个空指针；
4.因n个结点的树最多有n-1个结点，即n-1条边，因此n结点m条边的图要转为树，至少需要砍去m-n+1条边
5.树的度为k，ni代表度为i的结点的数量，则 n0+n1+…+nk = 1+n1+2n2+3n3+…knk
b.树的逻辑表示方法
有文氏图表示法、凹入表示法、括号表示法
以及将重点介绍的树形表示方法
其特征为：
①每个节点有零个或多个子节点；
②没有父节点的节点称为根节点；
③每一个非根节点有且只有一个父节点；
④除了根节点外，每个子节点可以分为多个不相交的子树；
c.树的基本运算
建立树的定义
typedef char ElemType; typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;
（其完整的树的运算实现参照二叉树中的各功能的实现）
2.二叉树
二叉树的的定义及逻辑表示方法
二叉树
每一个结点下都有左右之分的树结构，没一个结点下最多两个子结点，最少没有
完全二叉树：
所有子结点都在左侧
满二叉树：
终端结点（叶结点）都在最底层，并且每个父结点下都有两个子结点
c.二叉树的基本运算及其实现
二叉树节点的插入
void InsertBST(BSTree* &t,int key) { BSTree *p,*parent,*head; p = new BSTree; p->data = key; p->lchild = p->rchild = NULL; head = t; while(head) { parent = head; if(key < head->data) head = head->lchild; else head = head->rchild; } if(key < parent->data) parent->lchild = p; else parent->rchild = p; }
创建一个二叉树
void createBST(BSTree *t) { cout<<"输入树的节点个数： "; int n; int data[Maxsize]; cin>>n; for(int a=0;a<n;a++) { cin>>data[a]; } int i; t->data = data[0]; t->lchild = t->rchild = NULL; for(i=1;i<n;i++) InsertBST(t,data[i]); }
二叉树的输出详见下文二叉树的遍历实现
二叉树的查找删除实现详见下文查找内容
d.二叉树的遍历（重点）
先序遍历
void PreOrder(BiTree t) { if(t) { cout<<t->data; PreOrder(t->lchild); PreOrder(t->rchild); } }
中序遍历
（其特征为可以实现节点的如从小到大的输出顺序）
void InOrder(BiTree t) { if(t) { InOrder(t->lchild); cout<<t->data; InOrder(t->rchild); } }
后序遍历
void PostOrder(BiTree t) { if(t) { PostOrder(t->lchild); PostOrder(t->rchild); cout<<t->data; } }
3.二叉树–进阶
a.线索二叉树
如图中所示：
虚线为线索指针，实线为指向真实子女。因为A的ltag和rtag标志位都为0，所以A有左右子节点，left和right指向它的真实子女；B节点和A节点类似；D节点的两个标志位都为1，所以其left和right要指向它的前驱和后继，但是D在中序序列中是第一个，没有前驱所以left为NULL，right指向B；E节点的ltag=0，所以指向子节点；rtag=1，所以指向后继
以此类推
/* 二叉树的二叉线索存储结构定义*/ typedef enum{Link, Thread}PointerTag; //Link = 0表示指向左右孩子指针；Thread = 1表示指向前驱或后继的线索 typedef struct BitNode { char data; //结点数据 struct BitNode *lchild, *rchild; //左右孩子指针 PointerTag Ltag; //左右标志 PointerTag rtal; }BitNode, *BiTree;
b.哈夫曼树
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。构造哈夫曼树时，首先将由n个字符形成的n个叶子结点存放到数组HuffNode的前n个分量中，然后根据哈夫曼方法的基本思想，不断将两个较小的子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffNode数组中的前n个分量的后面。
通俗的来讲，哈弗曼树就是一种广泛应用的二叉树，哈弗曼树可以用来构造最优编码，用于信息的传输，压缩等方面
哈弗曼树也可以理解为，最小二叉树，最优二叉树。
三、查找（难点）
a.线性表的查找
主要有顺序查找，折半查找，内容较为简单，详见《第五版数据结构教程》9.2的有关内容。下面重点介绍下文树表查找的有关内容。
b.树表的查找
简明概念阐述
二叉树的树形结构使它很适合扮演索引的角色：二叉查找树（binary search tree），这种二叉树的主要作用就是进行查找操作；二叉查找树在二叉树的基础上增加了以下几个条件：
(1)、如果左子树不为空，则左子树上所有节点的值均小于根节点的值
(2)、如果右子树不为空，则右子树上所有节点的值均大于根节点的值
(3)、左、右子树也都是二叉查找树
【具体步骤表示如下】：
下图就是一个标准的二叉查找树：
例如查找值为4的节点，步骤如下：
1、访问根节点6，发现4<6；
2、访问节点6的左孩子节点3，发现4>3；
3、访问节点3的右孩子节点4，发现4=4，这正是要查找的节点
对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，那么搜索节点的时间复杂度就是O(logn)，和树的深度是一样的。
【具体可用递归算法实现查找节点元素】
BSTree *SearchBST(BSTree *t,int key) { if(!t || t->data == key) return t; else if(key >t->data) return (SearchBST(t->rchild,key)); else return (SearchBST(t->lchild,key)); }
【二叉排序树】
【补充B树】
定义：
B树是一种平衡多叉树，主要用于查询。m阶B树（每个结点下最多有m个子结点）满足如下条件：
根结点至少有两个子女，每个根结点所包含的关键字个数j满足：（m/2）-1 < j < m-1； 除根结点外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，古内部子树个数k满足：（m/2）<= k <= m； 所有的叶子结点都位于同一层。
B树的性质
所有叶子结点到根结点的路径长度相同，即具有相同的高度； 每个非叶子和非根结点（即内部结点）至少有m-1个孩子结点；根至少2个孩子； 每个结点最多有2m个孩子节点。 每个结点内的键都是递增的， 每个结点的孩子比key的个数多1
B树的使用方法
查找数据时，将所有的非根结点中的关键字取出，然后找寻是否存在符合范围的根结点，再进行一一对比。
B+树
定义：B+树是B树的改善结构，在满足B树的要求下，还满足如下要求：
有K个子树的中间结点包含K个元素（B树种是K-1个元素），每个元素不保存数据，只用来索引，所有的数据都存在在叶子结点； 所有的叶子结点种包含了全部的元素的信息，及指向含有这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接； 所有的中间节点元素都同时存在于子节点，在子结点中是最大（或最小）元素 对比B树的优势：查找迅速，存储结构简单，查询稳定；
疑难问题及解决方案
（PTA习题讲演）
判断一棵树是否是完全二叉树的思路：
1、如果树为空，则直接返回错。
2、如果树不为空：层序遍历二叉树。
3、如果一个结点左右孩子都不为空，将其左右孩子入队列；
4、如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；
5、如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后 的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树；
简单来说就是，子节点都是要求左往右走的，当遇到一个度小于2的结点，则后面的一定要全为叶子。
（具体代码实现较为复杂，记得思路即可）
