C++学习记录-数据结构-二叉树的插入和查找数字

C++学习记录-数据结构-二叉树的插入和查找数字

迭代法实现插入

void Insert(int num)
{
	scanner = root;//首先保存一下根节点的地址

	if (root == NULL)//如果根节点为空
	{
		root = new Node;
		root->data = num;//new一个并赋值
		scanner = root;//扫描指针重新定位到根节点
		return;
	}

	else//如果根节点不为空
	{
		while (true)
		{
			if (root->data >= num)//如果当前节点的数据大于等于欲插入的数据，则要左拐
			{
				if (root->left != NULL) { root = root->left; }//判断左孩是否为空，若否则指向左孩，继续循环查找位置
				else
				{
					root->left = new Node;
					root->left->data = num;
					root = scanner;//记得还原root节点
					break;
				}
				//如果为空，则说明找到了位置，对左孩进行赋值，注意此时 root->left 为NULL，如果让root=root->left，则会导致节点断连，因此不要进入root->left
			}
            
			else if (root->data < num)//如果当前节点的数据小于欲插入的数据，则要右拐
			{
				if (root->right != NULL) { root = root->right; }//判断右孩是否为空，若否则指向右孩，继续循环查找位置
				else
				{
					root->right = new Node;
					root->right->data = num;
					root = scanner;//记得还原root节点
					break;
				}
				//如果为空，则说明找到了位置，对右孩进行赋值，注意此时 root->left 为NULL，如果让root=root->left，则会导致节点断连，因此不要进入root->left
			}
		}
		return;
	}
}//迭代法实现二叉树插入

递归法实现二叉树查找数字

void search(Node*rootPtr,int num)
{
	if (rootPtr == NULL)
	{
		cout << "No";
		return;
	}
	//找不到或树为空，回馈No

	else if (rootPtr->data == num)
	{
		cout << "Yes";
		return;
	}
	//找到了，回馈Yes

	else if (rootPtr->data > num)
	{
		search(rootPtr->left, num);
	}
	//如果当前节点数据大于与查找的数，则要向左查找，这是一个递归的过程

	else if (rootPtr->data < num)
	{
		search(rootPtr->right, num);
	}
	//如果当前节点数据大于与查找的数，则要向左查找，这是一个递归的过程
	
	return;

}//递归法实现二叉树搜索