【数据结构】二叉树链接结构基本操作

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

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

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

创建二叉树、拷贝二叉树、销毁二叉树、二叉树遍历（前序、中序、后续、层序）、获取二叉树中节点个数、获取二叉树中第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、存放位置索引index以及无效符号invalid。在这里为了方便用户使用，多加了一层封装，使得用户调用层面只需要传入三个参数即可。

BTNode* BuyBinTreeNode(BTDataType data) { BTNode* pNewNode = (BTNode*)malloc(sizeof(BTNode)); if (pNewNode == NULL) { assert(0); return NULL; } pNewNode->_data = data; pNewNode->_pLeft = NULL; pNewNode->_pRight = NULL; return pNewNode; } BTNode* _CreatBinTree(BTDataType* array, int size, int* index,BTDataType invalid) { BTNode* pRoot = NULL; if (*index < size && invalid != array[*index]) { //根结点 pRoot = BuyBinTreeNode(array[*index]); //根的左子树 ++(*index); pRoot->_pLeft = _CreatBinTree(array, size, index,invalid); //根的右子树 ++(*index); pRoot->_pRight = _CreatBinTree(array, size, index,invalid); } return pRoot; } BTNode* CreatBinTree(BTDataType* array, int size, BTDataType invalid) { int index = 0; return _CreatBinTree(array, size, &index,invalid); }

2、二叉树的拷贝

也是采用递归的方法实现拷贝。

BTNode* CopyBinTree(BTNode* pRoot) { BTNode* newpRoot = NULL; if (pRoot == NULL) return NULL; newpRoot = BuyBinTreeNode(pRoot->_data); newpRoot->_pLeft = CopyBinTree(pRoot->_pLeft); newpRoot->_pRight = CopyBinTree(pRoot->_pRight); return newpRoot; }

3、二叉树的销毁

为了防止内存泄漏问题发生，在整个程序结束前应当将二叉树销毁掉，也是采用的递归的方法进行销毁的，不过需要注意的是因为在销毁完二叉树后我们需要将根结点置空，要改变其中指针的指向，所以需要传入一个二级指针。

void DestoryBinTree(BTNode** pRoot) { if (*pRoot) { DestoryBinTree(&(*pRoot)->_pLeft); DestoryBinTree(&(*pRoot)->_pRight); free(*pRoot); *pRoot = NULL; } }

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

void PreOrder(BTNode* pRoot) {//前序遍历 if (pRoot) { printf("%c",pRoot->_data); PreOrder(pRoot->_pLeft); PreOrder(pRoot->_pRight); } } void InOrder(BTNode* pRoot) {//中序遍历 if (pRoot) { InOrder(pRoot->_pLeft); printf("%c",pRoot->_data); InOrder(pRoot->_pRight); } } void PostOrder(BTNode* pRoot) {//后序遍历 if (pRoot) { PostOrder(pRoot->_pLeft); PostOrder(pRoot->_pRight); printf("%c", pRoot->_data); } }

5、二叉树的层序遍历

借助队列，实现二叉树的层序遍历（因为C语言中没有现成的队列的方法，所以需要添加一个队列），具体步骤：

while循环（队列非空）

取队头元素。遍历该元素。如果左孩子存在，将左孩子入队列。如果右孩子存在，将右孩子入队列。删除队头元素。 void LevelOrder(BTNode* pRoot) { if (pRoot == NULL) return; Queue q;//定义一个队列 QueueInit(&q); QueuePush(&q, pRoot);//将根结点入队列 while (!QueueEmpty(&q)) { BTNode* pCur = QueueFront(&q);//取队头元素 printf("%c ", pCur->_data); if (pCur->_pLeft) QueuePush(&q, pCur->_pLeft);//若左孩子存在，则入队列 if (pCur->_pRight) QueuePush(&q, pCur->_pRight);//若右孩子存在，则入队列 QueuePop(&q); } QueueDestory(&q); printf("\n"); }

6、获取二叉树中节点个数、第K层节点个数、叶子节点个数

根据二叉树的概念以及所要求节点的特点，采用递归的方法实现。

int GetBinTreeSize(BTNode* pRoot) { if (pRoot == NULL) return 0; return GetBinTreeSize(pRoot->_pLeft) + GetBinTreeSize(pRoot->_pRight) + 1; } int GetKLevelNodeCount(BTNode* pRoot, int K) { if (pRoot == NULL||K<=0) return 0; if (K == 1) return 1; return GetKLevelNodeCount(pRoot->_pLeft, K - 1) + GetKLevelNodeCount(pRoot->_pRight, K - 1); } int GetLeafCount(BTNode* pRoot) { if (pRoot == NULL) return 0; if (pRoot->_pLeft == NULL && pRoot->_pRight == NULL) return 1; return GetLeafCount(pRoot->_pLeft) + GetLeafCount(pRoot->_pRight); }

7、获取二叉树的高度（深度）

递归的方法：根结点的左子树的高度与根结点的右子树的高度中较大者+1。

int GetBinTreeHeight(BTNode* pRoot) { if (pRoot == NULL) return 0; int maxleft = GetBinTreeHeight(pRoot->_pLeft); int maxright = GetBinTreeHeight(pRoot->_pRight); if (maxleft > maxright) return 1 + maxleft; return 1 + maxright; }

8、查找值为x的节点在二叉树中是否存在

BTNode* BinaryTreeFind(BTNode* pRoot, BTDataType x) { if (pRoot == NULL) return NULL; if (pRoot->_data == x) return pRoot; BTNode* pTemp = NULL; if (pTemp = BinaryTreeFind(pRoot->_pLeft, x)) return pTemp; return BinaryTreeFind(pRoot->_pRight, x); }

9、二叉树镜像（递归与非递归的方式）

非递归的方式与层序遍历的实现很相似，都需要借助队列，不同的是需要增加一个交换左右子树的步骤。

void Swap(BTNode** pLeft, BTNode** pright) { BTNode* pTemp = *pLeft; *pLeft = *pright; *pright = pTemp; } void Mirror(BTNode* pRoot) { if (pRoot) { Swap(&pRoot->_pLeft, &pRoot->_pRight); Mirror(pRoot->_pLeft); Mirror(pRoot->_pRight); } } void MirrorNor(BTNode* pRoot) { Queue q; QueueInit(&q); QueuePush(&q, pRoot); while (!QueueEmpty(&q)) { BTNode* pCur = QueueFront(&q); Swap(&pCur->_pLeft, &pCur->_pRight); if (pCur->_pLeft) QueuePush(&q, pCur->_pLeft); if (pCur->_pRight) QueuePush(&q, pCur->_pRight); QueuePop(&q); } }

10、判断二叉树是否为完全二叉树

需要借助队列来完成，分析如下：

首先空树也是一个完全二叉树。利用队列先将二叉树根结点入队列，只要当前不为空，就出队列该节点，并入队列该节点的左右孩子，若有孩子不存在，则入队列NULL。若当前节点为空，则判断队列是否为空，若队列为空，则是完全二叉树。若队列不为空，则继续出队，若当前出队的节点是NULL，则该树不是完全二叉树。 int BinaryTreeComplete(BTNode* pRoot) { if (pRoot == NULL) return 1; Queue q; QueueInit(&q); QueuePush(&q, pRoot); while (pRoot != NULL) {//若节点不为空，就进行出队列，并入队节点的左右孩子 pRoot = QueueFront(&q); QueuePop(&q); if (pRoot != NULL) { QueuePush(&q, pRoot->_pLeft); QueuePush(&q, pRoot->_pRight); } } while (!QueueEmpty(&q)) {//节点为NULL但队列不空时 pRoot = QueueFront(&q); QueuePop(&q); if (pRoot == NULL)//在非空节点后又出现了NULL节点，说明不是完全二叉树 return -1; } return 1; }