【数据结构】二叉树链接结构基本操作_二叉树创建根节点时怎么保证左右子树地址不同

二叉树顺序存储的优缺点：

顺序存储结构就是使用数组来存储，顺序结构操作比较简单，对于堆结构来说，适合使用顺序存储方式来解决。但数组只适合表示完全二叉树，对于一般的二叉树如果采用顺序存储方式会造成大量的空间浪费，这是我们不希望看到的。

由此引出来二叉树的链式存储。并实现二叉树的以下操作：

创建二叉树、拷贝二叉树、销毁二叉树、二叉树遍历（前序、中序、后续、层序）、获取二叉树中节点个数、获取二叉树中第K层节点个数、获取二叉树中叶子节点个数、二叉树高度（深度）、检测给定值的元素是否在二叉树中、二叉树的镜像以及判断二叉树是否为完全二叉树。

二叉树定义：使用孩子表示法

typedef char BTDataType;
typedef struct BTNode
{
	struct BTNode* _pLeft;
	struct BTNode* _pRight;
	BTDataType _data;
}BTNode;

头文件中函数声明：

//二叉树的创建
BTNode* CreatBinTree(BTDataType* array, int size, BTDataType invalid);
//二叉树的拷贝
BTNode* CopyBinTree(BTNode* pRoot);
//二叉树的销毁
void DestoryBinTree(BTNode** pRoot);
 
//递归：前序遍历
void PreOrder(BTNode* pRoot);
 
//递归：中序遍历
void InOrder(BTNode* pRoot);
 
//递归：后序遍历
void PostOrder(BTNode* pRoot);
 
//层序遍历
void LevelOrder(BTNode* pRoot);
 
//获取二叉树中节点个数
int GetBinTreeSize(BTNode* pRoot);
 
//获取二叉树中第k层节点个数
int GetKLevelNodeCount(BTNode* pRoot, int K);
 
//获取二叉树中叶子节点个数
int GetLeafCount(BTNode* pRoot);
 
//获取二叉树高度（深度）
int GetBinTreeHeight(BTNode* pRoot);
 
//检测值为x的元素是否在二叉树中，在则返回该节点的地址，否则返回NULL
BTNode* BinaryTreeFind(BTNode* pRoot, BTDataType x);
 
//二叉树的镜像
void MirrorNor(BTNode* pRoot);
void Mirror(BTNode* pRoot);
//判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* pRoot);

1、二叉树的创建

首先创建二叉树的根节点，然后递归创建根节点的左子树及右子树。此处还要用到新建节点的函数BuyBinTreeNode。

创建二叉树函数所需的参数包括存放数据的数组array、有效元素个数size、存放位