二叉查找树的建立,删除,非递归和递归查找给定元素,非递归和递归查找最大元素结点和最小元素结点

简介: 二叉查找树的建立,删除,非递归和递归查找给定元素,非递归和递归查找最大元素结点和最小元素结点

二叉查找树的建立:

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 typedef int ElementType;
 5 typedef struct TNode* Position;
 6 typedef Position BinSeaTree;
 7 struct TNode {
 8     ElementType Data;
 9     BinSeaTree Left;
10     BinSeaTree Right;
11 };

递归查找给定元素

 1 Position FindRec(BinSeaTree BST, ElementType X)
 2 {
 3     if (!BST)
 4         return NULL;
 5     if (X > BST->Data)
 6         return FindRec(BST->Right, X);        //在右子树中查找
 7     else if (X < BST->Data)
 8         return FindRec(BST->Left, X);        //在左子树中查找
 9     else
10         return BST;
11 }

非递归查找给定元素:

 1 Position FindNoRec(BinSeaTree BST, ElementType X)
 2 {
 3     while (BST)
 4     {
 5         if (X > BST->Data)
 6             BST = BST->Right;        //向右子树移动,继续查找
 7         else if (X < BST->Data)
 8             BST = BST->Left;        //向左子树移动,继续查找
 9         else
10             break;            //找到了则跳出循环
11 
12     }
13     return BST;        //返回找到的结点地址,或者是NULL
14 }

递归查找最小元素结点

 1 Position FindMin(BinSeaTree BST)
 2 {
 3     if (!BST)
 4         return NULL;            //空的二叉搜索树,返回NULL
 5     else if (!BST->Left)                //找到最左端并返回
 6         return BST;
 7     else
 8         return FindMin(BST->Left);        //沿左分支继续递归查找
 9 
10 }

非递归查找最大元素结点:

1 //查找最大元素的非递归实现
2 Position FindMax(BinSeaTree BST)
3 {
4     if (BST)
5     while (BST->Right)
6         BST = BST->Right;
7     return BST;
8 }

插入一个结点:

 1 BinSeaTree Insert(BinSeaTree BST, ElementType X)
 2 {
 3     if (!BST)
 4     {
 5         BST = (BinSeaTree)malloc(sizeof(struct TNode));
 6         BST -> Data  = X;
 7         BST->Left = BST->Right = NULL;
 8     }
 9     else
10     {
11         if (X < BST -> Data)
12             BST->Left = Insert(BST->Left, X);        //递归插入到左子树
13         else if (X > BST->Data)
14             BST->Right = Insert(BST->Right, X);        //递归插入到右子树
15     }
16     return BST;
17 }

删除给定元素的结点:

1.要删除的结点有两个孩子结点

2.要删除的结点只有一个孩子结点

3.要删除的结点没有孩子结点

 1 //二叉搜索树的删除
 2 BinSeaTree Delete(BinSeaTree BST, ElementType X)
 3 {
 4     Position tmp;
 5     if (!BST)
 6         printf("The element to delte was not found\n");
 7     else
 8     {
 9         if (X > BST->Data)
10             BST->Right = Delete(BST->Right, X);        //从右子树中递归删除
11         else if (X < BST->Data)
12             BST->Left = Delete(BST->Left, X);        //从左子树中递归删除
13         else
14         {
15             if (BST->Left && BST->Right)
16             {
17                 tmp = FindMax(BST->Left);            //从左子树中找最大的元素填充删除结点
18                 BST->Data = tmp->Data;
19                 BST->Left = Delete(BST->Left, tmp->Data);        //将删除给定元素的左子树绑定到左子树上
20             }
21             else
22             {
23                 tmp = BST;
24                 if (!BST->Left)                //只有右孩子或无子节点
25                     BST = BST->Right;
26                 else
27                     BST = BST->Left;
28                 free(tmp);
29             }
30         }
31     }
32     return BST;                        //将删除给定元素的二叉树返回回去
33 }

用来测试的其他函数和主函数:

 1 void printBinTree(BinSeaTree BT, int depth)
 2 {
 3     for (int i = 0; i < depth; i++)
 4         printf("  ");
 5     printf("%d\n", BT->Data);
 6 }
 7 
 8 void InorderTraversal(BinSeaTree BT, int depth)
 9 {
10     if (BT)
11     {
12         InorderTraversal(BT->Right, depth + 1);
13         printBinTree(BT, depth);
14         InorderTraversal(BT->Left, depth + 1);
15     }
16 }
17 
18 int main()
19 {
20     BinSeaTree BST = NULL;
21     BinSeaTree node;
22     ElementType dt;
23     for (int i = 0; i < 7; i++)
24     {
25         scanf_s("%d", &dt);
26         BST = Insert(BST, dt);
27         getchar();
28     }
29     InorderTraversal(BST, 0);
30     node = FindMin(BST);
31     printf("\n\n%d\n", node->Data);
32     node = FindMax(BST);
33     printf("\n\n%d\n", node->Data);
34 
35     BST = Delete(BST, 41);
36     InorderTraversal(BST, 0);
37 
38     return 0;
39 }


相关文章
|
9月前
|
人工智能 测试技术 Windows
【深度优先搜索】【树】【状态压缩】2791. 树中可以形成回文的路径数
【深度优先搜索】【树】【状态压缩】2791. 树中可以形成回文的路径数
|
8月前
|
算法
|
9月前
|
机器学习/深度学习 C++
初阶数据结构之---二叉树链式结构(二叉树的构建,二叉树的前序,中序,后序和层序遍历,计算二叉树结点个数,第k层结点个数,叶子结点个数,判断是否为完全二叉树)
初阶数据结构之---二叉树链式结构(二叉树的构建,二叉树的前序,中序,后序和层序遍历,计算二叉树结点个数,第k层结点个数,叶子结点个数,判断是否为完全二叉树)
|
9月前
|
机器学习/深度学习
数据结构实验之查找一:二叉排序树
数据结构实验之查找一:二叉排序树
二叉树的三种遍历方式
二叉树的三种遍历方式
274 0
二叉树的三种遍历方式
|
存储 人工智能 搜索推荐
快排查找数组中的第K个最大元素(上)
冒泡排序、插入排序、选择排序时间复杂度都是O(n2),适合小规模数据排序。 两种时间复杂度为O(nlogn)的排序算法,归并排序和快速排序。这两种排序算法适合大规模数据排序,更常用。 归并排序和快速排序都用到了分治思想。
141 0
快排查找数组中的第K个最大元素(上)
|
人工智能 搜索推荐
快排查找数组中的第K个最大元素(下)
冒泡排序、插入排序、选择排序时间复杂度都是O(n2),适合小规模数据排序。 两种时间复杂度为O(nlogn)的排序算法,归并排序和快速排序。这两种排序算法适合大规模数据排序,更常用。 归并排序和快速排序都用到了分治思想。
198 0
快排查找数组中的第K个最大元素(下)