数据结构Day12

心已赠人 2023-07-15 11:24 2阅读 0赞

## 0、二叉查找树 ##

首先需要明确的是二叉树和二叉查找树的区别  
二叉树就是我们正常所理解的这种树形结构，每一个节点都包含一个项和两个指向其他节点（称为子节点）的指针，分为左节点和右节点。  
树的顶部，称为根；  
当一个节点没有子节点时，称为叶节点。  
而二叉查找树是在二叉树的基础上有如下规定：左节点的项在父节点的项前面，右节点的项在父节点的后面。

## 1、二叉查找树的ADT ##

对于一个抽象数据类型而言，最主要的可以概括为增查删改，而这些的前提是判断是否为空、是否为满、返回总项数。由于上述前提都相对来说比较简单，因此在这里不做过多讨论。下面依次来讨论一下二叉树的增查删改。

### 1、添加项 ###

添加项时需要注意的逻辑是，  
**1、二叉查找树是否已经满了**  
这个问题的判断相对来说较简单，只需要判断这个二叉树的累计项数是否大于了设定的最大值，在这种条件下，每删除一个项都需要将Size-1，每添加一个项都需要将Size+1  
**2、为待添加的项分配内存**  
在这里调用了MakeNode函数，使用Malloc对内存进行分配，需要注意的是在分配内存的时候要注意防止内存溢出。  
**3、待添加的项应该添加到哪一个位置**  
待添加的项需要添加到二叉树的哪一个位置由AddNode实现。**在这里要注意一点，公共接口函数处理的是用户所关心的问题，即只需要处理有关项和树的问题，而隐藏的对于节点等处理与指针相关的实质性业务的函数应在Static中实现**，例如这里的AddNode函数，在AddNode函数中，为了保证模块化设计，在这里使用ToLeft和ToRight两个函数去判断应该将这个函数放到哪里，这个过程一直持续到函数发现一个空子树为止，并在此处添加一个新的节点，因此这里的代码使用递归的方式实现，在使用递归的时候应该注意对每一种可能出现的情况都做判断，避免出现死循环导致内存溢出。在这个程序中，最终判断的逻辑为待添加位置是否为空，即如果应该向左放下一个节点，该节点的左节点是否为空，若为空，则表示这个节点已经是这个方向的最后一个节电了，递归结束。

### 2、查找项 ###

查找项需要注意的逻辑为  
**1、遵循模块化的设计理念**  
对节点的操作放在该文件中实现，即查找项的函数应该作为公共函数，而对节点的操作应该认为是ADT内的操作。  
**2、返回值中增加其父节点**  
为了便于之后删除项，在删除项中，需要知道待删除项的父节点，以便删除子节点之后更新父节点指向子节点的指针。  
**3、循环判断**  
循环判断该节点的项是否和树中的项相等，依次比较是否需要往左，是否需要往右，当前面两者都不满足时，则表示两个节点相等，此时退出。look.child即为目标项的节点，而Look.parent中已经在每一次的比较之后都会更新。如果轮询完所有的节点之后都没有发现，则look.child的值会为NULL，此时退出。而在判断的时候只需要判断look.child的值是不是为NULL，即可以知道这个节点是不是在二叉查找树中了。

while(look.child != NULL)
    { 
    	if(Toleft(待查找项，树中的当前项))
    	{ 
    	}
    	if(ToRight(待查找项，树中的当前项))
    	{ 
    	}
    	else
    		break;	
    }

### 3、删除项 ###

删除项的逻辑需要注意以下：  
**1、待删除的节点没有子节点**  
没有子节点时，只需要把其父节点的指针置为NULL即可，当然要去判断待删除的节点为其父节点的左节点还是右节点。在实际函数中，这种情况与删除右左节点的情况合并。  
**2、待删除的节点有一个子节点**  
在这种情况下，需要把被删除的节点的父节点中的地址更新为被删除节点子树的地址。例如，当一个节点没有左节点的时候，程序将右节点的地址赋给其父节点的指针，如果该节点也没有右节点，则指针为NULL，这就是没有子节点的情况。  
**3、待删除的节点有两个子节点**  
这个的删除逻辑为通过for循环找到被删除节点的左子树中最右边的叶节点，将被删除节点的右子树连接到这个叶节点上，之后将被删除的节点的左节点连接套被删除的节点的父节点上。  
**4、删除节点**  
删除节点时需要注意的一点是待修改的值本身就是Trnode\_t \*类型，因此要想修改这个指针地址，传进来的参数应该为Trnode\_t \*\* 类型。同时也应该注意模块化的设计理念，将删除节点和删除项的函数分开，删除节点的函数代码见下：

static void func(Trnode_t **pTr)
    { 
    	Trnode_t * Temp;
    	if((*pTr)->left == NULL)	//没有左节点
    	{ 
    		Temp = *ptr;
    		*ptr = (*ptr)->right;	//如果右节点的指针也为NULL，则表明无子节点
    		free(Temp);	//释放掉被删除节点的内存。
    	}
    	else if((*pTr)->left == NULL)	//没有右节点
    	{ 
    		Temp = *ptr;
    		*ptr = (*ptr)->left;
    		free(Temp);	//释放掉被删除节点的内存。
    	}
    	else
    	{ 
    		//表明右两个子节点，先找到左子树的最右一个叶节点
    		for(temp = (*ptr)->left; temp->right!= NULL; temp=temp->right)
    		{ 
    			continue;
    		}
    		//当找到退出时，temp即为最右边的叶节点
    		temp->right = (*ptr)->right;
    		temp = *ptr;
    		*ptr = (*ptr)->left;
    		free(temp);
    	}
    }

**5、删除项**  
删除项即是把项和对应的节点关联，使用前面说到的查找项的函数（seekItem）。在这里需要增加几个判断，a.判断找到的项是否有效；b.删除的节点是否为根节点，若为根节点，则直接将ptree->root传到删除节点的函数中，因为这种情况不用更新父节点，但是要更新Tree\_t结构中根节点的指针，因此传入的参数是根节点。  
在这里传入参数的时候需要注意传入的必须是其父节点中的对应子节点，而不能直接传入子节点，如果直接传入子节点的话，会导致父节点不知道其对应的子节点已经被改掉了，因而会产生野指针的情况，即子节点的地址已经被free掉了，而父节点中的子节点仍然保存着之前的值，会产生野指针的情况。

### 4、遍历项 ###

遍历项的核心操作为利用递归的特性，从左子树的项到中间的项，到右子树的项，依次不断递归遍历，其遍历过程自己画一个二叉查找树，之后依次遍历一遍就可以了。

void func(Trnode_t * root, (void)(*pfunc)(Item_t Item) )
    { 
    	if(root != NULL)
    	{ 
    			func( root->left, pfunc );
    			(*func)(root->Item);
    			func( root->right, pfunc );
    	}
    }

遍历项分为前序遍历、中序遍历和后序遍历，当按照左子树-项-右子树的顺序遍历即为前序遍历，按照项-左子树-右子树的顺序遍历即为中序遍历，按照左子树-右子树-项的顺序即为后序遍历，其主要差别为递归顺序的不同。