首页 > 其他分享 >【数据结构】二叉树

【数据结构】二叉树

时间：2024-05-31 23:31:14浏览次数：17  
标签：node 结点 遍历 NULL BTNode 二叉树 数据结构

【数据结构】二叉树

树

树的概念

树是一种非线性的数据结构，它是由n(n>=0)个有限结点组成一个有层次关系的集合

在这里插入图片描述
将其称之为数，由于其看似一颗倒挂树，根朝上，叶朝下。

  • 树的特点：

1.有个特殊的结点，称为根节点，根结点没有前驱结点
2.除根节点外，其余结点被分为M(M>0)个不相关的集合T1，T2，T3…Tm，其中每一个集合Ti(1<=i<=m)又是一个与树类似的子树，每棵子树的根结点有且只有一个前驱，可以有0个或多个后结点
3.树是递归定义的

任何一棵树都有俩部分组成：根与子树

树的相关概念

结点的度：一个结点含有的子树的个数称为该结点的度。
叶结点或终端结点：度为零的结点。
非终端结点或分支结点：度不为零的结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点
兄弟结点：具有相同父结点的结点互称为兄弟结点（亲兄弟）
树的度：一个树中最大的结点的度称为树的度
结点的层次：从根开始定义起，根为第一层，根的子结点为第二层，以此类推
树的高度或深度：树中结点的最大层次
堂兄弟结点：双亲在同一层的结点互为堂兄弟
结点的祖先：从根到该结点所经分支上的所有结点
子孙：以某结点为根的子树中任一结点都称为该结点的子孙
森林：由m(m>0)棵互不相关的树的集合称为森林

树的注意事项

  • 子树是不相交的
  • 除了根结点外，每个结点有且仅有一个父节点
  • 一棵N个结点的树有N-1条边

左孩子右兄弟表示法

typedef int DataType;
struct TreeNode
{
	struct TreeNode* FirstChild;//第一个孩子结点
	struct TreeNode* NextBroter;//指向其下一个兄弟结点
	DataType data;//结点中的数据域
};

树实际中的应用

  • Linux树状目录结构

在这里插入图片描述

  • windows树状目录结构

在这里插入图片描述

二叉树

二叉树的概念

一棵二叉树是结点的一个有限集合，该集合：

在这里插入图片描述

  • 要么为空

  • 要么由一个根结点加上俩棵别称为左子树和右子树的二叉树组成

在这里插入图片描述

二叉树的注意事项

  • 二叉树不存在度大于2的结点

  • 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

特殊二叉树

满二叉树

一个二叉树，如果每一层的结点数都达到最大值，则这个二叉树就是满二叉树。即如果一个二叉树的层数为k，且结点总数是2k-1，则为满二叉树

在这里插入图片描述

完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的，对于深度为k的，由n个结点的二叉树，当且仅当其每一个结点都与深度的k满二叉树中编号从1至n的结点——对应时称为完全二叉树

在这里插入图片描述

二叉树的性质

  • 对于任何一棵完全二叉树，如果度为0其叶结点个数为n0，度为2的分支结点个数为n2，则n0=n2+1。（度为0的永远比度为2的多一个）
  • 高度为h的完全二叉树，结点数量范围[2h-1,2h-1]
  • 结点为N的完全二叉树，结点数量的范围[log(N+1),log(N+1)]

二叉树的存储形式

顺序存储

顺序结构存储就是使用数组存储，一般数组只能用来表示完全二叉树（不是完全二叉树会浪费很多空间），二叉树顺序存储在物理上是一个数组，在逻辑上是一棵二叉树。

在这里插入图片描述

  • 表示二叉树的值在数组位置中的下标关系：
parent = (child - 1) / 2;
leftchild = parent * 2 + 1;
rightchild = parent * 2 + 2;

链式存储

二叉树的链式存储结构是指用链表表示一棵二叉树，使用链来表示元素之间的逻辑关系。
通常方法是链表中每个结点由三个域组成，数据域与左右指针域。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
	 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
	 struct BinTreeNode* _pRight; // 指向当前节点右孩子
	 BTDataType _data; // 当前节点值域
}

链式结构又分为二叉链与三叉链

typedef int BTDataType;
// 三叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pParent; // 指向当前节点的双亲
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
}；

在这里插入图片描述

二叉树链式结构

前面的知识已经对二叉树有了些许了解，总的来讲，普通二叉树没有意义，但是学习二叉树可以对后期了解更多与二叉树有关的知识进入交互学习。
比如搜索二叉树也是二叉树的一种：其左子二叉树小于右子二叉树，搜索二叉树也叫排序二叉树。
类似二分查找，但二分查找的劣势：
1.数组不便于增删查找
2.需要升序或者降序

实际上经常被用来搜索的数据结构有：平衡二叉搜索树、哈希表、B树

简单初始化

进入了解二叉树之前需要简单对二叉树进行初始化，以便对二叉树有清晰的认知。

在这里插入图片描述

#include<stdio.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;

BTNode* BuyBTNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;
}

BTNode* CreatBTNode()
{
	BTNode* node1 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;
}

二叉树的遍历

所谓二叉树遍历是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个结点只操作一次访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
在这里插入图片描述
二叉树的遍历有：前序遍历、中序遍历、后续遍历

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

在这里插入图片描述

前序遍历

前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

  • 根-左子树-右子树
void PreOrder(BTNode* node)
{
	if (node == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", node->data);
	PreOrder(node->left);
	PreOrder(node->right);
}

在这里插入图片描述

中序遍历

中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

  • 左子树-根-右子树
void InOrder(BTNode* node)
{
	if (node == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(node->left);
	printf("%d ", node->data);
	InOrder(node->right);
}

在这里插入图片描述

后续遍历

后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

  • 左子树-右子树-根
void PostOrder(BTNode* node)
{
	if (node == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(node->left);
	PostOrder(node->right);
	printf("%d ", node->data);
}

在这里插入图片描述

三种遍历代码实现

#include<stdio.h>
#include<stdlib.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;

BTNode* BuyBTNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

BTNode* CreatBTNode()
{
	BTNode* node1 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;
}


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


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

void PostOrder(BTNode* node)
{
	if (node == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(node->left);
	PostOrder(node->right);
	printf("%d ", node->data);
}

int main(void)
{
	BTNode* node = CreatBTNode();
	PreOrder(node);
	printf("\n");
	InOrder(node);
	printf("\n");
	PostOrder(node);
	printf("\n");

	return 0;
}

层序遍历

二叉树除了可以前序遍历、中序遍历、后序遍历，还可以层序遍历，层序遍历就是从二叉树的根结点出发，首先访问根结点，然后第二层从左至右开始访问，以此类推…自上而下，从左往右。

  • 原则：出上一层，入后一层
void levelOrder(BTNode* node)
{
	Queue q;
	QueueInit(&q);
	if (node)
	{
		QueuePush(&q, node);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	Queuedestory(&q);
}

二叉树相关代码实现

二叉树的结点个数

//二叉树结点个数
int BinaryTreeSize(BTNode* node)
{
	if (node == NULL)
		return 0;
	return BinaryTreeSize(node->left) + BinaryTreeSize(node->right) + 1;
}

//二叉树结点个数
int BinaryTreeSize(BTNode* node)
{
	return (node == NULL) ? 0
		: BinaryTreeSize(node->left)
		+ BinaryTreeSize(node->right)
		+ 1;
}

二叉树的高度

//二叉树的高度或者深度
int BinaryTreeHeight(BTNode* node)
{
	if (node == NULL)
		return 0;
	int leftHeight = BinaryTreeHeight(node->left) + 1;
	int rightHeight = BinaryTreeHeight(node->right) + 1;
	
	return (leftHeight > rightHeight) 
		? leftHeight 
		: rightHeight;
}

二叉树的叶子结点个数

//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* node)
{
	if (node == NULL)
	{
		return 0;
	}
	if (node->left == NULL && node->right == NULL)
	{
		return 1;
	}

	return BinaryTreeLeafSize(node->left) + BinaryTreeLeafSize(node->right);
}

第k层结点个数

寻找第k层结点结合第一层与第k层距离为k，第二层与第k层距离为k-1…

//二叉树第k层结点个数
int BinaryTreelevel(BTNode* node, int k)
{
	if (node == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreelevel(node->left, k - 1) 
		+ BinaryTreelevel(node->right, k - 1);
}

二叉树查找值为x的结点

//二叉树查找值为x的结点
BTNode* BinaryTreeFine(BTNode* node, BTDataType x)
{
	if (node == NULL)
	{
		return NULL;
	}
	if (node->data == x)
	{
		return node;
	}
	BTNode* left = BinaryTreeFine(node->left,x);
	BTNode* right = BinaryTreeFine(node->right, x);
	if (left != NULL)
	{
		return left;
	}
	if (right != NULL)
	{
		return right;
	}
	return NULL;
}

二叉树的销毁

void BinaryTreeDestory(BTNode* node)
{
	if(node==NULL)
	{
		return;
	}
	BInaryTreeDestory(node->left);
	BInaryTreeDestory(node->right);
	free(node);
	node->NULL;
}

DFS与BFS

  • DFS：深度优先遍历（二叉树有序遍历）——一般使用递归
  • BFS：广度优先遍历（二叉树层序遍历）——一般使用队列

标签：node,结点,遍历,NULL,BTNode,二叉树,数据结构
From： https://blog.csdn.net/dab112/article/details/139188828

相关文章

  • 【LeetCode算法】第101题：对称二叉树
    目录一、题目描述二、初次解答三、官方解法四、总结一、题目描述二、初次解答1.思路：递归判定左子树和右子树是否对称。用一个新函数sym来递归判定左子树和右子树是否对称。该函数细节：判定当前传入的两个根节点是否为空，若均为空则返回true，若只有其中一个为空则返回fa......
  • cadical基本数据结构分析3——运行状态控制
    在一对文件（options.hpp和options.cpp）运行控制参数统一初始化并设置动态增长规律； 1#ifndef_options_hpp_INCLUDED2#define_options_hpp_INCLUDED34/*------------------------------------------------------------------------*/56//Inorder......
  • 【二叉树】Leetcode 129. 求根节点到叶节点数字之和【中等】
    求根节点到叶节点数字之和给你一个二叉树的根节点root，树中每个节点都存放有一个0到9之间的数字。每条从根节点到叶节点的路径都代表一个数字：例如，从根节点到叶节点的路径1->2->3表示数字123。计算从根节点到叶节点生成的所有数字之和。叶节点是指没有......
  • 数据结构排序算法之直接插入排序与希尔排序【图文详解】
    P.S.：以下代码均在VS2019环境下测试，不代表所有编译器均可通过。P.S.：测试代码均未展示头文件stdio.h的声明，使用时请自行添加。                                             博主主页：LiUEEEEE         ......
  • [数据结构+二叉树+B-Tree和红黑树与B+Tree与hashMap原理+ concurrentHashMap的原理]析
    目录数据结构:你了解过哪些数据结构:这些数据结构的优缺点:二叉树：特点:二叉树适合做磁盘存储吗: 缺点：B-Tree:b-树的查找过程:思考:特点:B+Tree: B+树搜索过程与B树的查询过程没有区别。但实际上有三点不一样：（B+Tree优势）简述B+Tree:不经历IO的情况下，可以直接......
  • Leetcode 力扣106. 从中序与后序遍历序列构造二叉树 (抖音号：708231408)
    给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。示例1:输入：inorder=[9,3,15,20,7],postorder=[9,15,7,20,3]输出：[3,9,20,null,null,15,7]示例2:输入：inorder=[......
  • Leetcode 力扣105. 从前序与中序遍历序列构造二叉树 (抖音号：708231408)
    给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。示例1:输入:preorder=[3,9,20,15,7],inorder=[9,3,15,20,7]输出:[3,9,20,null,null,15,7]示例2:输入:preorder......
  • 数据结构与算法
    时间复杂度常数操作包括加减乘除，以及从数组中取出一个值（因为直接计算偏移量，是一块连续的区域）注意：从list中取出一个值不是常数操作，因为需要遍历去找时间复杂度就是计算存在多少个常数操作且忽略低阶项，只要高阶项，且忽略高阶项的系数通过亦或完成交换算法defswap():a......
  • C++数据结构之：栈Stack
    摘要：  it人员无论是使用哪种高级语言开发东东，想要更高效有层次的开发程序的话都躲不开三件套：数据结构，算法和设计模式。数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储......
  • 3598. 二叉树遍历 已知前序 中序 求后序遍历
    #include<iostream>usingnamespacestd;voidpostOrder(stringpre,stringin)//定义后序遍历函数，参数为前序遍历和中序遍历结果字符串{if(in.size()){charroot=pre[0];//获取前序遍历结果的第一个字符作为根节点intk=in.find(......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99