Fork me on GitHub

二叉搜索树

发表于 | 更新于: | 分类于 | | 浏览 次
字数统计: 1,542 | 阅读时长 ≈ 8

二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树

  • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树

二叉搜索树操作

头文件定义

1
2
3
4
5
6
7
8
typedef int DataType;

typedef struct BSTreeNode
{
	DataType key;
	struct BSTreeNode *left;
	struct BSTreeNode *right;
}BSTreeNode;

查找

若根结点不为空
当key == 查找的key，返回true
当key > 查找的key，在其左子树中查找
当key < 查找的key，在其右子树中查找
否则返回false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//查找递归写法
int BSTreeFind(const BSTreeNode *root, DataType key)
{
	if (root == NULL)
	{
		return 0;
	}

	if (key == root->key)
	{
		return 1;
	}else	if (root->key < key)
	{
		BSTreeFind(root->right,key);
	}
	else
	{
		BSTreeFind(root->left, key);
	}

	return 0;
}

//查找非递归写法
int BSTreeFind2(const BSTreeNode *root,DataType key)
{
	BSTreeNode *cur = (BSTreeNode *)root;
	while (cur != NULL)
	{
		if (cur->key == key)
		{
			return 1;
		}
		else if (cur->key > key)
		{
			cur = cur->left;
		}
		else
		{
			cur = cur->right;
		}
	}
	return 0;

}

插入

在二叉搜索树中插入新元素时，必须先检测该元素是否在树中已经存在。如果已经存在，则不进行插入；否则将新元素加入到搜索停止的地方。

插入具体过程

  1. 树为空，则直接插入,返回true
  2. 树不空，按二叉搜索树性质查找插入位置，插入新节点
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    //非递归插入写法
    int BSTreeInsert(BSTreeNode **root,DataType key)
    {
    	BSTreeNode *cur = *root;
    	BSTreeNode *parent = NULL;

    	//先找到要插入的位置
    	while (cur != NULL)
    	{
    		//先判断是否已存在该元素
    		if (key == cur->key)
    		{
    			return 0;
    		}
    		
    		parent = cur;
    		if (key>cur->key)
    		{
    			cur = cur->right;
    		}
    		else
    		{
    			cur = cur->left;
    		}
    	}

    	//创建结点
    	BSTreeNode *node = (BSTreeNode *)malloc(sizeof(BSTreeNode));
    	node->key = key;
    	node->left = node->right = NULL;

    	//插入元素
    	if (parent == NULL)
    	{
    		*root = node;
    		return 1;
    	}

    	if (key<parent->key)
    	{
    		parent->left = node;
    	}
    	else
    	{
    		parent->right = node;
    	}
    	return 1;
    }

    //递归插入写法   
    int BSTreeInsert2(BSTreeNode **root, DataType key)
    {
    	if (*root == NULL)
    	{
    		BSTreeNode *node = (BSTreeNode *)malloc(sizeof(BSTreeNode));
    		node->key = key;
    		node->left = node->right = NULL;
    		*root = node;
    		return 1;
    	}

    	if ((*root)->key == key)
    	{
    		return 0;
    	}
    	if (key >(*root)->key)
    	{
    		return BSTreeInsert2(&(*root)->right,key);
    	}
    	else
    	{
    		return BSTreeInsert2(&(*root)->right, key);
    	}
    }

删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
==情况1可以归类到2或者3==
对于上述情况，相应的删除方法如下：
a. 直接删除该结点
b. 删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点
c. 删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
d. 在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，在来处理该结点的删除问题 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
void RemoveLeftNULL(BSTreeNode *parent,BSTreeNode *cur, BSTreeNode **root,DataType key)
{
	if (parent == NULL)
	{
		*root = cur->right;
	}
	else
	{
		if (key < parent->key)
		{
			parent->left = cur->right;
		}
		else
		{
			parent->right = cur->right;
		}
	}
	free(cur);
}

void RemoveRightNULL(BSTreeNode *parent, BSTreeNode *cur, BSTreeNode **root, DataType key)
{
	if (parent == NULL)
	{
		*root = cur->left;
	}
	else
	{
		if (key < parent->key)
		{
			parent->left = cur->left;
		}
		else
		{
			parent->right = cur->left;
		}
	}
	free(cur);
}

static void RemoveHasLeftAndRight(BSTreeNode *cur)
{
	BSTreeNode *del = cur->left;
	BSTreeNode *delParent = NULL;
	while (del->right != NULL)
	{
		delParent = del;
		del = del->right;
	}
	cur->key = del->key;

	//删除del结点
	if (delParent == NULL)
	{
		//左孩子中最大的就是cur的左孩子
		cur->left = del->left;
	}
	else
	{
		delParent->right = del->left;
	}
	free(del);
}
int BSTreeRemove(BSTreeNode **root,DataType key)
{
	BSTreeNode *cur = *root;
	BSTreeNode *parent = NULL;

	//先找到要插入的位置
	while (cur != NULL)
	{
		//先判断是否已存在该元素
		if (key == cur->key)
		{
			if (cur->left == NULL)
			{
				RemoveLeftNULL(parent,cur,root,key);
			}
			else if (cur->right == NULL)
			{
				RemoveRightNULL(parent,cur,root,key);
			}
			else
			{
				RemoveHasLeftAndRight(cur);
			}
		}

		parent = cur;		//parent记录当前找到结点
		if (key > cur->key)
		{
			cur = cur->right;
		}
		else
		{
			cur = cur->left;
		}
	}
	return 1;
}

二叉搜索树应用

  1. 判断一个单词是否拼写正确
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
typedef struct Word
{
	char word[20];
	struct  Word *left;
	struct Word *right;
}Word;

//递归查找
int WordFind(Word *root,char word[])
{
	const Word *cur = root;
	int r;

	while (cur != NULL)
	{
		r = strncmp(word, cur->word, 20);
		if (r == 0)
		{
			return 1;
		}
		else if(r>0)
		{
			cur = cur->right;
		}
		else
		{
			cur = cur->left;
		}
	}
	return 0;
}

int WordInsert(Word **root,char word[])
{
	int r;
	if (*root == NULL)
	{
		Word *node = (Word *)malloc(sizeof(Word));
		strncpy(node->word,word,20);
		node->left = node->right = NULL;
		*root = node;
		return 1;
	}

	r = strncmp(word, (*root)->word, 20);
	// r为0时，此时该word已存在，返回0
	if (r == 0)
	{
		return 0;
	}
	// r小于0，此时该word放在左子树，否则放右子树
	if (r<0)
	{
		return WordInsert(&(*root)->left,word);
	}
	else
	{
		return WordInsert(&(*root)->right, word);
	}
}

void TestWord()
{
	Word *dict = NULL;
	WordInsert(&dict, "Apple");
	WordInsert(&dict, "Banana");
	WordInsert(&dict, "Orange");
	WordInsert(&dict, "Watermelon");
	WordInsert(&dict, "Pinapple");
	WordInsert(&dict, "Pear");

	char word[20];

	while (1)
	{
		scanf("%s",word);
		if (WordFind(dict,word) == 1)
		{
			printf("拼写正确\n");
		}
		else
		{
			printf("拼写错误\n");
		}
	}
}
  1. 模拟实现一个简单的字典
  2. log文件中有许多异常重复的IP地址，请统计出每个异常IP出现了多少
    次？

本文标题:二叉搜索树

文章作者:LiuXiaoKun

发布时间:2018年08月31日 - 22:08

最后更新:2019年04月19日 - 11:04

原始链接:https://LiuZiQiao.github.io/2018/08/31/二叉搜索树/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%