二叉树搜索

#include <stdio.h>
#include <stdlib.h>
struct BstNode {
	int data;
	BstNode* left;  //指向左孩的指针
	BstNode* right;  //指向右孩的指针

};

struct BstNode* root; //root为根  Ptr代表指针

BstNode* GetNewnode(int data)   //创建一个新节点
{
	struct BstNode* newNode = (struct BstNode*)malloc(sizeof(struct BstNode));
	newNode->data = data;
	newNode->left = NULL;
	newNode->right = NULL;
	return newNode;
}
BstNode* Insert(BstNode* root,int data)   //插入一个节点
{
	if (root == NULL)  //判断树根是否为空
	{
		root = GetNewnode(data); //如果为空则调用GetNewnode创建一个节点 使其成为树根
	}
	else if (data <= root->data)  //递归调用，判断插入值与当前值的大小关系，大于则在左树，小于则在右树
	{
		root->left = Insert(root->left, data);
	}
	else 
	{
		root->right = Insert(root->right, data);
	}
	return root; //返回指向树根的指针
}
bool Search(BstNode* root, int data)  //查找值
{
	if (root == NULL)
		return false;
	else if (data == root->data) 
		return true;
	else if (data <= root->data)  //如果当前值大于data则从左分支查找
		return Search(root->left, data);
	else
		return Search(root->right, data);//如果当前值小于data则从右分支查找
}
int main()
{
	int number;
	root = NULL;  //将指向树根的指针设为空 即为空树
	root = Insert(root, 10); root = Insert(root, 25);
	root = Insert(root, 30); root = Insert(root, 13);
	printf("请输入你想查找的数字:");
	scanf("%d", &number);
	if (Search(root, number))
		printf("存在！");
	else
		printf("不存在！");

	return 0;
}

二叉树搜索最小值

int FindMin(BstNode* temp)   //使用递归寻找最小值
{
	if (temp == NULL)   //当树为空报错
	{
		printf("树为空,发生错误！\n");
		return -1;
	}
	else if (temp->left == NULL)  //当前节点无左树时，即为最小值
	{
		return temp->data;
	}
	else
	{
		return FindMin(temp->left);  //当前节点还存在左树时，递归调用该函数
	}
}

二叉树的高度

int FindHeight(BstNode* temp)
{
	if (temp == NULL)   //当树为空报错
	{
		return -1;  //默认规定空树的高度为-1 也可以写成0
	}
	return fmax(FindHeight(temp->left), FindHeight(temp->right) )+ 1; //比较左右空树的选出最大值
}

二叉树广度优先

层序遍历

// 以层序遍历方式打印二叉树中的节点
void LevelOrder(struct BstNode* current) {
	if (root == NULL) return;
	struct BstNode* queue[100]; // 定义一个队列用于存储节点
	int front = 0, rear = 0; // 定义队列的前后指针
	queue[rear++] = root; // 将根节点加入队列
	while (front < rear) { // 当队列不为空时循环
		struct BstNode* current = queue[front++]; // 取出队首节点
		printf("%c ", current->data); // 打印节点数据
		if (current->left != NULL) queue[rear++] = current->left; // 将左子节点加入队列
		if (current->right != NULL) queue[rear++] = current->right; // 将右子节点加入队列
	}
}

二叉树深度优先

• 前序遍历

• 中序遍历

• 后序遍历

前序遍历 root left right

void PreOrder(struct BstNode* temp)  //传入根节点
{
	if (temp == NULL)  //递归调用退出条件
		return;
	printf("%c", temp->data);
	PreOrder(temp->left);  //递归调用 递归结束时 栈上空间会被释放 地址为0
	PreOrder(temp->right);
}

中序遍历 left root right

void InOrder(struct BstNode* temp)
{
	if (temp == NULL)
		return;
	PreOrder(temp->left);
	printf("%c", temp->data);
	PreOrder(temp->right);
}

后序遍历 left right root

void PostOrder(struct BstNode* temp)
{
	if (temp == NULL)
		return;
	PreOrder(temp->left);
	PreOrder(temp->right);
	printf("%c", temp->data);
}

二叉搜索树

判断是否为二叉搜索树

bool IsBinarySearchTree(struct BstNode* temp, int minValue, int maxValue)  //判断是否为二叉搜索树
{
	if (temp == NULL)
		return;
	//传入的节点应小于最大值，大于最小值，并且左树节点最小值应为minVal，最大值应为自身data，右树的最小值应为自身data，最大值为maxValue
	if (temp->data <= maxValue && temp->data >= minValue && IsBinarySearchTree(temp->left, minValue, temp->data) && IsBinarySearchTree(temp->right, temp->data, maxValue))
		return true;
	else
		return false;
}

删除一个节点

struct BstNode* Delete(struct BstNode* current, int data)
{
	if (current == NULL)
		return current;
	else if (data < current->data)
		current->left = Delete(current->left, data);
	else if (data > current->data)
		current->right = Delete(current->right, data);
	else
	{
		if (current->left == NULL && current->right == NULL) //第一种情况 无左右子节点
		{
			delete current;
			current = NULL;

		}
		else if (current->left == NULL)  // 第二种情况 只有一个子节点
		{
			struct BstNode* temp = current;
			current = current->right;
			delete temp;
			return current;
		}
		else if (current->right == NULL) 
		{
			struct BstNode* temp = current;
			current = current->left;
			delete temp;
			return current;
		}
		else
		{
			struct BstNode* temp =FindMin(current->right); //Findmin函数返回树中最小值的地址
			current->data = temp ->data;
			current->right = Delete(current->right, temp->data);
		}
			
	}
}

中序后续节点

struct BstNode* Getsuccessor(struct BstNode* root, int data)
{
	struct BstNode* current = find(root, data);  //find函数为找到指定值的位置
	if (current == NULL)
		return NULL;
	if (current->right != NULL)  //第一种情况 右子树不为空
	{
		return FindMin(current->right);
	}
	else  //第二种情况 右子树为空
	{
		struct BstNode* successor = NULL;
		struct BstNode* ancestor = root;

		while (current != ancestor)
		{
			if (current->data < ancestor->data)
			{
				successor = ancestor;   //把当前ancestor的值给successor，然后ancestor向左子节点移动，直到ancestors 和当前节点值一致
				ancestor = ancestor->left;
			}
			else
				ancestor = ancestor->right;   //当前节点大于ancestor时，ancestor变大 再次循环 直到进入上一个if条件，找出successor值
		}
		return successor; 
	}
}