【数据结构】——链式二叉树的实现（赋源码）

用户11286421

发布于 2024-09-23 20:11:15

890

发布于 2024-09-23 20:11:15

文章被收录于专栏：学习

链式二叉树

⽤链表来表⽰⼀棵⼆叉树，即⽤链来指示元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址，其结构如下：

typedef int BTDataType; //方便替换类型
typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* left;//左结点
    struct BinaryTreeNode* right;//右结点
}BTNode;

回顾⼆叉树的概念，⼆叉树分为空树和非空⼆叉树，非空⼆叉树由根结点、根结点的左⼦树、根结点的右子树组成的根结点的左子树和右子树分别⼜是由子树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的，因此⼆叉树定义是递归式的,后序链式⼆叉树的操作中基本都是按照该概念实现的。

二叉树的遍历方式

前序遍历

前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发⽣在遍历其左右⼦树之前

| 访问顺序为：根结点、左子树、右子树

void PreOrder(BTNode* root)
{
 if (root == NULL)
 {
 printf("N ");
 return;
 }
 printf("%d ", root->val);
 PreOrder(root->left);
 PreOrder(root->right);
}

中序遍历

中序遍历(Inorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之中（间）

| 访问顺序为：左子树、根结点、右子树

void InOrder(BTNode* root)
{
 if (root == NULL)
 {
 printf("N ");
 return;
 }
 InOrder(root->left);
 printf("%d ", root->val);
 InOrder(root->right);
}

后序遍历

后序遍历(Postorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之后

| 访问顺序为：左⼦树、右⼦树、根结点

void PostOrder(BTNode* root)
{
 if (root == NULL)
 {
 printf("N ");
 return;
 }
 InOrder(root->left);
 InOrder(root->right);
 printf("%d ", root->val);
}

计算以下树的前中后遍历方式的结果：

答案：前序遍历结果：1 2 3 4 5 6 中序遍历结果：3 2 1 5 4 6 后序遍历结果：3 1 5 6 4 1

以前序遍历举例

函数递归栈帧图

二叉树实现的所需函数

// ⼆叉树结点个数 
int BinaryTreeSize(BTNode* root);

// ⼆叉树叶⼦结点个数 
int BinaryTreeLeafSize(BTNode* root);

// ⼆叉树第k层结点个数 
int BinaryTreeLevelKSize(BTNode* root, int k);

//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root);

// ⼆叉树查找值为x的结点 
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);

// 层序遍历
void LevelOrder(BTNode* root);

// 判断⼆叉树是否是完全⼆叉树
bool BinaryTreeComplete(BTNode* root);

二叉树结点个数

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

二叉树叶子结点个数

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);
}

⼆叉树第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);
}

二叉树的深度/高度

int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftdep = BinaryTreeDepth(root->left);
	int rightdep = BinaryTreeDepth(root->right);
	return leftdep > rightdep ? leftdep+1 : rightdep+1;
}

二叉树查找值为x的结点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}

	BTNode* left = BinaryTreeFind(root->left, x);
	if (left)
	{
		return left;
	}
	BTNode* right = BinaryTreeFind(root->right, x);
	if (right)
	{
		return right;
	}
	return NULL;
}

二叉树销毁

void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}

	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);
	free(*root);
	*root = NULL;
}

层序遍历

需要借助队列进行实现

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，打印
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);
		QueuePop(&q);
		//队头节点的左右孩子入队列
		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	//队列为空
	QueueDestroy(&q);
}

判断二叉树是否是完全二叉树

需要借助队列进行实现

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	//队列不一定为空
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

二叉树OJ在线练习

单值二叉树

. - 力扣（LeetCode）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 typedef struct TreeNode TreeNode;
bool isUnivalTree(struct TreeNode* root) {
    if(root == NULL)
    {
        return true;
    }
    if(root->left && root->left->val != root->val)
    {
        return false;
    }
    if(root->right && root->right->val != root->val)
    {
        return false;
    }

    return isUnivalTree(root->right) && isUnivalTree(root->left);
}

相同的树

. - 力扣（LeetCode）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 typedef struct TreeNode TreeNode;
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    //都为空
    if(q == NULL && p == NULL)
    {
        return true;
    }
    //其一为空
    if(p == NULL || q == NULL)
    {
        return false;
    }
    //都不为空
    if(p->val != q->val)
    {
        return false;
    }
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

 typedef struct TreeNode TreeNode;
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    //都为空
    if(q == NULL  && p == NULL)
    {
        return true;
    }
    //其一为空
    if(p == NULL || q == NULL)
    {
        return false;
    }
    //都不为空
    if(p->val != q->val)
    {
        return false;
    }
    return isSameTree(p->left,q->right) && isSameTree(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root) {
    return isSameTree(root->left,root->right);
}

另一棵树的子树

. - 力扣（LeetCode）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    //都为空
    if(q == NULL && p == NULL)
    {
        return true;
    }
    //其一为空
    if(p == NULL || q == NULL)
    {
        return false;
    }
    //都不为空
    if(p->val != q->val)
    {
        return false;
    }
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root == NULL)
    {
        return false;
    }
    //相同就不用继续下去
    if(isSameTree(root,subRoot))
    {
        return true;
    }
    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

二叉树前序遍历

. - 力扣（LeetCode）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
typedef struct TreeNode TreeNode;
 int Treesize(TreeNode *root)
 {
    if(root == NULL)
    {
        return 0;
    }
    return 1 + Treesize(root->left) + Treesize(root->right);
 }
void _preorderTraversal(TreeNode* root,int* arr,int *pi)
 {
    if(root == NULL)
    {
        return;
    }
    //根左右
    arr[(*pi)++] = root->val;
    _preorderTraversal(root->left,arr,pi);
    _preorderTraversal(root->right,arr,pi);
 }
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = Treesize(root);

    int* arr =(int*) malloc(sizeof(int) * (*returnSize));
    int i = 0;
    _preorderTraversal(root,arr,&i);
    return arr;
}

中序遍历以及后序遍历链接如下：其解答过程同前序遍历几乎一模一样

中序遍历 . - 力扣（LeetCode）

后序遍历 . - 力扣（LeetCode）

二叉树的遍历

二叉树遍历_牛客题霸_牛客网

#include <stdio.h>

typedef struct BinaryTreeNode
{
    char val;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(char x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));

    newnode->val = x;
    newnode->right = newnode->left = NULL;
    return newnode;
}
BTNode* createTree(char* arr,int*pi)
{
    if(arr[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root = BuyNode(arr[(*pi)++]);
    root->left = createTree(arr, pi);
    root->right = createTree(arr, pi);

    return root;
}

void INOrder(BTNode * root)
{
    if(root == NULL)
    {
        return;
    }
    INOrder(root->left);
    printf("%c ",root->val);
    INOrder(root->right);
}
int main() {
    char arr[100];
    scanf("%s",arr);


    int pi = 0;
    BTNode* root = createTree(arr,&pi);

    INOrder(root);
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-09-09，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树