数据结构chapter树和叉树.pptVIP

设计递归算法的方法 数 据 结 构 6.5 哈夫曼树及其应用 第 6 章 树和二叉树 基本概念 路径： 从一个结点到另一个结点之间的分支序列。 路径长度： 从一个结点到另一个结点所经过的分支数目。 结点的权： 树中每个结点所赋予的具有某种实际意义的实数。 带权路径长度： 从树根到某一结点的路径长度与该结点的权的乘积。 树的带权路径长度： 树中从根到所有叶子结点的各个带权路径长度之和。 记为：WPL= Wi × Li ∑ i=1 n A B C D 7 5 2 4 WPL= +5×2 +2×2 +4×2 =36 7×2 数 据 结 构 6.3 二叉树的遍历与线索化 第 6 章 树和二叉树 线索二叉树的运算： 插入 （做某结点的右孩子） F p r A B C D E A B C D E p r F ① r-RChild=p-RChild; ① ② ② p-RChild=r; ③ ③ r-LChilid=p; 可交换顺序 数 据 结 构 6.3 二叉树的遍历与线索化 第 6 章 树和二叉树 线索二叉树的运算： 插入 （做某结点的右孩子） F p r A B C D E G H r A B C D E F p G H ① s=p-RChild; while(s-Ltag==0) s=s-LChild; ①s-LChild=r; ② ②r-LChild=p; ③ ③r-RChild=p-RChild; ④ ④p-RChild=r; 数 据 结 构 6.3 二叉树的遍历与线索化 第 6 章 树和二叉树 线索二叉树的运算： 插入 （做某结点的右孩子）算法 void InsNode(BiTNode *p,BiTNode *r) { if(p-Rtag==1) { r-RChild=p-RChild; r-Rtag=1; p-RChilid=r; r-LChild=p; r-Ltag=1; } else { s=p-RChild; while(s-Ltag==0) s=s-LChild; s-LChild=r; r-LChild=p; r-Ltag=1; r-RChild=p-RChild; r-Rtag=0; p-RChild=r; } } 数 据 结 构 6.4 树、森林与二叉树的关系 第 6 章 树和二叉树 树的三种存储结构 ①双亲表示法 data parent A B C D G E F 静态链表 定义：用数组描述的链表成 为静态链表。其中链表中的 结点为数组中的一个分量， 游标(Cursor)代替指针表示 结点在数组中的相对位置。 数 据 结 构 6.4 树、森林与二叉树的关系 第 6 章 树和二叉树 树的三种存储结构 ①双亲表示法 data parent A B C D G E F parent data 结点序号 0 1 2 3 4 5 6 A -1 B 0 C 0 D 1 E 1 F 1 G 2 静态链表 数 据 结 构 6.4 树、森林与二叉树的关系 第 6 章 树和二叉树 树的三种存储结构 ①双亲表示法 存储结构 #define MAX 100 typedef struct TNode { DataType data; int parent; } TNode; typedef struct { TNode tree[MAX]; int nodenum; }ParentTree; parent data 结点序号 0 1 2 3 4 5 6 A -1 B 0 C 0 D 1 E 1 F 1 G 2 数 据 结 构 6.4 树、森林与二叉树的关系 第 6 章 树和二叉树 树的三种存储结构 ②孩子表示法 A B C D G E F 0 1 2 3 4 5 6 A B C D E F G 1 2 ∧ 3 4 5 ∧ 6 ∧ ∧ ∧ ∧ ∧ 孩子链表 数 据 结 构 6.4 树、森林与二叉树的关系 第 6 章 树和二叉树 树的三种存储结构 ②孩子表示法 存储结构 typedef struct ChildNode { int Child; struct ChildNode *next; }ChildNode; typedef struct { DataType data; ChildNode *FirstChild; }DataNode; typedef struct { Da