发表更新数据结构16 分钟读完 (大约2472个字)

二叉查找树

  • 先附上完整的代码
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
template <class KEY,class OTHER>
struct SET
{
	KEY key;																		
	OTHER other;																	
};

template<class KEY,class OTHER>
class dynamicSearchTable
{
public:
	virtual SET<KEY, OTHER>* find(const KEY& x) = 0;
	virtual void insert(const SET<KEY, OTHER>& x) = 0;
	virtual void remove(const KEY& x) = 0;
	virtual ~dynamicSearchTable() {};
};

template<class KEY, class OTHER>
class BinarySearchTree :public dynamicSearchTable<KEY, OTHER>
{
private:
	struct BinaryNode
	{
		SET<KEY, OTHER>data;
		BinaryNode* left;
		BinaryNode* right;
		BinaryNode(const SET<KEY, OTHER>& thedata, BinaryNode* It = NULL,
			BinaryNode* rt = NULL):data(thedata),right(rt){}
	}; 
    BinaryNode* root;
    
public:
	BinarySearchTree();
	~BinarySearchTree();
	SET <KEY, OTHER>* find(const KEY& x)const;
	void insert(const SET<KEY, OTHER>& x);
	void remove(const KEY& x);
    
private:
	void insert(const SET<KEY, OTHER>& x, BinaryNode*& t);
	void remove(const KEY& x, BinaryNode*& t);
	SET <KEY, OTHER>* find(const KEY& x,BinaryNode* t)const;
	void makeEmpty(BinaryNode* t);
};


template<class KEY, class OTHER>
SET <KEY, OTHER>* BinarySearchTree<KEY, OTHER>::find(const KEY& x)const
{
	return find(x, root);
}


template<class KEY, class OTHER>
SET <KEY, OTHER>* BinarySearchTree<KEY, OTHER>::find(const KEY& x, BinaryNode* t)const
{
	if (t == NULL || (t->data.key == x))				
		return (SET<KEY,OTHER>*)t;										
	if (x < t->data.key)								
		return find(x.t->left);							
	else return find(x, right);							
}

template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::insert(const SET<KEY, OTHER>& x)
{
	insert(x, root);
}


template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::insert(const SET<KEY, OTHER>& x, BinaryNode*& t)
{
	if (t == NULL)
		t = new BinaryNode(x, NULL, NULL);							
	else if (x.key < t->data.key)									
		insert(x, t->left);					
	else if (t->data.key < x.key)									
		insert(x, t->right);
}

template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::remove(const KEY& x)
{
	remove(x, root);
}

template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::remove(const KEY& x, BinaryNode*& t)
{
	if (t == NULL)return;											
	if (x < t->data.key)remove(x, t->left);							
	else if (t->data.key < x)remove(x, t->right);
	else if (t->left != NULL && t->right != NULL)					
	{																
		BinaryNode* tmp = t->right;									
		while (tmp->left != NULL)tmp = tmp->left;					
		t->data = tmp->data;										
		remove(t->data.key, t->right);								
	}
	else
	{
		BinaryNode* oldNode = t;									
		t = (t->left != NULL) ? t->left : t->right;					
		delete oldNode;												
	}
}

template<class KEY, class OTHER>
BinarySearchTree<KEY, OTHER>::BinarySearchTree()
{
	root = NULL;
}

template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::makeEmpty(BinaryNode* t)
{
	if (t == NULL)return;										
	makeEmpty(t->left);
	makeEmpty(t->right);
	delete t;
}

template<class KEY, class OTHER>
BinarySearchTree<KEY, OTHER>::~BinarySearchTree()
{
	makeEmpty(root);
}

int main()
{
	return 0;
}

前提组成

  • template <class KEY,class OTHER>
struct SET
{
    KEY key;																		//关键字信息
    OTHER other;																	//和其他信息
};

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15

      这是基本的数据元素

      分别包括**键值**key和**其他值**value（就像字典里面对应的查找关键和词语解释）

    - ~~~c++
      template<class KEY,class OTHER>
      class dynamicSearchTable
      {
      public:
      	virtual SET<KEY, OTHER>* find(const KEY& x) = 0;						//查找目标元素，返回值为指针
      	virtual void insert(const SET<KEY, OTHER>& x) = 0;						//插入功能
      	virtual void remove(const KEY& x) = 0;									//显然是删除功能
      	virtual ~dynamicSearchTable() {};										//析构函数
      };
    

这就是二叉查找树的父类**动态查找表**，也可以看作一个模板而已，提供了基础的一个动态查找的基本功能模板

动态二叉树

  • 动态二叉树的主体类函数
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
template<class KEY, class OTHER>
class BinarySearchTree :public dynamicSearchTable<KEY, OTHER>
{
private:
	struct BinaryNode
	{
		SET<KEY, OTHER>data;
		BinaryNode* left;
		BinaryNode* right;

		BinaryNode(const SET<KEY, OTHER>& thedata, BinaryNode* It = NULL,
			BinaryNode* rt = NULL):data(thedata),right(rt){}
	}; BinaryNode* root;

public:
	BinarySearchTree();										//构造函数
	~BinarySearchTree();									//析构函数
	SET <KEY, OTHER>* find(const KEY& x)const;				//查找函数（公有，面向使用者）
	void insert(const SET<KEY, OTHER>& x);					//插入函数（公有，面向使用者）
	void remove(const KEY& x);								//删除函数（公有，面向使用者）
private:
	void insert(const SET<KEY, OTHER>& x, BinaryNode*& t);		//查找函数（私有，面向公有调用函数）
	void remove(const KEY& x, BinaryNode*& t);					//插入函数（公有，面向公有调用函数）
	SET <KEY, OTHER>* find(const KEY& x,BinaryNode* t)const;	//删除函数（公有，面向公有调用函数）
	void makeEmpty(BinaryNode* t);								//清空函数
};

树的节点分析：

1
2
3
4
5
6
7
8
9
struct BinaryNode
	{
		SET<KEY, OTHER>data;								//本体的数据
		BinaryNode* left;									//左子节点的指针
		BinaryNode* right;									//右子节点的指针

		BinaryNode(const SET<KEY, OTHER>& thedata, BinaryNode* It = NULL,	//节点的构造函数，可以直接设定三个成员
			BinaryNode* rt = NULL):data(thedata),right(rt){}
	}; BinaryNode* root;

注意：后面经常会用到公有函数调用私有函数，虽然名称一样，但一个面向使用者，私有的面向共有的函数调用内部

1
2
3
4
5
void remove(const KEY& x)								//删除函数（公有，面向使用者）
{
    remove(x,root);										//这里调用的就是私有函数
}
void remove(const KEY& x, BinaryNode*& t);				//这就是私有函数的接口和实现

接下来分析函数的实现

  • 构造函数
1
2
3
4
5
template<class KEY, class OTHER>
BinarySearchTree<KEY, OTHER>::BinarySearchTree()
{
	root = NULL;										//简单初始化了一下根节点
}
  • makempty

主要还是递归循环删除，采用了前序遍历的思想

1
2
3
4
5
6
7
8
template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::makeEmpty(BinaryNode* t)
{
	if (t == NULL)return;									//递归终止的条件（删到了空节点）
	makeEmpty(t->left);										//正常步骤先删左节点，往下递归
	makeEmpty(t->right);									//再删右节点，往下递归
	delete t;												//删除自己	
}//最后就删除了所给节点和节点的所有子节点

拓展：其实最近刷题还看到了一种实现方法就是入队和出队在这里

优点：就是摆脱了递归的对于空间的大量调用，利用循环和队列实现（更多是在链表使用的方法）

其实这是层序遍历的使用方法，只是用这个实现了层序遍历的删除方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
>**自己拓展的，不是范例的**
>Queue<BinaryNode*>  queue;									//存放节点指针的队列

>template<class KEY, class OTHER>
>void BinarySearchTree<KEY, OTHER>::makeEmpty(BinaryNode* t)
>{
queue.enqueue(t);										//先把根节点放入队列
   while(t.isempty())										//终止条件：检查队列是否为空，不空则继续进行
   {
       BinaryNode* t=queue.dequeue();						//出队队列的第一个节点
       if(t->left!=nullptr)queue.enqueue(t->left);			//左子节点有就放进队列，没则不处理
       if(t->right!=nullptr)queue.enqueue(t->right);		//同理
       delete t;											//然后删除自己
   }
>}
  • 析构函数
1
2
3
4
5
template<class KEY, class OTHER>
BinarySearchTree<KEY, OTHER>::~BinarySearchTree()
{
	makeEmpty(root);											//就从root开始删除，很简单，不解释了
}
  • 插入函数（insert）

从这插入函数观察二叉树的构成特点：左子节点小于父节点，右子节点大于父节点（节点不会重复）

这个特点就导致插入的时候有一个特性：以这个特点往下寻找插入点必然是叶节点，从而使插入特别方便。

函数还是递归实现的函数，逐次往下寻找（二叉树的结构导致如果树高了必然会导致搜索耗费大量的时间，之后会有扁平的处理方法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::insert(const SET<KEY, OTHER>& x)
{
	insert(x, root);												//表示从根节点往下寻找插入点
}

template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::insert(const SET<KEY, OTHER>& x, BinaryNode*& t)
{
	if (t == NULL)
		t = new BinaryNode(x, NULL, NULL);							//若根节点不存在，则直接存进去
	else if (x.key < t->data.key)									//若小于当前节点则向左递归
		insert(x, t->left);					
	else if (t->data.key < x.key)									//大于则向右递归
		insert(x, t->right);										
																	//等于的情况直接退出不干，二叉树的插入必须是不同
}
  • 查找函数（find）

查找函数就是基于二叉树的结构特点建立的，左小右大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class KEY, class OTHER>
SET <KEY, OTHER>* BinarySearchTree<KEY, OTHER>::find(const KEY& x)const
{
	return find(x, root);
}

template<class KEY, class OTHER>
SET <KEY, OTHER>* BinarySearchTree<KEY, OTHER>::find(const KEY& x, BinaryNode* t)const
{
	if (t == NULL || (t->data.key == x))				//如果是不存在或者就是当前的节点
		return (SET<KEY,OTHER>*)t;						//找到就返回这个指针,没有的话就是返回空指针
	if (x < t->data.key)								//如果小于则向左找
		return find(x.t->left);							
	else return find(x, right);							//大于则向右找
}

注意：有人可能会注意到，t不是BinarNode吗，怎么能强制转换为SET类的指针啊

1
return (SET<KEY,OTHER>*)t;

这里需要解释一下结构体和类的一个特点：

对于类和结构的存贮使从第一个数据成员开始的。

举个例子：对于BinarNode的存储空间第一个就是存放的SET，因为在定义里面是写在第一个的。

从而对于指向BinaryNode存储空间的指针某种意义上也是指向了SET的开头，进而可以进行强制转换

1
2
3
4
5
6
7
8
9
10
//树节点的结构体
struct BinaryNode
	{
		SET<KEY, OTHER>data;
		BinaryNode* left;
		BinaryNode* right;

		BinaryNode(const SET<KEY, OTHER>& thedata, BinaryNode* It = NULL,
			BinaryNode* rt = NULL):data(thedata),right(rt){}
	}; BinaryNode* root;
  • 删除函数（remove）

主体思路：

  • 删除大体是这个思路为了保证树的结构不变，主要分三种情况
  • 1.如果这个删除节点没有度数为0，很简单删除就好了
  • 2.只有一个子节点，把字节点复制上去，把字节点删除
  • 3.这个最复杂，因为他又俩个节点，为了保证树结构不变必然是在叶子节点中找到最靠近这个节点的数
  • 其实根据这个查找二叉树的结构，分析出最接近的是左子节点一直往子节点的右子节点找（左子节点<x<当前节点），或者是右子节点的左子节点一直找（当前节点<x<右子节点）
  • 对于这题我们假设向右子节点寻求最接近的值

最关键的是：

首先，替代问题，为了保证稳定性必须要替换一个最接近的节点互换位置，顶替

其次由于结构最接近无非 最近但小于（左节点的最右节点）和最近但大于 （右节点的最左字节点）

这个寻找方法便捷的地方在于必然是叶子节点替换，也易于删除

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
//这里的实现主要是最右子节点最左节点（大于且最靠近的树）
template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::remove(const KEY& x)
{
	remove(x, root);
}

template<class KEY, class OTHER>
void BinarySearchTree<KEY, OTHER>::remove(const KEY& x, BinaryNode*& t)
{
    //先找到要删除的节点
	if (t == NULL)return;
    //第一种情况空节点返回

	if (x < t->data.key)remove(x, t->left);
    //第二种情况，要删除小于当前节点，往左递归
    
	else if (t->data.key < x)remove(x, t->right);
    //第三种情况要找的大于当前节点，往右边递归

	else if (t->left != NULL && t->right != NULL)					
	{																
		BinaryNode* tmp = t->right;									
		while (tmp->left != NULL)tmp = tmp->left;
        //循环找到右子节点的最左节点
        
		t->data = tmp->data;
        //替换俩个节点顺序
		remove(t->data.key, t->right);
        //删除替换后的叶子节点，结束
	}
    //第四种，找到了当前节点就是要删除的节点，但是左右都有子节点
    
    
	else
	{
		BinaryNode* oldNode = t;																					t = (t->left != NULL) ? t->left : t->right;
        //如果有一个子节点，t就是直接替换为子节点，然后删除原来的节点，即使没有子节点，t变为空间点也合乎逻辑
		delete oldNode;
	}
    //第五种，找到了要么一个子节点，要么没有

	//有没有发现，我选择右子树寻找替代，那么替代的那个点也是右子树要处理
}

有一点需要注意：

1
>void BinarySearchTree<KEY, OTHER>::remove(const KEY& x, BinaryNode*& t)

我们发现节点的参数传递都是引用传递，那是为了方便节点直接替换

例如remove，正是因为引用传递，在层层递归中确保每次传下来的t都是确确实实来自于父节点里面直接的左右节点的指针

这样就维持了上下关系，确保修改是有效的

##总结：至此就分析结束了

（有时间在这里补一个二叉树查找性能的分析）

http://example.com/2024/06/08/二叉查找树（动态查找表dynamicSearchTree）/

作者

yang

发布于

2024-06-08

更新于

2024-06-08

许可协议

#

评论

关注我

归档

标签

STL1
c++1
c++语法2
csv1
json1
塔防课程1
数据结构3
游戏心得2
设计模式1

分类

链接

最新文章

×