【数据结构】C语言实现链式二叉树
目录
一.链式二叉树新节点的创建
创建链式二叉树结点的结构体应该包括：存储数据的数据域data，以及存储左孩子结点地址的指针域left，存储右孩子结点地址的指针域right。
创建链式二叉树新结点和单链表中创建新结点的处理方法相同。
代码如下：
BTNode* buyNode(char x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
node->data = x;
node->left = node->right = NULL;
return node;
}二.链式二叉树的判空
链式二叉树的判空只需要返回根节点。
代码如下：
//判空
bool BTEmpty(BTNode* root)
{
return (!root);
}三.链式二叉树的先序遍历
链式二叉树先序遍历的思路是：先访问根节点，后递归访问左子树，递归访问右子树。
代码如下：
//前序遍历——根左右
void preOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
preOrder(root->left);
preOrder(root->right);
}四.链式二叉树的中序遍历
链式二叉树先序遍历的思路是：先递归访问左子树，再访问根节点，最后递归访问右子树。
代码如下：
//中序遍历--左根右
void inOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
inOrder(root->left);
printf("%c ", root->data);
inOrder(root->right);
}五.链式二叉树的后序遍历
链式二叉树先序遍历的思路是：先递归访问左子树，再递归访问右子树，最后访问根节点。
代码如下：
//后序遍历--左右根
void postOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
postOrder(root->left);
postOrder(root->right);
printf("%c ", root->data);
}六.链式二叉树的层序遍历
链式二叉树的层序遍历需要借助数据结构队列来实现。
思路：先把根节点入队列，再队列不为空情况下，去队头，出对头，将队头的非空的左右孩子入队列。
这是层序遍历的效果图：
代码如下：
//层序遍历
void leverOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
//取队头，出队头
BTNode* top = QueueFront(&q);
QueuePop(&q);
printf("%c ", top->data);
//将队头非空左右孩子入队列
if (top->left)
QueuePush(&q, top->left);
if (top->right)
QueuePush(&q, top->right);
}
QueueDestroy(&q);
}七.链式二叉树叶子节点的计算
叶子节点数 = 左子树的叶子节点数 + 右子树的叶子节点数。
叶子结点的判断条件是根存在且左右子树都为空。
代码如下：
// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return BinaryTreeLeafSize(root->left)
+ BinaryTreeLeafSize(root->right);
}八.链式二叉树左孩子节点数计算
根结点的左孩子节点数 = 左子树的左孩子节点数 + 右子树的左孩子节点数。
左孩子结点的判断条件是根存在且左子树不为空。
代码如下：
//左孩子节点数
int BinaryTreeLLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->left != NULL)
return BinaryTreeLLeafSize(root->left) + BinaryTreeLLeafSize(root->right)+1;
else
return BinaryTreeLLeafSize(root->left) + BinaryTreeLLeafSize(root->right);
}九.链式二叉树右孩子节点数计算
根结点的右孩子节点数 = 左子树的右孩子节点数 + 右子树的右孩子节点数。
左孩子结点的判断条件是根存在且左子树不为空。
代码如下：
//右孩子节点数
int BinaryTreeRLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->right != NULL)
return BinaryTreeRLeafSize(root->left) + BinaryTreeRLeafSize(root->right)+1;
else
return BinaryTreeRLeafSize(root->left) + BinaryTreeRLeafSize(root->right);
}十.链式二叉树节点数计算
节点数 = 根节点 + 左孩子节点数 + 右孩子节点数。
根节点要存在。
代码如下：
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return 1 + BinaryTreeSize(root->left)
+ BinaryTreeSize(root->right);
}十一.链式二叉树高度计算
二叉树的高度为左右子树中的较高子树（用三目操作符即可）再加上根结点自己的高度，即
二叉树的高度 = 左子树的高度 > 右子树的高度 ? 左子树高度 + 1 : 右子树高度 + 1
代码如下：
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int leftDep = BinaryTreeDepth(root->left);
int rightDep = BinaryTreeDepth(root->right);
return 1 + (leftDep > rightDep ? leftDep : rightDep);
}十二.链式二叉树查询某层节点个数
根结点的K层节点数 = 左子树的K层节点数 + 右子树的K层节点数。
判断条件是在K层且结点存在。
代码如下：
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BinaryTreeLevelKSize(root->left, k - 1)
+ BinaryTreeLevelKSize(root->right, k - 1);
}十三.链式二叉树查找节点
查找的思路很简单，就是递归二叉树来看是否存在值为需要查找的元素的节点。需要注意的是，如果左孩子存在该节点的话，右孩子就无需再递归下去了，直接返回该节点即可。所以要创造两个变量分别保存左子树和右子树的返回的值。
即，左右子树存在一个该节点，则节点就存在。
代码如下：
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* leftFind = BinaryTreeFind(root->left, x);
if (leftFind)
{
return leftFind;
}
BTNode* rightFind = BinaryTreeFind(root->right, x);
if (rightFind)
{
return rightFind;
}
return NULL;
}十四.判断是否为完全二叉树
判断二叉树是否为完全二叉树的代码与层序遍历相似，都需要借助数据结构队列，思路是利用完全二叉树的性质：若完全二叉树不为满二叉树,则空节点必定连续出现在最后一层的靠右部分。
因此利用层序遍历的思路，将所有结点的空孩子也入队，当完全二叉树遍历到第一个空结点时后面一定全为空结点，如果后面还有非空结点，那么这树就不是完全二叉树。
代码如下：
//判断树是否是完全二叉树
bool TreeComplete(BTNode* root)
{
//完全二叉树按层序走,非空结点一定是连续的(出过的结点的空子树也被无形中带入队了,不用担心结点在后面没有入队)
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front==NULL)
{
break;
}
else
{
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
}
//判断是不是完全二叉树(即出队过程中剩余元素有没有非空的结点)
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
//front不为空,就为真,就返回假
if (front)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}十五.实现翻转链式二叉树
翻转二叉树 = 翻转左子树 + 翻转右子树。
和销毁二叉树的思路一致，采用后序遍历的思想，最后翻转根节点的左右子树。
//翻转二叉树
BTNode* InvertTree(BTNode* root)
{
if (root == NULL)
return NULL;
BTNode* tmp = InvertTree(root->right);
root->right = InvertTree(root->left);
root->left = tmp;
return root;
}十六.链式二叉树的销毁
二叉树的销毁采用后序遍历的思想，即：先销毁左右子树，再销毁根节点
代码如下：
// ⼆叉树销毁--左右根
void BinaryTreeDestory(BTNode** root)
{
if (*root == NULL)
{
return;
}
BinaryTreeDestory(&((*root)->left));
BinaryTreeDestory(&((*root)->right));
free(*root);
*root = NULL;
}更多推荐
24
0- 0
已为社区贡献1条内容
所有评论(0)