c语言 二叉树基本操作
#include "BinTree.h"
#include
#include
#include
#include #include "Queue.h"BTNode* BuyBinTeeNode(BTDataType data)
{
BTNode* pNewNode = (BTNode*)malloc(sizeof(BTNode));
if (NULL == pNewNode)
{
assert(0);
return NULL;
} pNewNode->_data = https://www.it610.com/article/data;
pNewNode->_pLeft = NULL;
pNewNode->_pRight = NULL;
return pNewNode;
}BTNode* _CreateBinTree(BTDataType* array, int size, int* index, BTDataType invalid)
{
BTNode* pRoot = NULL;
if (*index < size && invalid != array[*index])
{
// 根节点
pRoot = BuyBinTeeNode(array[*index]);
// 根的左子树
++(*index);
pRoot->_pLeft = _CreateBinTree(array, size, index, invalid);
// 根的右子树
++(*index);
pRoot->_pRight = _CreateBinTree(array, size, index, invalid);
} return pRoot;
}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);
}
}void LevelOrder(BTNode* pRoot)
{
Queue q;
if (NULL == pRoot)
return;
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);
} QueueDestroy(&q);
printf("\n");
}void Swap(BTNode** pLeft, BTNode** pRight)
{
BTNode* pTemp = *pLeft;
*pLeft = *pRight;
*pRight = pTemp;
}void MirrorNor(BTNode* pRoot)
{
Queue q;
if (NULL == pRoot)
return;
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);
} QueueDestroy(&q);
}void Mirror(BTNode* pRoot)
{
if (pRoot)
{Swap(&pRoot->_pLeft, &pRoot->_pRight);
Mirror(pRoot->_pLeft);
Mirror(pRoot->_pRight);
}
}BTNode* CreateBinTree(BTDataType* array, int size, BTDataType invalid)
{
int index = 0;
return _CreateBinTree(array, size, &index, invalid);
}int getSize(Node* root){
if(root==NULL){
return 0;
}
return getSize(root->left)+getSize(root->right)+1;
}int GetLeafCount(BTNode* pRoot)
{
if (NULL == pRoot)
return 0;
if (NULL == pRoot->_pLeft && NULL == pRoot->_pRight)
return 1;
return GetLeafCount(pRoot->_pLeft) + GetLeafCount(pRoot->_pRight);
}int GetKLevelNodeCount(BTNode* pRoot, int K)
{
if (NULL == pRoot || K <= 0)
return 0;
if (1 == K)
return 1;
return GetKLevelNodeCount(pRoot->_pLeft, K - 1) +
GetKLevelNodeCount(pRoot->_pRight, K - 1);
}BTNode* BinaryTreeFind(BTNode* pRoot, BTDataType x)
{
BTNode* pRet = NULL;
if (NULL == pRoot)
return NULL;
if (x == pRoot->_data)
return pRoot;
if (pRet = BinaryTreeFind(pRoot->_pLeft, x))
return pRet;
return BinaryTreeFind(pRoot->_pRight, x);
}void DestroyBinTree(BTNode** pRoot)
{
assert(pRoot);
if (*pRoot)
{
DestroyBinTree(&(*pRoot)->_pLeft);
DestroyBinTree(&(*pRoot)->_pRight);
free(*pRoot);
*pRoot = NULL;
}
}void TestBinTree()
{
char* str = "ABD$$$CE$$F";
BTNode* pRoot = CreateBinTree(str, strlen(str), '$');
Mirror(pRoot);
MirrorNor(pRoot);
printf("前序遍历结果：");
PreOrder(pRoot);
printf("\n");
printf("中序遍历结果：");
InOrder(pRoot);
printf("\n");
printf("后序遍历结果：");
PostOrder(pRoot);
printf("\n");
printf("层序遍历结果：");
LevelOrder(pRoot);
printf("K=3: %d\n", GetKLevelNodeCount(pRoot, 3));
if (BinaryTreeFind(pRoot, 'E'))
{
printf("E is in BTree!!!\n");
}
else
{
printf("E is not in BTree!!!\n");
}
DestroyBinTree(&pRoot);
} 【c语言 二叉树基本操作】
推荐阅读
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- 一起来学习C语言的字符串转换函数
- C语言字符函数中的isalnum()和iscntrl()你都知道吗
- C语言浮点函数中的modf和fmod详解
- C语言中的时间函数clock()和time()你都了解吗
- java中如何实现重建二叉树
- 种树郭橐驼传（文言句式+古今异义+词类活用+通假字）
- C语言学习|第十一届蓝桥杯省赛 大学B组 C/C++ 第一场
- 白杨树
- 08黑龙江迟淑荣弯柳树网络学院第五期学习赵宗瑞老师主讲的（传统文化与身心健康）教育体系心得体会