二叉排序树删除值小于value的结点


同学去阿里面试的时候，要求写出代码：

现在有一棵二叉排序树，每个节点保存一个int类型的值，删除值为10以下的节点（树中可能不含值为10的节点），说一下思路，写一下算法。

算了原来错误的思路就不拿出来误导大家了，只能说想简单了，花了几天空闲的时间思考这个问题，终于把代码写出来了，虽然琢磨了一段时间，但是终究还是写出来了。

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在JAVA中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

经过测试数据或者自己画图，感觉有这么几个难点把

1.如果数据是这样：6,5,7,8,15，就是先开始根结点的值小于10，后来右子树中=存在大于10的结点，由于需要释放小于10的结点，就需要重新调整根结点

2.如果数据是这样：6,5,7,8,15,14,9,8,13,11,10，就是先开始小于10，然后右子树出现了大于了10，结果峰回路转左子树中又有小于10的结点，其实这组数据基本就包含了核心代码的思想

代码思想：如果当前结点小于10的话，就循环查找右子树，直到找到第一个大于10的结点p，然后调整树结构，接着循环查找p的左子树，直到找到又出现第一个小于10的结点，然后递归查找右子树和左子树整个过程，直到没有大于10的结点为止

代码如下，其中题目要求为删除的值为10，当然更通用的是删除值为val以下的结点(如果结点值等于val，也会被删除)，另外在创建树的时候由于为了方便测试代码，所以随机生成，但是对于有相同值，会自动忽略，也就是树中的所有结点值都是唯一的：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct biTree{
 struct biTree*lchild,*rchild;
 int data;
};

struct biTree* createBST(struct biTree *root,int val){
 if(root==NULL){
  root=(struct biTree*)malloc(sizeof(struct biTree));
  root->data=val;
  root->lchild=root->rchild=NULL;
  return root;
 }
 if(val<root->data) root->lchild=createBST(root->lchild,val);
 else if(val>root->data) root->rchild=createBST(root->rchild,val);
 return root;
}

void inOrder(struct biTree*root){
 if(root==NULL)  return ;
 inOrder(root->lchild);
 printf("%d ",root->data);
 inOrder(root->rchild);
}

int delVal(struct biTree **root,int val){
 if(root==NULL) return 0;
 struct biTree *p=*root,*pre=*root;
 struct biTree *q=(struct biTree*)malloc(sizeof(struct biTree));
 while(1){
  int value=(*root)->data;
  while(p&&p->data<=val){
   pre=p;
   p=p->rchild;
   free(pre);
  }
  if(value<val) *root=p;    //其实只会调整一次根结点
  else q->lchild=p;
  while(p&&p->data>val){
   pre=p;
   p=p->lchild;
  }
  if(p==NULL)  break;
  q=pre;
 }
 return 1;
}

int main(){
 int i;
 while(1){
  int a[30];
  struct biTree *root=NULL;
  unsigned int seed;
  seed = time(0);
  srand(seed);
  for(i=0;i<10;i++){
   a[i]=rand()%100+1;
  }
  for(i=0;i<10;i++){
   printf("%d ",a[i]);
  }
  printf("\n");

  for(i=0;i<9;i++)  root=createBST(root,a[i]);
  inOrder(root);
  printf("\n");

  int val;
  scanf("%d",&val);  //输入某个值，小于这个值的所有结点都会被删除
  delVal(&root,val);
  inOrder(root);
  printf("\n\n");
  root=NULL;
 }
 
 return 0;
}

本文永久更新链接地址：

相关内容