第十二章动态数据结构

第十二章动态数据结构内容摘要：

inorder( p right ) } } * + a / d * b c e f ＊ ＋ a / b c d * e f  后序遍历过程是： 得到表达式的表达式的逆波兰表示式（运算符在两个运算分量之后）。 后序遍历算法是： void postorder (treepointer p) { /*后序遍历 */ if ( p!=NULL ) { postorder( p left )。 postorder( p right ) printf(―%c‖ , p data )。 } } * + a / d * b c e f ＊ ＋ a / b c d * e f  检索 检索是按给定关键字值 c 在树上找一个结点 ti ，且 ti 的关键字值 key 恰好等于 c。 若检索到，函数将带回相应结点指针；否则若没检索到，函数将带回 NULL。 下述检索算法的前提条件是， p 是检索树。 treepointer search( typekey c , treepointer p ) { if ( ( p key == c ) || ( p == NULL ) ) return p。 else if ( c p key ) return search( c , p left )。 else return search( c , p right )。 }  插入一个结点 插入是指将一个数据项插入到树中某一恰当位置，使树仍保持检索树的性质。 显然，首先要按 key值查出应该插入的位置，然后再插入。 void insert( keytype c , datatype d , treepointer *p ) { if ( *p == NULL ) { *p = (treepointer)malloc(sizeof(struct tree))。 (*p) key = c。 (*p) data = d。 (*p) left = NULL。 (*p) right = NULL。 }else if ( c (*p) key ) insert( c , d , amp。 ((*p)left) )。 else insert( c , d , amp。 ((*p)right) )。 } 由于 insert 的参数 p 是指向指针的指针类型，在 insert 内 p 指向 指针类型的实在参数。 所以在执行 *p=(treepointer)malloc(sizeof(struct tree)) 时，将使实在参数指针变量指向新申请来的结点。 1) 若调用 insert 时，如图 root 为空树。 以 amp。 root 作实在参数调用 insert , 即 insert(c,d,amp。 root) insert 的形式参数 p 指向 root ，而 root 值为 NULL。 转插入功能，执行 *p=(treepointer)malloc(sizeof(struct tree)) 得 : 再执行后边的几个赋值语句 , 得 : root: c。 d p: 2) 若调用 insert时， root非空，在中间某一个结点查到空指 针，如图；设查到该结点后，应该继续向右查，以 amp。 ((*p)right) 作实在参数递归调用 insert，即执行 insert(c,d, amp。 ((*p)right) ) insert 的形式参数 p 指向本步的 (*p) right ，而 (*p) right 值为 NULL。 转插入功能，执行 *p=(treepointer)malloc(sizeof(struct tree)) 再执行后边的几个赋值语句 , 得 : c。 d ... ... p: 删除一结点 设欲删除结点为 r，则可能有如下几种情况。 针对不同情况删除算法不同 . r 是叶结点 :简单删掉 r 结点，并把 r 的父结点连接处改成 NULL 即可。 4 2 5 1 3 r: r 只有一个左子树 7 8 5 6 3 1 2 4 r: 7 8 5 6 4 2 3 1 r: r 只有一个子树 : 把 r 以下部分接入 r 的父结点连接 r 处。 然后删掉 r结点。 r 只有一个右子树 r 两个方向都有子树 : 在 r 的左子树上找到关键字 key 值最大的结点 s，把 s 结点的数据 data及关键字 key 复制到 r 结点上，然后删除掉 s 结点。 9 s: 10 r: 4 5 14 15 12 13 3 1 2 11 8 6 7 9当然也可以在 r的右子树上找到关键字 key值最小的结点s，把 s结点的数据 data及关键字 key复制到 r结点上，然后删除掉 s结点。 8 s: 5 r: 4 10 13 14 11 12 3 1 2 9 7 6 6使用在左子树上找最大结点的方法，按如下步骤进行 : ① 沿 r 左子树的右方向，向下找一个没有 右子树的结点 s ，图中结点 (9)。 ② 把该结点 s 的值复制到结点 r（即欲删除 的结点。 ③ 把 s 的左子树连在 s 的父结点（图中为 结点 (5) ）的右链上，在图中即连到 (5) 结点的右链上。 ④ 删除 s结点，即图中的 (9)结点。 图 3的情况 r 两个方向都有子树 : 在 r 的左子树上找到关键字 key 值最大的结点 s，把 s 结点的数据 data及关键字 key 复制到 r 结点 上，然后删除掉 s 结点。 9 s: 10 r: 4 5 14 15 12 13 3 1 2 11 8 6 7 9 综合上述三种情况，下述函数 deletenode 完成删除一个结点。 deletenode的调用形式是： deletenode( valueofkey , amp。 root ) 其中  value_of_key是欲删除结点的关键字值；  root是指针类型（ treepointer）变量，指向树根。 这里 用指向指针的指针作参数。 treepointer del( treepointer * , treepointer * )； /* 处理第三种情况的函数的函数原型 */ void deletenode( keytype c , treepointer *p ) { /* 删除关键字值等于 c 的结点 */ treepointer r。 if ( *p == NULL ) printf( ―not found:%d\n‖ , c )。 else if ( c (*p) key ) /* c 当前结点的 key 值，被删结点在左子树上 */ deletenode( c , amp。 ((*p) left) )。 else if ( c (*p) key ) /* c 当前结点的 key 值，被删结点在右子树上 */ deletenode( c , amp。 ((*p) right ) )。 else{ r = *p。 if ( rright == NULL ) *p = r left /* 右子树空，接左分支 */ else if ( rleft == NULL ) *p = r right。 /* 左子树空，接右分支 */ else r=del( amp。 (rleft),p )。 /* 左右均非空 */ free( r )。 /* 释放 r */ } }。 4 5 6 2 7 1 3 8 root: p: deletenode( 4 , amp。 root ) r: r 只有一个左子树 treepointer del( treepointer *s, treepointer *p ) { /* 处理第三种情况，仅第三种情况调用 */ treepointer r。 if ((*s)right != NULL ) /* 右分支非空 ? */ r=del( amp。 ((*s)right),p ) //右分支非空 , 在右方向以下继续查找 else { /* 找到右分支为空的结点 *s */ (*p)key =(*s) key。 /* 复制 *s的关键字、数据到 *p结点 */ (*p)data =(*s) data。 r = *s。 /* r记载该 *s结点，为 free做准备 */ *s。