二叉树的基本操作（节点创建、二叉树的创建、遍历、叶子结点的数量、二叉搜索树的插入、二叉搜索树的检索）

二叉树的基本操作（节点创建、二叉树的创建、遍历、叶子结点的数量、二叉搜索树的插入、二叉搜索树的检索）

• 节点创建

//节点定义
typedef struct BTreeNode
{
	int data; 
	struct BTreeNode* lchild;
	struct BTreeNode* rchild;
}BTreeNode;

typedef BTreeNode* btreenode;

//创建节点
BTreeNode* CreateNode(int val)
{
	BTreeNode* p = (BTreeNode*)malloc(sizeof(btreenode));
	p->data = val;
	p->lchild = p->rchild = NULL;
	return p;
}

• 二叉树的创建

//二叉树的创建
struct BTreeNode* Create()
{
	int val;
	scanf("%d",&val);
	struct BTreeNode* root = (struct BTreeNode*)malloc(sizeof(struct BTreeNode*));

	if (val < 0)
	{
		return NULL;
	}

	if (!root)
	{
		printf("创建失败\n");
	}

	if (val > 0)
	{
		root->data = val;
		root->lchild = Create();
		root->rchild = Create();
	}

	return root;
}

二叉树的遍历（前序、中序、后序）

//前序遍历
void FronTraval(btreenode root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d",root->data);
	FronTraval(root->lchild);
	FronTraval(root->rchild);
}

//中序遍历
void Midtraval(btreenode root)
{
	if (root == NULL)
	{
		return;
	}
	FronTraval(root->lchild);
	printf("%d", root->data);
	FronTraval(root->rchild);
}


//后序遍历
void Midtraval(btreenode root)
{
	if (root == NULL)
	{
		return;
	}
	FronTraval(root->lchild);
	FronTraval(root->rchild);
	printf("%d", root->data);
}

• 叶子节点的数量

//二叉树的叶子节点的数量
int LeafNode(btreenode root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->lchild == NULL && root->rchild == NULL)
	{
		return 1;
	}
	else
	{
		return LeafNode(root->lchild) + LeafNode(root->rchild);
	}
}

- 二叉搜索树的插入

//二叉搜索树的插入
void InsertNode(btreenode root, int val)
{
	if (root == NULL)
	{
		return;
	}
	
	int rootData = root->data;

	//根据值得大小创建相应的节点（左节点）
	if (root->lchild == NULL && val < rootData)
	{
		root->lchild = CreateNode(val);
		return;
	}

	//根据值得大小创建相应的节点（右节点）
	if (root->rchild == NULL && val > rootData)
	{
		root->rchild = CreateNode(val);
		return;
	}

	//将值放入相应的节点
	if (val > rootData)
	{
		InsertNode(root->rchild, val);
	}
	else if (val < rootData)
	{
		InsertNode(root->lchild, val);
	}
}

• 二叉树的检索

//二叉搜索树的检索(递归实现)
void SearchData(int val, btreenode root)
{
	if (root != NULL)
	{
		if (root->data == val)
		{
			printf("%d\n",root->data);
		}
		else if (val > root->data)
		{
			SearchData(val,root->lchild);
		}
		else if (val < root->data)
		{
			SearchData(val,root->rchild);
		}
	}
}