ch2-5数据结构_树.pptVIP

第二章 常用数据结构及其运算 树的定义（逻辑结构） 树是一种数据结构： Tree=（D，R） 其中： D 是具有相同特性的数据元素的集合； R 是D上逻辑关系的集合，且满足： 在D中存在唯一的称为根的数据元素，没有前趋； D中其余数据元素都有且只有一个前趋； D中所有元素，或有若干个互不相同的后继（子树），或无后继（叶结点）； 则称Tree为树。 2.5 树与二叉树 2.5.4 二叉树的应用 1. 二叉排序树 （1）定义：二叉排序树是一棵二叉树，满足下列条件： ? 空树； ? 左子树上的结点值 根结点的值； ? 右子树上的结点值 = 根结点的值； ? 左、右子树也是二叉排序树。 10 3 15 9 8 9 21 13 4 2 18 在二叉排序树中，若按中序遍历就可以得到由小到大的有序序列。上图中序遍历得到： { 2，3，4，8，9，9，10，13，15，18，21 } 2.5 树与二叉树 2.5.4 二叉树的应用 1. 二叉排序树 （2）二叉排序树的插入（生成） ? 在给定的二叉排序树中插入值为b的结点 若树为空，则作为根结点； 若树不空，则将b与根结点值r作比较： br，插入左子树； b=r，插入右子树； （注：新插入的结点一定是新添的叶子结点） 2.5 树与二叉树 2.5.4 二叉树的应用 1. 二叉排序树 ? 插入算法： InsertBet(t,b){ if (t==nil){ GETNODE(t)； data(t)-b; lchild(t)-nil; rchild(t)-nil; } else if (bdata(t)) InsertBet(lchild(t),b); else InsertBet(rchild(t),b); } 2.5 树与二叉树 ? 二叉排序树是一种动态表结构，即二叉排序树的生成过程是不断地向二叉排序树中插入新的结点。 2.5.4 二叉树的应用 10 18 3 7 12 8 2 3 10 10 18 10 18 3 10 18 8 3 10 18 12 8 3 10 18 12 8 2 3 10 18 7 12 8 2 3 序列 {10，18，3，8，12，2，7，3} 构成一棵二叉排序树的过程。 （3）二叉排序树的删除：删除结点P，使删除后的二 叉树仍是二叉排序树：DelNode(t,p,f) 2.5 树与二叉树 2.5.4 二叉树的应用 1. 二叉排序树 P为叶子结点 P只有左或右子树 直接删除 将P的左子树或右子树直接成为其双亲结点的左右子树 循着P的左子树的根C找其右子树分支，找到第一个无右子树的结点S，将S的左子树改为其双亲结点Q的右子树，用S取代P。 Y Y N N 2.5 树与二叉树 F CL PR f P C Q S QL SL p q s F CL PR f S C Q QL p q SL 2.5.4 二叉树的应用 例： 1. 二叉排序树 DelNode(*t,*p,*f){ fag=0; if (p-lchild==NULL) f=p-rchild; else if (p-rchild==NULL) f=p-lchild; else{ q=p; s=p-lchild; while (s-rchild!=NULL){ q=s; s=s-rchild; } if (q==p) q-lchild=s-lchild; else q-rchild=s-lchild; p-data=s-data; free(s); fag=1; } if (fag==0){ if (f==NULL) t=s; else if (f-lchild==p) f-lchild=s; else f-rchild=s; free(p); }} 2.5 树与二叉树 2.5.4 二叉树的应用 删除算法： 2.5 树与二叉树 2.5.4 二叉树的应用 例： 1. 二叉排序树 10 18 4 12 2 3 15 7 6 删7 10 18 4 12 2 3 15 6 10 18 4 2 3 15 6 删12 10 15 4 2 3 6 删18 10 15 4 2 6 删3 6 15 2 4 删10 * * 2.5 树与二叉树 ? 非线性数据结构 ? 元素结点之间存在分支和层次关系。(一对多) ? 应用：家谱 社会组织机构 书的章节划分 操作系统中的多级目录结