实现
/*
* 二叉查找树
* 定义:
* 1.若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
* 2.若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
* 3.左、右子树分别为二叉查找树;
* 4.没有键值相等的结点;
*/
#include <stdio.h>
#include <stdlib.h>
#define Error(Str) FatalError(Str);
#define FatalError(Str) fprintf(stderr, "%s\n", Str), exit(1)
#define GetArrayLen(array,len){len = (sizeof(array) / sizeof(array[0]));}
struct TreeNode;
typedef int ElementType;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
struct TreeNode
{
//int depth;
ElementType Element;
SearchTree Left;
SearchTree Right;
};
SearchTree createTree();
SearchTree MakeEmpty(SearchTree T);
/*
* 创建一棵树
*/
SearchTree createTree()
{
SearchTree T;
T = malloc(sizeof(struct TreeNode));
if(T == NULL)
FatalError("内存申请失败!");
T->Left = NULL;
T->Right = NULL;
return T;
}
/*
* 插入
*/
SearchTree Insert(ElementType X, SearchTree T)
{
if(T == NULL)
{
//创建一个单节点的树
T = malloc(sizeof(struct TreeNode));
if(T == NULL)
FatalError("内存申请失败!");
else
{
T->Element = X;
T->Left = T->Right = NULL;
}
}
else
if(X < T->Element)
T->Left = Insert(X, T->Left);
else
if(X > T->Element)
T->Right = Insert(X, T->Right);
return T;
}
/*
* 置空一棵树
*/
SearchTree MakeEmpty(SearchTree T)
{
if(T != NULL)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return NULL;
}
/*
* 查找
*/
Position Find(ElementType X, SearchTree T)
{
if(T == NULL)
return NULL;
if(X < T->Element)
return Find(X, T->Left);
else
if(X > T->Element)
return Find(X, T->Right);
else
return T;
}
/*
* 查找最小节点(递归实现,用相同方法查找最大节点时只需将分支朝向右子树即可)
*/
Position FindMin(SearchTree T)
{
if(T == NULL)
return NULL;
else
if(T->Left == NULL)
return T;
else
return FindMin(T->Left);
}
/*
* 查找最大节点(非递归)
*/
Position FindMax(SearchTree T)
{
if(T != NULL)
while(T->Right != NULL)
T = T->Right;
return T;
}
/*
* 删除
*/
SearchTree Delete(ElementType X, SearchTree T)
{
Position TmpCell;
if(T == NULL)
{
Error("元素没有找到,亲!");
}
else
if(X < T->Element)//要删除的数据小于该节点的元素值,递归调用左子树
T->Left = Delete(X, T->Left);
else if(X > T->Element)//要删除的数据大于该节点的元素值,递归调用右子树
T->Right = Delete(X, T->Right);
else//找到要删除的元素
if(T->Left && T->Right)//该节点拥有两个子树
{
//替换右子树中最小的节点
TmpCell = FindMin(T->Right);
T->Element = TmpCell->Element;
T->Right = Delete(T->Element, T->Right);
}
else//1个或0个子树
{
TmpCell = T;
if(T->Left == NULL)
T = T->Right;
else if(T->Right == NULL)
T = T->Left;
free(TmpCell);
}
return T;
}
/*
* 二叉查找树打印
*/
SearchTree printfTree(SearchTree T,int dep, int flag)
{
if(T == NULL)
return NULL;//递归出口
else
{
dep++;
int i;
for(i=1; i<dep; i++)
printf("----");
if(1 == flag)
printf("%d--left--dep:%d\n", T->Element, dep);
else if(2 == flag)
printf("%d--right--dep:%d\n", T->Element, dep);
else
printf("%d--root--dep:%d\n", T->Element, dep);
printfTree(T->Left, dep, 1);
printfTree(T->Right, dep, 2);
}
}
void main()
{
//创建一个二叉查找树
int arr[100];
int len,i;
//GetArrayLen(arr, len);
SearchTree tree = NULL;
//主循环
char input[10];
int list_val=0,key;
while(1)
{
//参数接收
int par_key=1,par3=0;
while(1)
{
if(1 == par_key)
scanf("%s", &input);
else if(2 == par_key)
scanf("%d", &list_val);
else if(3 == par_key)
scanf("%d", &par3);
else
break;
char c=getchar();
if(c=='\n')
break;
par_key++;
}
if(strcmp(input , "insert") == 0)
{
//结点新增
tree = Insert(list_val, tree);
printf("插入完成,新插入的值为:%d,下面是目前的二叉查找树,皮卡！\n", list_val);
printfTree(tree,0, 0);
}
else if(strcmp(input , "find") == 0)
{
//结点查找
}
else if(strcmp(input , "delete") == 0)
{
//结点删除
Delete(list_val, tree);
printf("节点删除完成,要删除的值为:%d,下面是目前的二叉查找树,皮卡！%d\n", list_val,tree->Element);
printfTree(tree,0, 0);
}
else if(strcmp(input, "edit") == 0)
{
//结节修改
}
else if(strcmp(input , "traverse") == 0)
{
//遍历
printfTree(tree,0, 0);
}
else if(strcmp(input , "exit") == 0)
break;
}
}2.运行结果：
[root@iZ28mhfkaunZ tree]# ./searchtree insert 16 插入完成,新插入的值为:16,下面是目前的二叉查找树,皮卡！ 16--root--dep:1 iinsexi exit [root@iZ28mhfkaunZ tree]# ./searchtree insert 15 插入完成,新插入的值为:15,下面是目前的二叉查找树,皮卡！ 15--root--dep:1 insert 19 插入完成,新插入的值为:19,下面是目前的二叉查找树,皮卡！ 15--root--dep:1 ----19--right--dep:2 insert 17 插入完成,新插入的值为:17,下面是目前的二叉查找树,皮卡！ 15--root--dep:1 ----19--right--dep:2 --------17--left--dep:3 delete 19 节点删除完成,要删除的值为:19,下面是目前的二叉查找树,皮卡！15 15--root--dep:1 ----17--right--dep:2
3.