【c语言】二叉树--介绍和基本用法

大家好呀~，在这里提前祝大家小年快乐啦！新的一年不要放下学习嗷

很高兴我今天又简单的了解了一个知识——二叉树

二叉树又叫做二叉链表，众所周知，链表是一对一的，而二叉树和其他类型的树都是一对多的。

就像这样：

有序二叉树有一个特点：左子树<根<右子树 ，我现在说的就是这种二叉树。

除了删除结点很不方便，其他的都跟链表很像，如果看不懂的话建议提前看一下我之前的博客

【C语言】单向链表--介绍和基本操作_emo~~~~的博客-CSDN博客

还是一个结构体：只不过里面有两个指针，一个指向左子树lchild，一个指向右子数rchild

在添加时，我们需要先找到最后的子节点，而且按照上面说的特点进行判断，并把新节点newnode连接在树上面。

在遍历时：我们有三种遍历方式：前序遍历、中序遍历、后序遍历。其中对于有序二叉树，中序遍历可以从小到大有序的输出树中的数据。

注释很多，具体的大家看注释吧！

#include
#include

typedef struct btree
{
	struct btree* lchild;
	char value;
	struct btree* rchild;
}*bitree,bitnode;//创建一个结点
//创建bitree的原因是需要它来代表树，而bitnode代表的是每个结点的大小，用于malloc

bitree creat(bitree ptr,int n)//传进来的是根(其实创建函数也就相当于查找函数)
{
	bitree newnode = (bitree)malloc(sizeof(bitnode));
	bitree now,back;
	back = NULL;
	newnode->value = n;
	newnode->lchild = NULL;
	newnode->rchild = NULL;
	now = ptr;
	if (ptr == NULL)//传进来的是一个空指针，说明此时树还是空的
	{
		ptr = newnode;
		return ptr;
	}
	else
	{
		while (now)//遍历，找到适合添加新结点的位置
		{
			back = now;//将最后一个结点的位置存起来
			if (now->value > n)
				now = now->lchild;
			else
				now = now->rchild;
		}
		if (back->value > n)
			back->lchild = newnode;
		else
			back->rchild = newnode;
	}
	return ptr;//添加完成，返回根
}

void mid(bitree ptr)//中序遍历
{
	if (ptr != NULL)//递归出口
	{
		mid(ptr->lchild);
		printf("%d  ", ptr->value);//中序遍历就是输出在中间，而且还可以按从小到大输出
		mid(ptr->rchild);
	}
}

void front(bitree ptr)//前序遍历
{
	if (ptr != NULL)//递归出口
	{
		printf("%d  ", ptr->value);
		mid(ptr->lchild);
		mid(ptr->rchild);
	}
}

void behind(bitree ptr)//后序遍历
{
	if (ptr != NULL)//递归出口
	{
		mid(ptr->lchild);
		mid(ptr->rchild);
		printf("%d  ", ptr->value);
	}
}

void addp(bitree ptr)
{
	int n = 0;
	int count = 0;
	scanf("%d", &n);
	bitree now = NULL;
	now = ptr;
	while (now != NULL)
	{
		if (now->value == n)
		{
			printf("已有此结点n");
			count = 1;
			break;
		}
		else if (now->value > n)
			now = now->lchild;
		else
			now = now->rchild;
	}
	if (count == 0)
	{
		ptr = creat(ptr, n);//直接添加进去
		printf("n最终结果为：n");
		mid(ptr);
	}
}

int main()
{
	int i = 0;
	int arr[] = { 5,6,24,8,12,3,17,1,9 };
	bitree ptr = NULL;
	for(int i=0;i<9;i++)
		ptr = creat(ptr,arr[i]);
	printf("原始数据为：n");
	mid(ptr);
	printf("n");
	printf("输入您想要插入的数据：n");
	addp(ptr);
	return 0;
}

希望与诸君共勉。