当前位置:   article > 正文

基于C语言的二叉排序树操作(包含完整代码)_试用c语言编写二叉树的排序程序

试用c语言编写二叉树的排序程序

二叉排序树(BST也称二叉查找树), 或者是一颗空树,或者是具有下列特性的二叉树:

(1)若左子树非空,则左子树上所有结点的值均小于根结点的值

(2)若右子树非空,则右子树上所有结点的值均大于根结点的值

(3)左右子树也分别是一颗二叉排序树 

 如下图例子所示:

 1.定义结构体

  1. typedef struct TreeNode
  2. {
  3. int data;//数据域
  4. struct TreeNode *lchild;//左孩子
  5. struct TreeNode *rchild;//右孩子
  6. }TreeNode;

 2.BST查找

  1. TreeNode *bstSearch(TreeNode *T,int data)
  2. {
  3. if(T)//不是空树则进入判断
  4. {
  5. if(T->data==data)//查找到,直接返回
  6. return T;
  7. else if(T->data>data)//左小右大,数据小,则递归往左子树走
  8. return bstSearch(T->lchild,data);
  9. else
  10. return bstSearch(T->rchild,data);//数据大,则递归往右子树走
  11. }
  12. else//全部查找结束没有则返回空
  13. return NULL;
  14. }

3.创建bst树

  1. void bstInsert(TreeNode **T,int data)
  2. {/*第一个参数**T:双重解引用,用于更改T中的值
  3. 第二个参数data:用于传递元素并比较大小*/
  4. if(*T==NULL)//首先判断该结点是否为空,是空结点则新建结点并初始化
  5. {
  6. *T = (TreeNode *)malloc(sizeof(TreeNode));//申请内存空间
  7. (*T)->data = data;//写入数据
  8. (*T)->lchild = NULL;//左孩子初始为空
  9. (*T)->rchild = NULL;//右孩子初始为空
  10. }
  11. else if(data==(*T)->data)//二叉排序树不允许重复元素,遇到重复元素跳过
  12. return;
  13. else if((*T)->data>data)//要插入的元素比结点内的元素小,则往左子树走
  14. return bstInsert(&((*T)->lchild),data);
  15. else//要插入的元素比结点内的元素大,则往右子树走
  16. return bstInsert(&((*T)->rchild),data);
  17. }

4.前序遍历(根左右)

  1. void preOrder(TreeNode *T)
  2. {
  3. if(T)
  4. {
  5. printf("%d ",T->data);//输出根结点
  6. preOrder(T->lchild);//递归遍历左子树
  7. preOrder(T->rchild);//递归遍历右子树
  8. }
  9. }

5.主函数验证

  1. int main()
  2. {
  3. TreeNode *T = NULL;//定义根结点
  4. TreeNode *node;//定义第三结点主要接收BST查找函数变量
  5. int nums[6] = {8,6,10,9,11,23};
  6. int i;
  7. for(i=0;i<6;i++)
  8. {
  9. bstInsert(&T,nums[i]);//验证创建bst树
  10. }
  11. preOrder(T);//验证先序遍历
  12. printf("\n");
  13. node = bstSearch(T,9);//验证BST查找
  14. printf("%d\n",node->data);
  15. return 0;
  16. }

完整代码如下:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. /*定义结构体*/
  4. typedef struct TreeNode
  5. {
  6. int data;//数据域
  7. struct TreeNode *lchild;//左孩子
  8. struct TreeNode *rchild;//右孩子
  9. }TreeNode;
  10. /*BST查找*/
  11. TreeNode *bstSearch(TreeNode *T,int data)
  12. {
  13. if(T)//不是空树则进入判断
  14. {
  15. if(T->data==data)//查找到,直接返回
  16. return T;
  17. else if(T->data>data)//左小右大,数据小,则递归往左子树走
  18. return bstSearch(T->lchild,data);
  19. else
  20. return bstSearch(T->rchild,data);//数据大,则递归往右子树走
  21. }
  22. else//全部查找结束没有则返回空
  23. return NULL;
  24. }
  25. /*创建bst树*/
  26. void bstInsert(TreeNode **T,int data)
  27. {/*第一个参数**T:双重解引用,用于更改T中的值
  28. 第二个参数data:用于传递元素并比较大小*/
  29. if(*T==NULL)//首先判断该结点是否为空,是空结点则新建结点并初始化
  30. {
  31. *T = (TreeNode *)malloc(sizeof(TreeNode));//申请内存空间
  32. (*T)->data = data;//写入数据
  33. (*T)->lchild = NULL;//左孩子初始为空
  34. (*T)->rchild = NULL;//右孩子初始为空
  35. }
  36. else if(data==(*T)->data)//二叉排序树不允许重复元素,遇到重复元素跳过
  37. return;
  38. else if((*T)->data>data)//要插入的元素比结点内的元素小,则往左子树走
  39. return bstInsert(&((*T)->lchild),data);
  40. else//要插入的元素比结点内的元素大,则往右子树走
  41. return bstInsert(&((*T)->rchild),data);
  42. }
  43. /*前序遍历(根左右)*/
  44. void preOrder(TreeNode *T)
  45. {
  46. if(T)
  47. {
  48. printf("%d ",T->data);//输出根结点
  49. preOrder(T->lchild);//递归遍历左子树
  50. preOrder(T->rchild);//递归遍历右子树
  51. }
  52. }
  53. /*主函数验证*/
  54. int main()
  55. {
  56. TreeNode *T = NULL;//定义根结点
  57. TreeNode *node;//定义第三结点主要接收BST查找函数变量
  58. int nums[6] = {8,6,10,9,11,23};
  59. int i;
  60. for(i=0;i<6;i++)
  61. {
  62. bstInsert(&T,nums[i]);//验证创建bst树
  63. }
  64. preOrder(T);//验证先序遍历
  65. printf("\n");
  66. node = bstSearch(T,9);//验证BST查找
  67. printf("%d\n",node->data);
  68. return 0;
  69. }

 6.运行结果

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/709617
推荐阅读
相关标签
  

闽ICP备14008679号