二叉查找树的建立：
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 }
