数据结构树的讲解.ppt

6．4 树和森林 6.4.1树的存储结构 一、双亲表示法（顺序存储） //-----------树的双亲表存储表示----------// #define MAX_TREE_SIZE 100 typedef struct PTNode { TElemType data; int parent; //双亲位置域 }PTNode; typedef struct{ PTNode nodes[MAX_TREE_SIZE]; int n; //结点数 }PTree; 双亲表示法举例 6.4.1树的存储结构二、孩子表示法（顺序存储） #define MAX_TREE_SIZE 100 typedef struct PTNode { TElemType data; int child1; //第1个孩子位置域 int child2; //第2个孩子位置域 ...... int childd; //第d个孩子位置域 }PTNode; typedef struct{ PTNode nodes[MAX_TREE_SIZE]; int n; //结点数 }PTree; 孩子表示法举例 孩子链表存储表示（链式存储） 孩子链表存储表示举例 例1: 设树T以孩子链表为存储结构,寻找值为x的双亲结点的算法如下: 例2: 删除值为x的结点的第i棵子树的算法delete如下： 三.孩子兄弟表示法---树的二叉树表示法(二叉链表示法) //-----树的二叉链表(孩子兄弟)存储表示------ typedef struct CSNode { ELemType data; struct CSNode *firstchild,*nextsibling; }CSNode, *CSTree; 6.4.2 森林与二叉树的转换一.森林转换成二叉树 如果F={T1,T2, …,Tm}是森林,则可按如下规则转换成一棵二叉树B=(root,LB,RB)。 (1)若F为空，即m=0,则B为空树； (2)若F非空，即m0，则B的根root即为森林中第一棵树的根ROOT(T1)； B的左子树LB是从T1中根结点的子树森林F1={T11,T12, …,T1m1}转换而成的二叉树; 其右子对RB是从森林F={T2,T3, …,Tm} 转换而成的二叉树. 二. 二叉树转换成森林 如果B=(root,LB,RB)是一棵二叉树,则可按如下规则转换成森林F={T1,T2, …,Tm}： (1)若B为空，则F为空； (2)若B非空，则F中第一棵树T1的根ROOT(T1)即为二叉树B的根root； T1中的根结点的子树森林 F1是由B的左子树LB转换而成的森林; F中除T1之外其余树组成的森林F={T2,T3, …，Tm}是由B的右子树RB转换而成的森林。 6.4.3 树和森林的遍历 树的两种遍历方法： 一、先根遍历： （1）访问树的根结点； （2）依次先根遍历每棵子树。 R A D E B C F G H K 二、后根遍历： （1）依次后根遍历每棵子树。 （2）访问树的根结点； D E A B G H K F C R 森林的两种遍历方法： 一、先序遍历森林： 若森林非空，则 （1）访问森林中第一棵树的根结点； （2）先序遍历第一棵树的根结点的子树森林； （3）先序遍历除去第一棵树之后的森林。 二、中序遍历森林： 若森林非空，则 （1）中序遍历第一棵树的根结点的子树森林； （2）访问森林中第一棵树的根结点； （3）中序遍历除去第一棵树之后的森林。 6.6 赫夫曼树及其应用6.6.1最优二叉树(赫夫曼树) 路径长度: 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称做路径长度。 树的路径长度: 树的路径长度是从树根到每一结点的路径长度之和。 树的带权路径长度: 树的带权路径长度为树中所有叶子结点(k)的带权路径