树和二叉树
1) 了解树的定义和基本术语：
树的定义：树是N个节点的有限集，在任意一棵非空树中：1、有且
2)了解二叉树的定义、性质
2) 掌握二叉树的顺序存储结构和二叉树的链式存储结构
二叉树的顺序存储结构：使用顺序表(数组）存储二叉树。只有完全二叉树才可以使用顺序存储（普通二叉树会浪费空间）。存储方式：仅需从根节点开始，按照层次依次将树中节点存储到数组即可。遍历是使用层次遍历。
二叉树的链式存储结构： 第一种：二叉链表 typedef struct BitNode{
int data;//数据域
struct BitNode *Tchild ,*Rchild; }BitNode,*Bitree;
第二种：三叉链表：便于找到节点的双亲，增加一个指向其双亲节点的指针域，则在非递归的遍历过程中就不需在另设栈。 typedef struct BitNode{ int data;//数据域
struct BitNode *Tchild ,*Rchild,*parent; }BitNode,*Bitree;
3) 掌握二叉树的先序遍历、中序遍历、后序遍历和层次遍历过程 二叉树的先序遍历：
遍历思想：1）访问跟节点 2）访问当前节点的左子树
3）若当前节点无左子树，则访问当前节点的右子树。 例过程：
1、访问该二叉树的根节点，找到1； 2、访问节点1的左子树，找到2；
1 2 4 5 6 3 7 3、访问节点2的左子树，找到4； 4、由于访问节点4左子树失败，且也没有右子树，因此以节点4为根节点的子树遍历完成。但节点2还没有遍历其右子树，因此现在开始遍历，即访问节点5；
5、由于节点5无左右子树，因此节点5遍历完成，并且由此以节点2的子树也遍历完成。现在回到节点1，并开始遍历该节点的右子树，即访问节点5； 6、访问节点3左子树，找到节点6；
7、由于节点6无左右子树，因此节点6遍历完成，回到节点3并遍历其右子树，找到节点7；
8、节点7无左右子树，因此以节点3为根节点的子树遍历完成，同时回归节点1，由于节点1的左右子树全部遍历完成；
递归遍历：
void pre_order(Bitree T){ if(T){
printf(\ pre_order(T->L); pre_order(T->R); } }
非递归遍历：对于任一节点p
思想：1)访问节点p，并将节点p入栈；
2）判断节点p的左孩子是否为空，若为空，则取栈顶节点并进行出栈操作，并将栈顶节点的右孩子置为当前的节点p，循环至1）步骤；若不为空，则将p的左孩子置为当前的节点p，
3）直到p为null并且栈为空，则遍历结束。
二叉树的层次遍历：
思想：通过使用队列的数据结构，从数的根节点开始，依次将其左孩子和右孩子入队，而后每次队列中一个节点出队，都将其左孩子和右孩子入队，直到树中所有节点都出队，出队节点的先后顺序就是层次遍历的最终结果。 1 过程：1）首先，根节点1入队；
2）根节点1出队，出队的同时，将左孩子2和右孩子3分别入队； 2 3 3）对头节点2出队，出队的同时，将节点2的左孩子4和右孩子5 依次入队；
4 6 5 4）队头节点3出队，出队的同时，将节点3的左孩子6和右孩子
7依次入队
5）不断循环，直至队列内为空。
4) 了解线索二叉树的概念、线索二叉树的构造和遍历过程
线索二叉树概念：对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍
历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。
7 注意：线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了二叉链表找左、右孩子困难的问题
线索二叉树的构造：为方便起见，我们可以在线索链表上添加一个头结点 typedef enum PointerTag{ Link,thread; }
typedef struct BiThrNode{ int data;
struct BiThrNode *Tchild ,*Rchild; PointerTag LTag,RTag; }BiThrNode,*BitThrTree;
遍历过程：
中序遍历非递归算法（T指向头结点，头结点的左链lchild指向根节点）： void InOrder(BitThrTree T){
p = T->Lchild;//P指向根节点
/** 空树或遍历结束时，p==T **/ while(p != T){
while(p->data == Link) p = p->Lchild;
if(!p->data)//访问其左子树为空的节点的情况 return error; /**
访问后继节点 **/
while(p->RTag == thread && p->Rchild != T){ p = p->rchild;
prinf(\->data); }
p = p->rchild; } }
二叉树的线索化：
5) 掌握树的双亲表示法、孩子表示法和孩子兄弟表示法以及特点 双亲表示法：
特点： 表示法:
#define MAX_TREE_SIZE 100 //节点结构
typedef struct PTNode{ int data;
int parent;//双亲位置域 }PTNode; //数结构
typedef struct{
PTNode node[MAX_TREE_SIZE]; int r,n; }PTree;
孩子表示法：
typedef struct CTNode{ int child;
struct CTNode *next; }*ChildPtr;
typedef struct{ int data;
ChildPtr firstchild; }CTBox;
typedef struct{
CTBox nodes[MAX_TREE_SIZE]; int n,r;//节点数和根的位置 }CTree;
孩子兄弟表示法： 特点：
typedef struct CSNode{ int data;
struct CSNode *firstchild,*nextchild; }CSNode,*CSTree;
6) 了解森林、树转换为二叉树以及二叉树还原为森林、树的过程
森林转换为二叉树：
如果F={T1,T2,T3,T4,T5....Tm}是森林，则可按如下规则转换成一棵二叉树B=(root,LB,RB). 1) 若F为空，即m=0,则B为空树;
2) 若F非空，即m！=0，则B的根root即为森林中第一颗树的根root(T1）；B的左子树LB是从T1中根节点的子树森林F1={T11,T12,T13,T14.....T1m1}转换而成的二叉树，其右子树RB是从森林F’={T2,T3,T4.....Tm}转换而成的二叉树。 二叉树转换为森林:
如果B=(root,LB,RB)是一颗二叉树.则可按如下规则转换成F={T1,T2,T3,T4,T5....Tm}森林， 1) 若F为空，即m=0,则B为空树;
2) 若F非空，即m！=0，则B的根root即为森林中第一颗树的根root(T1）；B的左子树LB是从T1中根节点的子树森林F1={T11,T12,T13,T14.....T1m1}转换而成的二叉树，其右子树RB是从森林F’={T2,T3,T4.....Tm}转换而成的二叉树。 7) 掌握树的先根遍历和后根遍历过程
8)掌握森林的先序遍历和中序遍历过程
10) 掌握赫夫曼树的概念、构造赫夫曼树和产生赫夫曼编码的过程
概念：赫夫曼数又称最优（二叉）树，是一类带权路径长度最小的树 构造赫夫曼数（俗称赫夫曼算法）：
1）根据给定的n个权值{w1,w2,w3,w4....Wn}构成n棵二叉树的集合F={T1,T2,T3....Tn},其中每棵二叉树Ti中只有一个带权为Wi的根节点，其左右子树均为空。
2）在F中选取两棵根节点的权值最小的数作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左、右子树上根节点的权值之和。 3）在F中删除这两棵树，同时将新得到的二叉树加入F中。
4）重复2）和3），直到F只包含一棵树为止。这棵树便是赫夫曼数
相关推荐：
loading