注册

已有账号?请登录

登录

还没账号?请注册

C语言实现的二叉搜索树

二叉搜索树,又名二叉查找树、二叉排序树。英文名叫Binary Search Tree, 简称BST

基本性质

  1. 若左子树非空,则左子树上所有结点的值均小于根结点的值
  2. 若右子树非空,则右子树上所有结点的值均大于根结点的值
  3. 左、右子树本身又各是一棵二叉排序树
  4. 所有节点都是唯一的,不允许出现重复

1. 插入节点

算法

  1. 检查根节点(root)是否NULL
  2. 若根节点等于NULL,则将新节点(newNode)变成根节点,即root=newNode
  3. 若根节点不是NULL,那么就将根节点变成当前节点(temp)与新节点比较,即temp=root
  4. 重复步骤5、6、7,直到当前节点变成NULL
  5. 将当前节点赋值给父节点,即parent=temp
  6. 若新节点小于当前节点,则往左边搜寻,即temp=temp->left
  7. 若新节点大于当前节点,则往右边搜寻,即temp=temp->right
  8. 若新节点小于父节点,则将新节点变成父节点的左子节点,即parent->left=newNode
  9. 若新节点大于父节点,则将新节点变成父节点的右子节点,即parent->right=newNode

时间复杂度: 最好情况 O(log n) 最坏情况 O(n)

上述代码输出

输出结果: 5 2 1 4 3 8 7 6 9

2. 删除节点

  1. 节点是叶子节点,直接删除
  2. 节点只有一个子节点,用子节点替换该节点的位置
  3. 节点有左右两个子节点,在该节点的右子树中找出最小的节点来替换该节点的位置

算法

  1. 若节点小于当前节点,则递归左子树
  2. 若节点小于当前节点,则递归右子树
  3. 若找到节点,目标节点没有子节点就直接删除并返回NULL
  4. 若找到节点,目标节点只有一个子节点,则将子节点赋值给目标节点并释放原目标节点
  5. 若找到节点,目标节点有两个子节点,则从目标节点的右子树中找出最小的节点data赋值给目标节点的data并递归目标节点的右子树

时间复杂度: 最好情况 O(log n) 最坏情况 O(n)

上述代码输出

删除前: 5 2 1 4 3 8 7 6 9

删除后: 6 3 8 7 9

3. 前、中、后序遍历及搜索

  1. 前序遍历:首先访问根节点,然后访问左子树,最后访问右子树
  2. 中序遍历:首先访问左子树,然后访问根节点,最后访问右子树
  3. 后序遍历:首先访问左子树,然后访问右子树,最后访问根节点

时间复杂度:O(n)

上述代码输出

前序遍历: 5 2 1 4 3 8 7 6 9

中序遍历: 1 2 3 4 5 6 7 8 9

后序遍历: 1 3 4 2 6 7 9 8 5

找到: 2

没找到12

本站所有文章均由阿坤原创,欢迎转载!

Copyright © 2020 luozk.com All Rights Reserved