二叉排序树删除值小于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;
}

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/cadae98a131ba7196b82fee02e766039.html