(第5章 树和二叉树--jy.ppt

Non-recursive Algorithms 5.4 线索二叉树（Threaded Binary Tree） 2.遍历线索二叉树 5.6 赫夫曼树与赫夫曼编码 最优二叉树 赫夫曼树 的定义 构造最优二叉树的算法 赫夫曼编码 前缀编码 bool Preorder BiTree T, ElemType x, BiTree p //若二叉树中存在和x相同的元素，则p指向该结点并返回TRUE, // 否则 p NULL 且返回 FALSE if T if T- data x p T; return TRUE; //if else p NULL; return FALSE; else if Preorder T- lchild, x, p return TRUE; //else else return Preorder T- rchild, x, p ; 5、复制二叉树 其基本操作为:生成一个结点。 根元素 T 左子树 右子树 根元素 NEWT 左子树 右子树 左子树 右子树 后序遍历 BiTNode *GetTreeNode TElemType item, BiTNode *lptr , BiTNode *rptr if ! T new BiTNode exit 1 ; T- data item; T- lchild lptr; T- rchild rptr; return T; 生成一个二叉树的结点 其数据域为item,左指针域为lptr,右指针域为rptr BiTNode *CopyTree BiTNode *T if !T return NULL; if T- lchild newlptr CopyTree T- lchild ; //复制左子树 else newlptr NULL; if T- rchild newrptr CopyTree T- rchild ; //复制右子树 else newrptr NULL; newT GetTreeNode T- data, newlptr, newrptr ; return newT; // CopyTree A B C D E F G H K ^ D ^ C ^ ^ H ^ ^ K ^ G A 例如:下列二叉树的复制过程如下: newT F ^ ^ B E ^ 按给定的表达式建相应二叉树 表达式 操作数1 运算符 操作数2 运算符 操作数1 操作数2 例如，表示表达式 a+b ?c-d/e 的二叉树 a b c d e - × + / 特点： 操作数为叶子结点， 运算符为分支结点 先缀表示式： -×+ a b c / d e 后缀表示式： a b+ c× d e / - a+b a+b ×c –d/e a+b×c 分析表达式和二叉树的关系: a b b a × c + a b c a+b ×c / d e a b c × + + + × - a b + a b c ? + a b + c ? a b + c ? d e / - 仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树， 由二叉树的先序和中序序列建树 如果同时已知二叉树的中序序列“cbdaegf”,则会如何？ 二叉树的先序序列 二叉树的中序序列 左子树 左子树 右子树 右子树 根 根 a b c d e f g c b d a e g f 例如: a a b b c c d d e e f f g g a b c d e f g ^ ^ ^ ^ ^ ^ ^ ^ 先序序列中序序列 线索二叉树结点格式: Represented in c: typedef struct node int ltag,rtag; datatype data; struct node *lchild, *rchild; bithptr; lchild ltag data rtag rchild D G A B C E F a A binary tree 0 A 0 B 1 D E 1 F G C b A threaded binary tree 0 0 1 1 1 0 0 1 1 1 在中序线索二叉树中，查找结点*p的中序后继结点 bithptr *INORDERNEXT bithptr *p bithptr *q; if p- rtag 1 return p- rchild ; else q p- rchild; while q- ltag