树形结构思维导图

typedef struct PTNode{ TElemType data; int parent; }PTNode; typedef struct{ PTNode nodes[MAX_TREE_SIZE]; int r,n; //根的位置和结点数 }PTree;

定义逻辑：用一组连续的存储空间存储树的结点，同时在每个结点中，用一个变量存储该结点双亲结点的位置

typedef struct CTNode{ //孩子结点 int child; struct CTNode *next; }*ChildPtr; typedef struct{ //表头结点 TElemType data; ChildPtr firstchild; //孩子链表头结点 }CTBox; typedef struct{ CTBox nodes[MAX_TREE_SIZE]; int n,r; //结点数和根的位置 }CTree;

孩子链表：把每个节点的孩子排列在一条单链表中，所有n个表头指针组成一个线性表

typedef struct CSNode{ ElemType data; struct CSNode *firstchild,*nextsibling; //指向第一个孩子结点和下一个兄弟结点 }CSNode,*CSTree;

孩子兄弟：两个链表域、一个链接孩子结点，一个链接下一个兄弟结点

用一个数组来存储一颗二叉树，一般适用于完全二叉树：用一组连续的存储单元自上而下、自左而右存储各个结点的元素。

二叉链表或三叉链表实现

性质：如果含有n个结点的二叉链表中，右n+1个空指针域

递归的思路：每一个子树都是一个以叶子为根结点的二叉树

中序遍历

先序遍历

后序遍历

用空指针来存放当前结点的直接前驱和后继等线索，加快查找速度

线索：指向前驱或后继点的指针

线索二叉树：加上线索的二叉树

线索化：对二叉树按某种遍历的次序使其变为线索二叉树

结构体定义

中序遍历线索化过程

在权为w1、w2......wn的n个子叶的所有二叉树中，带权路径长度WPL最小的二叉树，称为哈夫曼树或者最优二叉树

根据给定的n个权值{w ,w ,...,w }构成二叉树集合F={T1,T2,...,Tn }, 其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树为空

在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二 叉树,且置新的二叉树的根结点的权值为左右子树根结点的权值之和。

在F中删除这两棵树,同时将新的二叉树加入F中。

重复2、3,直到F只含有一棵树为止，便是赫夫曼树。

包含n个子叶结点的哈夫曼树中，共有2n--1个结点

在哈夫曼树中结点度数为0或者2，没有度数为1的结点

typedef struct { int weight; //结点的权值 int parent; //双亲的下标 int LChild; //左孩子结点的下标 int RChild; //右孩子结点的下标 }HTNode, *HuffmanTree;

初始化

创建哈夫曼树