【数据结构】用最简洁的内容带你了解二叉树的链式结构

admin管理员组

文章数量:1487745

【数据结构】用最简洁的内容带你了解二叉树的链式结构

前言

我们知道二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。前面我们已经学习了顺序结构堆来表示完全二叉树，这次我们将认识第二种存储结构链式结构来实现二叉树。

1. 链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链。后面课程学到高阶数据结构如：红黑树等，会用到三叉链。

2. 实现链式结构的二叉树

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

代码语言：javascript代码运行次数：0运行复制

typedef int BTDataType;
// 二叉链
typedef struct BinaryTreeNode
{
	struct BinTreeNode* left; // 指向当前结点左孩子
	struct BinTreeNode* right; // 指向当前结点右孩子
	BTDataType val; // 当前结点值域
}BTNode;

二叉树的创建方式比较复杂，为了更好的步入到二叉树内容中，这里我们先手动创建一棵链式二叉树

代码语言：javascript代码运行次数：0运行复制

BTNode* BuyBTNode(int val)
{
	BTNode * newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->val = val;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}
BTNode * CreateTree()
{
	BTNode * n1 = BuyBTNode(1);
	BTNode * n2 = BuyBTNode(2);
	BTNode * n3 = BuyBTNode(3);
	BTNode * n4 = BuyBTNode(4);
	BTNode * n5 = BuyBTNode(5);
	BTNode * n6 = BuyBTNode(6);
	BTNode * n7 = BuyBTNode(7);
	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;
	n5->left = n7;
	return n1;
}

回顾二叉树的概念，二叉树分为空树和非空二叉树，非空二叉树由根结点、根结点的左子树、根结点的右子树组成的

根结点的左子树和右子树分别又是由子树结点、子树结点的左子树、子树结点的右子树组成的，因此二叉树定义是递归式的，之后有关链式二叉树的操作中基本都是按照该概念实现的。

结语

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下。

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-10-17，如有侵权请联系 cloudcommunity@tencent 删除前往查看数据结构链表指针存储二叉树

本文标签： 数据结构用最简洁的内容带你了解二叉树的链式结构