1. Toy模板网首页
  2. > Toy博客

【数据结构】二叉树（详细）

9月前 作者：南木_N 分类：Toy博客 阅读(36) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】二叉树（详细）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.树

学习二叉树，首先得了解树，从树的基本概念出发。

1.1定义

树是n个节点的的有限集合，是一种非线性结构。当n=0时称为空树，对于非空树T：（1）只有一个根结点（root）；（2）除根节点外的其余结点可分为m个互不相交的有限集T1，T2，……，Tm，其中每个集合本身又是一棵树，称为根的子树。
数据结构二叉树,数据结构,算法

1.2基本术语

  • 结点：树的一个独立单元，包含一个数据元素或者指向其子树的分支。如图中的A，B，C等。
  • 结点的度：结点拥有的子树数称为结点的度（也可以理解为这个结点有多少个孩子）。如A的度是2，B的度是3，D的度是0。
  • 树的度：树的各个结点的度的最大值。如图中的树的度为3。
  • 叶子结点（或者终端结点）：度为0的结点。如图中的D，E，F，G。
  • 非终端结点：度不为0的结点。除根结点外，非终端结点也称为内部结点。如图中B，C。
  • 孩子结点（或者子节点）：一个结点的子树的根结点称为该结点的孩子结点。如图中B和C是A的子结点。
  • 双亲结点（或者父结点）：一个结点有一个子结点，该结点称为其子结点的父结点。如图中，A是B和C的双亲结点。
  • 兄弟结点：同一双亲的孩子之间互称兄弟。如图中B和C是兄弟结点。
  • 祖先：从根结点到该结点所经分支上的所有结点。如D的祖先是A和B。
  • 子孙：以某结点为根的子树的任一结点都称为该结点的子孙。如D，E，F是B的子孙。
  • 层次：从根结点开始，根结点为第一层，根的孩子为第二层，以此类推直到最后一层。如A是第一层，B是第二层，D是第三层。
  • 深度：树中结点的最大层次。如A这棵树的深度是3。
  • 森林：由m棵互不相交的树构成的集合。如去掉A结点，B和C这两棵子树就是森林。

这么多概念，但常用的只有结点的度、双亲结点、叶子结点、树的层次、树的高度、结点的祖先和子孙。

数据结构二叉树,数据结构,算法

1.3树形结构和线性结构

树形结构 线性结构
树的根结点没有双亲结点 线性表的第一个元素没有前驱
树的叶子结点没有子结点 线性表的最后一个元素没有后继
树的内部结点有一个前驱和多个后继 线性表的其余元素只有一个前驱和一个后继

1.4树的存储结构

树有多种存储结构：双亲表示法、孩子链表表示法、孩子兄弟表示法等。由于今天的猪脚是二叉树，所以在这里简单介绍下双亲表示法和孩子兄弟表示法。

1.4.1双亲表示法

//结点
#define MAXSIZE 100
typedef int ElemType;
typedef struct
{
	ElemType x;//结点的数据
	int parent;//结点的双亲结点的下标
}PTNode;
typedef struct
{
	PTNode a[MAXSIZE];//结点数组
	int size;//结点个数
}PTree;

数据结构二叉树,数据结构,算法

1.4.2孩子兄弟表示法

//结点
typedef int ElemType;
typedef struct CBTreeNode
{
	ElemType x;//数据
	struct CBTreeNode* firstchild;//指向结点的左孩子，也就是第一个孩子
	struct CBTreeNode* Nextbrother;//指向同一父结点的兄弟
}CBTNode;

数据结构二叉树,数据结构,算法

2.二叉树

2.1定义

二叉树是n（n>=0）个结点的有限集合。当n=0时为空树，当n不为0时，二叉树有以下特点：1.每个结点的度不超过2（可以理解为二孩政策下的结点最多只能有两个孩子）；
2.每个结点的左子树和右子树顺序不能颠倒，所以二叉树是有序树。数据结构二叉树,数据结构,算法

2.2特殊二叉树

  1. 满二叉树：每一层结点数都达到最大，那么它就是满二叉树。如第1层最多有2 ^0个结点，第2层最多有 2 ^1个结点，则第k层最多有2 ^(k-1)个结点，假设这棵满二叉树有k层，那么它总共有2 ^0+2 ^1+……+2 ^(k-1) = 2 ^k-1个结点。
  2. 完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。（简介版：完全二叉树的前k-1层是满二叉树，最后一层从左到右依次连续）

数据结构二叉树,数据结构,算法

2.3性质

  1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点。
  2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1。
  3. 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
    证明
    数据结构二叉树,数据结构,算法
  4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log (n+1)(ps:log是以2
    为底，n+1为对数)。
    证明
    数据结构二叉树,数据结构,算法
  5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
    （1）. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
    （2）. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
    （3）.若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子
    数据结构二叉树,数据结构,算法

2.4存储结构

2.4.1顺序存储

二叉树的顺序存储是用数组存储的，其中结点之间的关系用下标来表示。即二叉树的逻辑结构是树，但是其物理结构是数组。
数据结构二叉树,数据结构,算法
但这种存储结构会造成空间浪费，适用于完全二叉树和满二叉树。
数据结构二叉树,数据结构,算法
但这个结构却可以来实现一个很牛逼的排序：堆排序。

2.4.2链式存储结构

链式存储结构可以解决顺序存储结构浪费空间的问题，二叉树的链式存储表示有二叉链表、三叉链表、双亲链表、线索链表等。这里重点讲二叉链表。

//二叉树的节点
typedef int DataType;
typedef struct BinaryTreeNode
{
	DataType val;
	struct BinaryTreeNode* left;//指向左孩子的指针
	struct BinaryTreeNode* right;//指向右孩子的指针
}BTNode;

数据结构二叉树,数据结构,算法

下面讲二叉树的基本操作。

3.二叉树的基本操作

遍历是指每个结点被访问一次且仅被访问一次。二叉树有一个前驱和两个后继，这注定其遍历不同于线性结构的遍历。二叉树的遍历有前序遍历、中序遍历，后序遍历，层序遍历。

3.1前序遍历（先序遍历）

  1. 概念
    前序遍历：先访问根节点，再访问左子树和右子树。
    数据结构二叉树,数据结构,算法

由图可知，树的前序遍历是递归的，所以可以用递归来实现。

  1. 代码实现
//先手动创建一个二叉树
BTNode* BuyNode(DataType x)//申请一个结点
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		return NULL;
	}
	newnode->left = newnode->right = NULL;
	newnode->val = x;
	return newnode;
}
BTNode* CreateBT()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;//返回根结点
}
//前序遍历
void PreOrder(BTNode* root)
{
	//思路：先访问根结点，再访问左子树和右子树
	if (root==NULL)
	{
		printf("NULL ");
		return;
	}
	//先访问根结点
	printf("%d ", root->val);
	//再访问左右子树
	PreOrder(root->left);
	PreOrder(root->right);
}
int main()
{
	BTNode* root = CreateBT();
	PreOrder(root);
	return 0;
}

答案
数据结构二叉树,数据结构,算法

3.2中序遍历

  1. 概念
    中序遍历：先访问左子树，再访问根节点，最后访问右子树。
    数据结构二叉树,数据结构,算法
    同样可以用递归实现
  2. 代码实现
// 二叉树中序遍历
void InOrder(BTNode* root)
{
	//思路：先访问左子树，再访问根节点，最后访问右子树
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	//先访问左子树
	InOrder(root->left);
	//再访问根节点
	printf("%d ", root->val);
	//最后访问右子树
	InOrder(root->right);
}

答案
数据结构二叉树,数据结构,算法

3.3后序遍历

  1. 概念
    后序遍历：先访问左子树，再访问右子树，最后访问根节点。
    数据结构二叉树,数据结构,算法
  2. 代码实现
//后序遍历
void PostOrder(BTNode* root)
{
	//思路：先访问左子树，再访问右子树，最后访问根结点
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

答案
数据结构二叉树,数据结构,算法

3.4层序遍历

  1. 概念
    层序遍历：从上到下，从左到右，依次访问。
    数据结构二叉树,数据结构,算法
  2. 代码实现
// 层序遍历
void LevelOrder(BTNode* root)
{
	//思路：用队列实现，出队一层，入队下一层
	Queue q;
	QInit(&q);
	//如果非空就直接入队
	if (root)
	{
		QPush(&q, root);
	}
	//队列中只入队非空元素
	while (!QEmpty(&q))
	{
		//先出队
		BTNode* tmp = QPop(&q);
		printf("%d ", tmp->val );
		//再判断左右子树是否为空
		if (tmp->left)
		{
			QPush(&q, tmp->left);
		}
		if (tmp->right)
		{
			QPush(&q, tmp->right);
		}
	}
	QDestroy(&q);
}

答案
数据结构二叉树,数据结构,算法

4.二叉树练习

样例
数据结构二叉树,数据结构,算法

  1. 求二叉树的节点个数
// 二叉树节点个数

//法一：
int size = 0;//也可以使用静态变量
void TreeSize(BTNode* root)
{
	//思路：只要节点不为空，就记录一次
	if (root == NULL)
	{
		return 0;
	}
	++size;
	TreeSize(root->left);
	TreeSize(root->right);
}


//法二：
int BinaryTreeSize(BTNode* root)
{
	//思路：二叉树的节点个数 = 左子树的节点个数 + 右子树的节点个数
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1 ;
}

注意
但是法一有个弊端：size是全局（或静态）变量，每次调用都得初始化一次。
答案
数据结构二叉树,数据结构,算法

  1. 求二叉树的叶子节点个数
// 二叉树叶子节点个数
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);
}

答案
数据结构二叉树,数据结构,算法

  1. 求二叉树的高度
// 二叉树的高度(深度)
int TreeHeight(BTNode* root)
{
	// 思路：二叉树的高度 = 左子树的高度和右子树的高度的最大值 + 1
	if (root == NULL)
	{
		return 0;
	}
	int left = TreeHeight(root->left);
	int right = TreeHeight(root->right);
	return left > right ? left + 1 : right + 1;
}

答案
数据结构二叉树,数据结构,算法

  1. 求第k层节点个数
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	//思路：
	//对于第一层，是求第k层节点个数（k）
	//对于第二层，是求第k-1层节点个数（k-1）
	//……
	//对于第k层，是求这一层节点个数（1）
	//第k层节点个数 = 左子树第k层节点个数 + 右子树第k层节点个数
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

答案
数据结构二叉树,数据结构,算法

  1. 判断是否是单值二叉树（LeetCode965）OJ链接
    单值二叉树：二叉树的每个节点都有相同的值
// 判断是否是单值二叉树
bool isUnivalTree(BTNode* root)
{
	//思路：比较根节点与左右子树是否相等，不相等就返回false，相等就判断左右子树是否是单值二叉树
	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->left) && isUnivalTree(root->right);
}

答案
数据结构二叉树,数据结构,算法

  1. 查找一个值为x的节点
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, DataType x)
{
	//思路：先判断根的值是否与x相等，相等就返回根，
	//不等就判断是否与左子树相等，相等就返回
	//不等就判断是否与右子树相等，相等就返回，不等就返回NULL
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == x)
	{
		return root;
	}
	BTNode*tmp = BinaryTreeFind(root->left, x);
	if (tmp != NULL)
	{
		return tmp;
	}
	tmp = BinaryTreeFind(root->right, x);
	if (tmp != NULL)
	{
		return tmp;
	}
	return NULL;
}
  1. 判断两棵二叉树是否相等（LeetCode100）OJ链接 
// 判断两棵二叉树是否相等
bool isSameTree(BTNode* p, BTNode* q)
{
	//思路：先判断根结点是否相等，再判断左子树是否相等，最后判断右子树是否相等
	if (p == NULL && q == 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);
}

答案
数据结构二叉树,数据结构,算法

  1. 判断是否是对称二叉树（LeetCode101）OJ链接 
bool isLefRig(BTNode* p1, BTNode* p2)//功能类似于判断两棵二叉树是否相等
{
	if (p1 == NULL && p2 == NULL)
	{
		return true;
	}
	if (p1 == NULL || p2 == NULL)
	{
		return false;
	}
	if (p1->val != p2->val)
	{
		return false;
	}
	return isLefRig(p1->left, p2->right) && isLefRig(p1->right, p2->left);
}
bool isSymmetric(BTNode* root)
{
·	//思路：写一个辅助函数，功能与判断二叉树是否相等类似
	if (root == NULL)
	{
		return true;
	}
	return isLefRig(root->left, root->right);
}

答案
数据结构二叉树,数据结构,算法

  1. 二叉树的前序遍历（LeetCode144）OJ链接 
int TreeSize(struct TreeNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void PreOrder(struct TreeNode* root, int* a, int* i)
{
	if (root == NULL)
	{
		return;
	}
	//先对根结点进行操作，再对左右子树进行操作
	a[(*i)++] = root->val;
	PreOrder(root->left, a, i);
	PreOrder(root->right, a, i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
	//我们需要知道这棵树的大小，再来动态申请
	int size = TreeSize(root);
    *returnSize = size;
	int* ret = (int*)malloc(sizeof(int) * size);
	//写一个函数来实现遍历，不要在这个函数遍历，因为遍历需要递归，所以TreeSize会重复调用
	int i = 0;//用来记录数组的下标，方便存储数据
	PreOrder(root, ret, &i);//为什么要传下标的地址？因为要对下标进行修改
	return ret;
}

答案
数据结构二叉树,数据结构,算法

  1. 二叉树的中序遍历（LeetCode94）OJ链接 
int TreeSize(struct TreeNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void InOrder(struct TreeNode* root, int* a, int* i)
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->left, a, i);
    a[(*i)++] = root->val;
	InOrder(root->right, a, i);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
	//我们需要知道这棵树的大小，再来动态申请
	int size = TreeSize(root);
    *returnSize = size;
	int* ret = (int*)malloc(sizeof(int) * size);
	//写一个函数来实现遍历，不要在这个函数遍历，因为遍历需要递归，所以TreeSize会重复调用
	int i = 0;//用来记录数组的下标，方便存储数据
	InOrder(root, ret, &i);//为什么要传下标的地址？因为要对下标进行修改
	return ret;
}

结果
数据结构二叉树,数据结构,算法

  1. 二叉树的后序遍历（LeetCode145）OJ链接 
int BinaryTreeSize(struct TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
void PostOrder(struct TreeNode* root, int* ret, int* pi)
{
	if (root == NULL)
	{
		return 0;
	}
    PostOrder(root->left, ret, pi);
	PostOrder(root->right, ret, pi);
    ret[(*pi)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
	int size = BinaryTreeSize(root);
	*returnSize = size;
	int* ret = (int*)malloc(sizeof(int) * size);//用来存放前序序列
	int i = 0;
	PostOrder(root, ret, &i);
	return ret;
}

结果
数据结构二叉树,数据结构,算法

  1. 判断一棵树是否是另一棵树的子树
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
	//思路：用当前节点所在树与sub进行比较，相等返回真，不相等用当前根结点的左子树比较，再不相等用右子树比较
	if (root == NULL)
	{
		return false;
	}
	if (isSameTree(root, subRoot))
	{
		return true;
	}
	return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

结果
数据结构二叉树,数据结构,算法

  1. 判断是否是完全二叉树
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	//思路：利用层序遍历，将完全二叉树的所有节点全部入队，
	//当出队时节点为NULL，如果为完全二叉树，则队列中的其余节点都是NULL，
	//所以最后判断队列中的节点是否不为NULL，即可判断
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode*tmp = QueueFront(&q);
		QueuePop(&q);
		if (tmp == NULL)
		{
			break;//当遇到NULL，就跳出循环
		}
		else
		{
			QueuePush(&q, tmp->left);//如果为NULL也入队
			QueuePush(&q, tmp->right);
		}
	}
	while (!QueueEmpty(&q))
	{
		BTNode* tmp = QueueFront(&q);
		QueuePop(&q);
		if (tmp)
		{
			QueueDestroy(&q);//注意销毁队列，防止内存泄漏
			return false;
		}
	}
	QueueDestroy(&q);//等下学习怎么销毁，先记住它有销毁的功能
	return true;
}
int main()
{
	char arr[100] = { 0 };
	scanf("%s", arr);
	int i = 0;
	int size = strlen(arr);
	BTNode* root = CreateBT(arr, &i,size);
	InOrder(root);
}

5.二叉树的创建和销毁

前面的二叉树是我们手动创建的，现在学习了前序、中序、后序遍历，就可以利用它们来创建和销毁二叉树。

5.1二叉树的创建

二叉树遍历OJ链接

BTNode* BuyNode(DataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		return NULL;
	}
	newnode->left = NULL;
	newnode->right = NULL;
	newnode->val = x;
	return newnode;
}
BTNode* CreateBT(char* arr, int* pi,int size)
{	//ABC##DE#G##F###
	if (*pi == size)//递归的停止条件
	{
		return NULL;
	}
	if (arr[*pi] == '#')
	{
		(*pi)++;//遇到#,不要忘记跳过
		return NULL;
	}
	BTNode* root = BuyNode(arr[(*pi)++]);
	root->left = CreateBT(arr, pi,size);
	root->right = CreateBT(arr, pi,size);
	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] = { 0 };
	scanf("%s", arr);
	int i = 0;
	int size = strlen(arr);
	BTNode* root = CreateBT(arr, &i,size);
	InOrder(root);
}

结果
数据结构二叉树,数据结构,算法文章来源地址https://www.toymoban.com/news/detail-837934.html

5.2二叉树的销毁

// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
	//如果用前序或者中序遍历销毁二叉树会导致内存泄漏（找不到左右子树）
	//所以用后序遍历销毁二叉树
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
	root == NULL;
}

到了这里，关于【数据结构】二叉树（详细）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构之二叉树（详细版）

    数据结构之二叉树（详细版）

            二叉树作为数据结构的一种，尤为重要，下面是对二叉树的详细讲解。想要了解二叉树，首先要了解 二叉树的基本概念，以及创建二叉树的结构，再深层点，遍历二叉树的前序中序和后续，其次是层序，后面将会讲解如何计算二叉树的高和叶结点 等等。        

    2024年02月03日
    浏览(46)
  • 数据结构--二叉树遍历(详细过程)

    数据结构--二叉树遍历(详细过程)

    目录 一、什么是二叉树？ 二、二叉树的遍历 1. 先序遍历 2. 中序遍历  3.后序遍历 4. 遍历的推导 三、重要的事情 1. 二叉树：一种树形结构，特点是每个 结点至多只有两颗子树 ，并且子树有左右之分，次序不能颠倒。 特殊形态的二叉树：满二叉树和完全二叉树； 2. 满二叉树

    2024年04月17日
    浏览(39)
  • 二叉树（上）——“数据结构与算法”

    二叉树（上）——“数据结构与算法”

    各位CSDN的uu们好呀，好久没有更新我的数据结构与算法专栏啦，今天，小雅兰继续来更新二叉树的内容，下面，让我们进入链式二叉树的世界吧！！！ 二叉树链式结构的实现  二叉树链式结构的实现 普通的二叉树的增删查改是没有价值的！！！ 只有搜索二叉树的增删查改才

    2024年02月15日
    浏览(45)
  • 二叉树【数据结构】【超详细，一学就会】

    二叉树【数据结构】【超详细，一学就会】

    目录 📖1.什么是二叉树？ 🌴2.满二叉树和完全二叉树  ⛳2.二叉树的性质 🔥3.二叉树的创建与遍历 3.1 创建二叉树 3.2 前中后序遍历——递归和非递归 🏹4.二叉树的实现 1️⃣获取树中节点的个数 2️⃣获取叶子节点的个数 3️⃣获取第K层节点的个数 4️⃣获取二叉树的高度

    2024年02月05日
    浏览(43)
  • 【数据结构】树与二叉树（十三）：递归复制二叉树（算法CopyTree）

    【数据结构】树与二叉树（十三）：递归复制二叉树（算法CopyTree）

      二叉树是一种常见的树状数据结构，它由结点的有限集合组成。一个二叉树要么是 空集 ，被称为 空二叉树 ，要么由一个根结点和两棵不相交的子树组成，分别称为 左子树 和 右子树 。每个结点最多有两个子结点，分别称为左子结点和右子结点。 引理5.1：二叉树中层数

    2024年02月01日
    浏览(40)
  • 【数据结构与算法】树与二叉树

    【数据结构与算法】树与二叉树

    除了之前我们讲的栈、队列、链表等线性结构，数据结构中还有着一对多的 非线性结构 ——— 树 。 树是有 n 个结点组成的有限集，当n=0时为空树，在任意一颗非空树中，有且仅有一个 特定的根结点 ；当n1时，其余结点又可以分为一棵树，称为根的 子树 。 如下图所示: A为

    2023年04月09日
    浏览(50)
  • 数据结构与算法——树与二叉树

    数据结构与算法——树与二叉树

    😊各位小伙伴久等了，本专栏新文章出炉了！！！ 我又回来啦，接下来的时间里，我会持续把数据结构与算法专栏更新完。 👉树型结构👈 是一类重要的 ✍非线性数据结构 ，其中以树和二叉树最为常用，直观来看，树是以分支关系定义的层次结构。树型结构在客观世界中

    2024年02月11日
    浏览(46)
  • 数据结构与算法之《二叉树》详解

    数据结构与算法之《二叉树》详解

    文章目录 一、树的概念及结构 二、二叉树的概念及结构 2、1 二叉树的概念 2、2 二叉树的特点 2、3 二叉树的结构（图片） 2、4 特殊的二叉树 三、二叉树的代码及思路实现 3、1 二叉树的存储结构 3、1、1 二叉树的顺序存储结构 3、1、2 二叉树的链式存储结构 3、2 二叉树链式

    2024年02月01日
    浏览(45)
  • 数据结构之线索二叉树详细解释

    数据结构之线索二叉树详细解释

    1.1 线索二叉树的原理 我们现在倡导节约型社会，一切都应该以节约为本。但当我们创建二叉树时我们会发现其中一共有两个指针域，有的指针域指向的结构为空，这也就浪费了很多空间。所以为了不去浪费这些空间我们采取了一个措施。就是利用那些空地址，存放指向结点

    2023年04月20日
    浏览(41)
  • 【数据结构和算法】---二叉树（1）--树概念及结构

    【数据结构和算法】---二叉树（1）--树概念及结构

    树是一种 非线性的数据结构 ，它是由n（n=0）个有限结点组成一个具有层次关系的集合。之所以叫它树，是因为将此结构倒转后与现实生活中的树极其相似，一个主干分出多个分支，分支还可继续分展。 有一个特殊的结点，称为 根结点 ，根节点没有前驱结点； 除根节点外，

    2024年02月03日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包