haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

树应用一(排序二叉树)

发布时间:2014-02-03 11:04:36  

已知一棵度为m的树中有n1个度为1的结点,n2 个度为2的结点,……,nm个度为m的结点, 问树中有多少个叶子结点? 总结点数=所有结点的总度数+1 =(n1*1+n2*2+n3*3+…+nm*m)+1 叶子结点=总结点数-(n1+n2+n3+…+nm) 如:度为4的树中有2个度为1的点,2个度为2 的点,1个度为4的点,问共有多少个结点?有 多少个叶子结点?

二叉排序树
授课人: 高建君

一、定义
二叉排序树(Binary Sort Tree):又称二叉 查找(搜索)树(Binary Search Tree)。 其定义为:二叉排序树或者是空树,或者是 满足如下性质的非空二叉树: ①若它的左子树非空,则左子树上所有结点的 值均小于根结点的值; ②若它的右子树非空,则 右子树上所有结点的值均大 于根结点的值; ③左、右子树本身又各是 一棵二叉排序树。 上述性质简称二叉排序树性质(BST性质),故 二叉排序树实际上是满足BST性质的二叉树。

二叉排序树的特点:由BST性质可得 ①二叉排序树中任一结点x,其左(右)子树中 任一结点y(若存在)的关键字必小(大)于x的关键 字。 ②二叉排序树中,各结点关键字是唯一的。

注意:
实际应用中,可将二叉排序树定义中BST性 质①里的“小于”改为“小于等于”,或将BST 性质②里的“大于”改为“大于等于”,甚至 可同时修改这两个性质。 ③按中序遍历该树所得到的中序序列是一个 递增有序序列。

中序序列: 2,3,4,5,7,8

二、二叉排序树的查找算法
(1)输入待查找的关键字K (2)若树不为空,则若给定K值等于根结点,查 找成功,返回根结点的指针 (3)若给定值小于根结点,则在根结点左子树 继续查找 (4)若给定值大于根结点,则在根结点右子树 继续查找 (5) 重复以上(2)(3)(4)操作,直到找到或为空结 束。 算法如下:

type point =^node ; node=record

da : datatype ;
left , right : point ; end;

function search ( bst:point; k:datatype) : point ; begin if bst= nil then begin search :=nil ; exit ; end else begin if k=bst^.da then begin search :=bst; exit; end{递归终结条件} if k< bst^.da then search := search(bst^.left,k); {在左子树中查找} if k>bst^.da then search:= search(bst^.right,k); {在右子树中查找} end; end;

若查找成功,则是从根结点出发走了一条 从根到待查结点的路径。 若查找不成功,则是从根结点出发走了一 条从根到某个叶结点的路径。 与二分查找类似,和关键字比较的次数不 超过树的深度。

二叉排序树查找成功的平均查找长度: 在等概率假设下,(a)图平均查找长度为:

在等概率假设下,(b)图平均查找长度为: ASLb=(1+2+3+4+5+6+7+8+9+10)/10=5.5

三、二叉排序树的插入和生成 1、 二叉排序树插入算法:
(1) 设插入一个结点s,若原树为空,

则s结点为根结点; (2)若二叉排序树不为空,则将待插的结点值和根结点 的值比较: (i)若二者相等,则说明树中已有此值,无须插入。 (ii)若s^.da<bst^.da,则将其插入根的左子树中。 (iii)若s^.da>bst^.da,则将其插入根的右子树中。

请写出插入过程的算法

递归算法: Procedure insert(var bst:point;s: point ) ; begin if bst=nil then bst:= s else if s^.da<bst^.da then insert( bst^.left, s ) else; insert( bst^.right , s) end ;

非递归算法: procedure insert2(var bst:point;s: point ) ; begin p:=bst ; q:=nil ; while p<> nil do {查找插入位置} begin if s^.da<p^.da then {在左子树中查找} begin q:=p ; p:=p^.left ; end else begin q:=p ;p:=p^.right ; end{在右子树中查找} end; if bst=nil then bst:=s {新插的结点作为根} else if s^.da< q^.da then q^.left :=s q^.right:=s ; else
{树非空时将新结点作为q的左孩子或右孩子插入}

end ;

2、二叉排序树的生成
从空的二叉排序树开始,每输入一个结点 数据,就调用一次插入算法将它插入到当前已 生成的二叉排序树中。 输入序列决定了二叉排序树的形态。

假定待建立二叉树的一组元素是: 23 11 45 3 50 67 32

画一画:
已知一组元素为 46,25,78,62,12,37,70,29,画出按 元素排列顺序输入生成的一棵二叉排 序树。

procedure creat (var bst:point;n:integer) ; begin bst:=nil ; {初始化} for k:=1 to n do begin read( x) ; {读入一个结点值} new(s) ; s^.da:=x ; s^.left:= nil; s^.right := nil ; insert( bst, s) ; {调用插入新结点的过程} end end ;

3、二叉排序树的删除运算
⑴删除一个结点(如P)有三种可能

a.p是叶子结点(它的孩子数为0) 将p的双亲指向p的指针域置空即可。 b. p只有一个孩子child(共有4种状态 ,哪4种) 将child和p的双亲直接链接后,即可删去p。

c.p有两个孩子 把P的中序前驱结点的值赋给该结点的值 域,然后再删除它的中序前驱结点,因它的中序 前驱结点的右指针为空,所以只要把中序前驱 结点的左指针链接到中序前驱结点所在的链接 位置即可。

画一画:
分别删除72、12、49、28结点。请画出分 别删除一个结点后得到的二叉排序树。

⑵删除算法

Procedure dele (var bst:point; k:datatype) ; begin 1) p:=bst ; q:=nil ; b:= false {q指向p的前驱} while ( p<> nil) and ( b=false ) do {查找待删结点} begin if k= p^.da then b:=true else if k<p^.da then begin q:=p ;p:=p^.left ; end else begin q:= p ;p:= p^.right ; end end ; 2) if p=nil then write(‘no found’) {无可删的结点}

3) else begin {分三种不同情况删除} i)if (p^.left=nil ) and (p^.right=nil){是叶结点} then if p=bst then bst:=nil else if p=q^.left then q^.left:=nil else q^.right:=nil ;

ii)if (p^.left=nil ) or (p^.right=nil) {单支结点} then if p=bst then if p^.left=nil then bst:=p^.right else bst:

=p^.left else begin {分四种情况删除非根的单支结点} if(p=q^.left) and (p^.left<>nil) then q^.left:=p^.left ; if(p=q^.left)and (p^.right<>nil) then q^.left:=p^.right; if(p=q^.right)and (p^.left<>nil) then q^.right:=p^.left; if(p=q^.right)and (p^.right<>nil) then q^.right:=p^.right; end;

iii) if (p^.left<>nil) and ( p^right<>nil) then begin {有两个孩子} (a) r:=p;s:=p^.left ; {s指向p^的左子树的根结点,r
指向s的前驱结点}

(b) while s^.right<> nil do {查找p^前驱结点} begin r:=s ;s:=s^.right end; (c) p^.da :=s^.da {将s结点的值赋给p^结点} (d) if r=p then p^.left:=s^.left else r^.right:=s^.left
{删除结点s,并将它的左子树链接到位}

end end; {结束三种情况} end; 删除双支结点,包括两次查找,一次找待 删结点,一次找它的中序前驱结点。

作业题
1、输入n个不同的正整数,建立以这些数据为结点的二叉排序树: ⑴输出二叉排序树的广义表表示; ⑵查找值为X 的结点,若查找到,则输出“yes”,若查找不到,则 插入值为x的新结点,并输出插入x后中序遍历的结果。

输入: 第一行为n的值,第二行为n个不同的正整数,第三行 为x的值 输出: 两行。分别是问题⑴和⑵的解。 输入样例: 10 21 51 6 32 86 23 33 60 65 30 输出样例: 37(21(6,32(23,33)),51(,86(60(,65)))) 6 21 23 30 32 33 37 51 60 65 86

2、输入n个不同的正整数,建立以这些数据为结点的 二叉排序树。输入y,删除值为y的结点,输出删除 后二叉树的广义表表示。 输入: 第一行为n的值,第二行为n个不同的正整数,第三 行为y的值 输出: 删除y后,中序遍历的结果。 输入样例: 10 37 21 51 6 32 86 23 33 60 65 21 输出样例: 37(23(6,32(,33)),51(,86(60(, 65))))

3、试将一段英文中出现的单词按词典的顺序打印出来,同时 应注明每个单词在该段文章中出现的次数。 分析:将一段英文中的单词按词典顺序打印的过程,就是由 一个无序序列构造有序序列的过程,这个过程可以通过构造二 叉排序树实现。 输入: 一段英文 输出: 按词典的顺序打印单词,每个单词出现的次数 输入样例: Everyone round you can hear speak you when you 输出样例: can Everyone hear round speak when you everyone:1 round:1 you:3 can:1 hear:1 when:1 speak:1

4、将一棵一般树(由单字符组成)转换成二叉树, 并输出转换得到的二叉树的广义表表示。 一般树输入方式用父亲与孩子间加括号的串表示。 例如,图1所示的树,串表示输入为: A(B(E)C(FG)D(H(IJK))) 分析:一般树转化为二叉树的方法:将结点的第一 个孩子作为左孩子,结点的右邻兄弟作为前面左孩 子结点的右孩子。如图1的树,根结点A的第一个 孩子为结点B,则结点B为转化二叉

树后为结点A 的左孩子,结点C是结点B的右邻兄弟,则结点C 为转化二叉树后结点B的右孩子,同样,结点D是 结点C的右邻兄弟,则为其转化后的右孩子。类推, 转化后的二叉树形式如图2所示。

输入: 一个字符串 输出: 二叉树的广义表 输入样例: A(B(E)C(FG)D(H(IJK))) 输出样例: A(B(E,C(F(,G),D(H(I(,J(,K)))))))


网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com