二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(8)

{

// 查找第i-1个元素p

p = L; j = 0;

while ( p && j<i-1 ) {

插入前p = p->next; j++;

}

// 若找到，在p后插入x

if ( p && j==i-1 ) {

执行①之后s = (LinkList) malloc(sizeof(LNode));

s->data = x;

s->next = p->next; // ①

p->next = s; // ②

执行②之后return true; // 插入成功

}

else

return false; // 插入失败

}

注意：

a) 要让p指向第i-1个而不是第i个元素（否则，不容易找到前驱以便插入）。

b) 能够插入的条件： p && j==i-1 。即使第i个元素不存在，只要存在第i-1个元素，仍然可以插入第i个元素。

c) 新建结点时需要动态分配内存。

s = (LinkList) malloc(sizeof(LNode));

若检查是否分配成功，可用

if ( s==NULL ) exit(1); // 分配失败则终止程序

d) 完成插入的步骤：①②。技巧：先修改新结点的指针域。

12. 删除算法 ListDelete(&L,i,&x)

思路：

先查找第i-1个元素

若找到且其后存在第i个元素，则用x返回数据，并删删除前

除之

bool ListDelete ( LinkList &L, int i, int &x )

执行①之后 { 6 这里返回true表示正确插入，返回false表示插入失败。

// 查找第i-1个元素p

p = L; j = 0;

while ( p && j<i-1 ) {

p = p->next; j++;

}

//若存在第i个元素，则用x返回数据，并删除之

if ( p && j==i-1 && p->next ) { // 可以删除

s = p->next; // ①

p->next = s->next; // ②

x = s->data;

free (s);

return true;

}

else

return false;

}

注意：

a) 要求p找到第i-1个而非第i个元素。为什么？

b) 能够进行删除的条件： p && j==i-1 && p->next 。条件中的p->next就是要保证第i个元素存在，否则无法删除。若写成p->next && j==i-1也不妥，因为此时(循环结束时)可能有p==NULL，所以必须先确定p不空。技巧：将条件中的“大前提”放在前面。该条件也不可以写成p->next && p && j==i-1，因为先有p!=0才有p->next，上式颠倒了这一关系。

c) 释放结点的方法。 free(s);

d) 完成删除的步骤：①②。

13. 建立链表的两种方法

思路：

建立空表（头结点）；

依次插入数据结点（每次插入表尾得(a1,a2,?,an)，每次插入表头得(an,?,a2,a1)）。二叉排序树的建立 a) 顺序建表

void CreateLinkList ( LinkList &L, int n)

{

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-8.html