数据结构~~链式二叉树

目录

一、基本概念

链式存储概念

 二、链式二叉树的结构

链式二叉树结构

构建链式二叉树

二叉树的遍历

 二叉树节点和高度等

 二叉树销毁

三、链式二叉树的练习

相同的树 

对称二叉树

 另外一颗子树

二叉树前序遍历 

 二叉树遍历

四、完整代码

Tree.h

Tree.c

五、总结


一、基本概念

链式二叉树是一种常见的数据结构,它是用链表结点来存储二叉树中的每一个结点,结点结构通常包括数据域和若干个指针域。其中,指针域用于指向左孩子结点和右孩子结点。

对于那些非完全二叉树,由于顺序存储结构的空间利用率低,因此二叉树一般都采用链式存储结构。在链式二叉树中,根据指针的数量可以分为二叉链和三叉链两种结构。二叉链的结点包含存储数据的变量、存储左孩子的指针以及存储右孩子的指针;而三叉链的结点除了包含存储数据的变量、存储左孩子的指针以及存储右孩子的指针,还包含存储双亲的指针。

二叉树的遍历是指按某条搜索路径访问树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。根据访问根结点的顺序不同可以分为前序遍历、中序遍历和后序遍历。

链式存储概念

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

 二、链式二叉树的结构

链式二叉树结构

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

构建链式二叉树

int类型  手撕构建方便前期调试

BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc err");
		return NULL;
	}
	newnode->_data = x;
	newnode->_left = NULL;
	newnode->_right = NULL;
	return newnode;
}
      //123nn4n5nn67nn8nn  通过前序遍历构建
BTNode* BinaryTreeCreate()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);
	BTNode* node8 = BuyNode(8);

	node1->_left = node2;
	node1->_right = node6;
	node2->_left = node3;
	node2->_right = node4;
	node4->_right = node5;
	node6->_left = node7;
	node6->_right = node8;
	return node1;
}

char数组类型

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreateChar(BTDataType* a, int* pi)
{
	if (a[(*pi)] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc err");
		return NULL;
	}
	newnode->_data = a[(*pi)++];
	newnode->_left = BinaryTreeCreateChar(a, pi);
	newnode->_right = BinaryTreeCreateChar(a, pi);
	return newnode;
}

二叉树的遍历

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

前序遍历递归图解:

// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

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

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%d ",root->_data);
	BinaryTreeInOrder(root->_right);
}

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

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%d ",root->_data);
}

 层序遍历:除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层 上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

// 层序遍历
#include"Queue.h"
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* Fout = QueueFront(&q);
		QueuePop(&q);
		printf("%d ",Fout->_data);
		if (Fout->_left)
		{
			QueuePush(&q,Fout->_left);
		}
		if (Fout->_right)
		{
			QueuePush(&q, Fout->_right);
		}
	}
	QueueDestroy(&q);
}

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

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* Fout = QueueFront(&q);
		QueuePop(&q);
		if (Fout == NULL)
		{
			break;
		}
		QueuePush(&q, Fout->_left);
		QueuePush(&q, Fout->_right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* Fout = QueueFront(&q);
		QueuePop(&q);
		if (root)
		{
			QueueDestroy(&q);
			return false;
		}

	}
	QueueDestroy(&q);
	return true;
}

 二叉树节点和高度等

1.二叉树节点个数 

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 
		BinaryTreeSize(root->_left) 
		+ BinaryTreeSize(root->_left)+1;
}

2.二叉树叶子节点个数

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

3.二叉树的最大高度

//二叉树的最大高度
int TreeHeight(BTNode* root) 
{
	if (root == NULL)
		return 0;
	int node_left=TreeHeight(root->_left); 
	int node_right = TreeHeight(root->_right);
	return node_left > node_right ? 
		node_left + 1 : node_right + 1;
}

4.二叉树第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);
}

5.二叉树查找值为x的节点

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	
	if (root == NULL)
		return NULL;
	if (root->_data == x)
		return root;
	BTNode* ret1 = BinaryTreeFind(root->_left, x);
	if (ret1)
		return ret1;
	BTNode* ret2 = BinaryTreeFind(root->_right, x);
	if (ret2)
		return ret2;

	return NULL;

}

 二叉树销毁

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*(root) == NULL)
		return;
	BinaryTreeDestory(&(*root)->_left);
	BinaryTreeDestory(&(*root)->_right);
	free(*(root));
}

三、链式二叉树的练习

相同的树 

给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

思路:  可以通过递归的方式同时遍历两棵树。

比较两棵树的根节点值是否相等,如果不相等则直接返回 false。

然后递归地对左子树和右子树分别进行相同的比较,只有当左右子树在相应位置上都相同的时候才返回 true。

在递归过程中,只要有一处不满足相同条件就可以立即返回 false,只有所有节点和结构都完全一致才能最终返回 true。

/**
 * 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 (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);
}

对称二叉树

给你一个二叉树的根节点 root , 检查它是否轴对称。 

思路:

采用递归的方法。

一个二叉树是轴对称的,意味着对于任意一个节点,它的左子树和右子树是镜像对称的。

具体来说,就是对于当前节点,它的左子节点和右子节点的值相等(如果都存在的话),并且左子节点的左子树和右子节点的右子树对称,左子节点的右子树和右子节点的左子树也对称。我们通过递归地比较左右子树的对应节点来判断整个二叉树是否对称。如果在递归过程中发现不满足对称条件的情况,就可以返回 false,如果递归完整棵树都满足,则返回 true。

 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool _isSymmetric(struct TreeNode* p, struct TreeNode* q) {

    if (p == NULL && q == NULL)
        return true;
    if (p == NULL || q == NULL)
        return false;
    if (p->val != q->val)
        return false;

    return _isSymmetric(p->left, q->right)&&_isSymmetric(p->right, q->left);
}
bool isSymmetric(struct TreeNode* root) {
    return _isSymmetric(root->left, root->right);
}

 另外一颗子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

思路

我们可以从根节点开始,对主树 root 进行先序遍历。

在遍历过程中,每当遇到一个节点,就判断以这个节点为根的子树是否与 subRoot 完全相同。

为了判断子树是否相同,可以编写一个辅助函数来比较两棵树是否完全一致,这与前面判断两棵树是否相同的思路类似,即同时递归地检查节点值以及左右子树的结构和节点值是否匹配。如果找到匹配的子树,就返回 true,否则继续遍历主树的其他节点。

/**
 * 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 (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);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if(root==NULL)
    return false;
    if( root->val==subRoot->val &&
       isSameTree(root,subRoot))
       return true;
    
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

二叉树前序遍历 

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

思路:

首先访问根节点,然后递归地对左子树进行前序遍历,最后递归地对右子树进行前序遍历。

具体来说,我们可以使用一个辅助函数,在这个函数中先输出当前节点的值,然后如果左子树存在就对左子树调用该函数进行递归遍历,接着如果右子树存在就对右子树调用该函数进行递归遍历。这样就可以按照前序遍历的顺序输出所有节点的值。

/**
 * 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().
 */
int TreeSize(struct TreeNode* root) {
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void PrevOrder(struct TreeNode* root,int* a,int* i)
{
    if(root==NULL)
    return;
    a[(*i)++]=root->val;
    PrevOrder(root->left,a,i);
    PrevOrder(root->right,a,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    * returnSize=TreeSize(root);
    int* a=(int*)malloc(sizeof(int)*(*returnSize));
    int i = 0;
    PrevOrder(root,a,&i);
    return a;
}

 二叉树遍历

编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。

输入描述:

输入包括1行字符串,长度不超过100。

输出描述:

可能有多组测试数据,对于每组数据, 输出将输入字符串建立二叉树后中序遍历的序列,每个字符后面都有一个空格。 每个输出结果占一行。

思路:

1. 定义二叉树节点结构体:包含节点值以及左右子节点指针。

2. 构建二叉树函数:通过遍历输入的先序遍历字符串来构建二叉树。使用一个静态索引来跟踪当前处理的字符位置。如果遇到非'#'字符,就创建一个新节点,然后递归地构建左子树和右子树,遇到'#'则表示空节点。

3. 中序遍历函数:按照中序遍历的顺序(先左子树、当前节点、再右子树)输出节点值并添加空格。

4. 在主程序中,获取用户输入的字符串,调用构建二叉树函数得到二叉树,然后调用中序遍历函数输出结果。

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

typedef struct Tree {
    struct Tree* le;
    struct Tree* ri;
    int val;
} BTNode;

void PrevInor(BTNode* root) 
{
    if (root == NULL)
        return;
    PrevInor(root->le);
    printf("%c ", root->val);
    PrevInor(root->ri);
}

BTNode* BUTree(char* a,int* pi)
{
    if(a[*pi] =='#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* newnode=(BTNode*)malloc(sizeof(BTNode));
    newnode->val=a[(*pi)++];
    newnode->le=BUTree(a, pi);
    newnode->ri=BUTree(a, pi);
    return newnode;
}
int main()
{
    char a[100];
    scanf("%s",a);
    int i=0;
    BTNode* node=BUTree(a, &i);
    PrevInor(node);
}

四、完整代码

Tree.h

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

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate();//BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
BTNode* BuyNode(BTDataType x);

//求二叉树的最长高度
int TreeHeight(BTNode* root);

Tree.c

#define _CRT_SECURE_NO_WARNINGS
#include"Tree.h"

BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc err");
		return NULL;
	}
	newnode->_data = x;
	newnode->_left = NULL;
	newnode->_right = NULL;
	return newnode;
}

/*int n,*/
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreateChar(BTDataType* a, int* pi)
{
	if (a[(*pi)] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc err");
		return NULL;
	}
	newnode->_data = a[(*pi)++];
	newnode->_left = BinaryTreeCreateChar(a, pi);
	newnode->_right = BinaryTreeCreateChar(a, pi);
	return newnode;
}

             //123nn4n5nn67nn8nn
BTNode* BinaryTreeCreate()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);
	BTNode* node8 = BuyNode(8);

	node1->_left = node2;
	node1->_right = node6;
	node2->_left = node3;
	node2->_right = node4;
	node4->_right = node5;
	node6->_left = node7;
	node6->_right = node8;
	return node1;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*(root) == NULL)
		return;
	BinaryTreeDestory(&(*root)->_left);
	BinaryTreeDestory(&(*root)->_right);
	free(*(root));
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 
		BinaryTreeSize(root->_left) 
		+ BinaryTreeSize(root->_left)+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);
}
// 二叉树第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* ret1 = BinaryTreeFind(root->_left, x);
	if (ret1)
		return ret1;
	BTNode* ret2 = BinaryTreeFind(root->_right, x);
	if (ret2)
		return ret2;

	return NULL;

}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%d ",root->_data);
	BinaryTreeInOrder(root->_right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%d ",root->_data);
}
// 层序遍历
#include"Queue.h"
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* Fout = QueueFront(&q);
		QueuePop(&q);
		printf("%d ",Fout->_data);
		if (Fout->_left)
		{
			QueuePush(&q,Fout->_left);
		}
		if (Fout->_right)
		{
			QueuePush(&q, Fout->_right);
		}
	}
	QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* Fout = QueueFront(&q);
		QueuePop(&q);
		if (Fout == NULL)
		{
			break;
		}
		QueuePush(&q, Fout->_left);
		QueuePush(&q, Fout->_right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* Fout = QueueFront(&q);
		QueuePop(&q);
		if (root)
		{
			QueueDestroy(&q);
			return false;
		}

	}
	QueueDestroy(&q);
	return true;
}


//二叉树的最大高度
int TreeHeight(BTNode* root) 
{
	if (root == NULL)
		return 0;
	int node_left=TreeHeight(root->_left); 
	int node_right = TreeHeight(root->_right);
	return node_left > node_right ? 
		node_left + 1 : node_right + 1;
}

Queue.c(部分)

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc err");
		return;
	}
	newnode->data = x;
	newnode->next=NULL;
	if (pq->phead == NULL)
	{
		assert(pq->ptail == NULL);
		pq->phead = pq->ptail= newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else 
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL
		&& pq->ptail == NULL;
}

五、总结

二叉树全面总结:

定义:
二叉树是一种特殊的树结构,每个节点最多有两个子节点,分别称为左子节点和右子节点。

主要特点:

• 节点度最大为 2。

• 具有递归结构。

重要类型:

• 满二叉树:所有节点都有两个子节点,且叶子节点都在同一层。

• 完全二叉树:除了最后一层,其他层都是满的,最后一层的叶子节点靠左排列。

遍历方式:

• 前序遍历:先访问根节点,再遍历左子树,最后遍历右子树。

• 中序遍历:先遍历左子树,再访问根节点,最后遍历右子树。

• 后序遍历:先遍历左子树,再遍历右子树,最后访问根节点。

• 层次遍历:按照层次依次访问节点。

应用:

• 高效搜索和排序。

• 表达式树。

• 二叉堆实现优先队列等。

性质:

• 在完全二叉树中,节点编号与层次存在特定关系。

• 叶子节点数与度为 2 的节点数存在一定关系。

存储方式:

• 链式存储:通过节点指针连接。

• 数组存储:适用于完全二叉树。

常见算法:

• 构建二叉树。

• 求深度、高度。

• 查找节点。

• 平衡性判断及调整(如 AVL 树、红黑树等)。

二叉树是数据结构中的基础且重要部分,在计算机科学中有广泛的应用和研究价值。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/644941.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

如何恢复未保存/误删除的Excel文档?

想象一下&#xff0c;您已经在一个非常重要的 Excel 上工作了几个小时&#xff0c;而您的计算机卡住了&#xff0c;您必须重新启动计算机。Excel 文件未保存/误删除&#xff0c;您只是因为忘记点击保存按钮而损失了数小时的工作时间。但是&#xff0c;当您意识到一小时前在 Exc…

U盘引导盘制作Rufus v4.5.2180

软件介绍 Rufus小巧实用开源免费的U盘系统启动盘制作工具和格式化U盘的小工具&#xff0c;它可以快速将ISO镜像文件制作成可引导的USB启动安装盘&#xff0c;支持Windows或Linux启动&#xff0c;堪称写入镜像速度最快的U盘系统制作工具。 软件截图 更新日志 github.com/pbat…

LeetCode:74.搜索二维矩阵

class Solution(object):def searchMatrix(self, matrix, target):M, N len(matrix), len(matrix[0])for i in range(M):for j in range(N):if matrix[i][j] target:return Truereturn False代码解释 这段代码定义了一个名为 Solution 的类&#xff0c;其中包含一个方法 sea…

HoneyTrap蜜罐系统实践操作@FreeBSD

HoneyTrap介绍 HoneyTrap是一个可扩展的开源系统&#xff0c;用于运行、监控和管理蜜罐。 HoneyTrap蜜罐系统通过在网络中部署感应节点&#xff0c;实时感知周边网络环境&#xff0c;并将感应节点的日志进行实时存储和可视化分析&#xff0c;从而实现对网络环境中威胁情况的感…

线程池,日志

所要用到的知识点&#xff1a; 多线程的创建 生产消费模型&#xff0c; 线程锁 条件变量 代码&#xff1a; 线程池日志

linux系统——top资源管理器

在linux系统中&#xff0c;有类似于windows系统中的资源管理器&#xff0c;top用于实时的监控系统的任务执行状态以及硬件配置信息 在linux中&#xff0c;输入top命令&#xff0c;可以进入相应界面&#xff0c;在此界面可以使用一些指令进行操作 如&#xff0c;输入z 可以改变…

齿轮常见故障学习笔记

大家好&#xff0c;这期咱们聊一聊齿轮常见的失效形式&#xff0c;查阅了相关的资料&#xff0c;做个笔记分享给大家&#xff0c;共同学习。 介绍 齿轮故障可能以多种方式发生。如果在设计阶段本身就尽量防止这些故障的产生&#xff0c;则可以产生改更为优化的齿轮设计。齿轮…

区块链会议投稿资讯CCF A--USENIX Security 2025 截止9.4、1.22 附录用率

会议名称&#xff1a;34th USENIX Security Symposium CCF等级&#xff1a;CCF A类学术会议 类别&#xff1a;网络与信息安全 录用率&#xff1a;2023年接收率29%&#xff0c;2024录用的区块链相关文章请查看 Symposium Topics System security Operating systems security …

springboot结合baomidou dynamic-datasource组件实现多数据源

dynamic-datasource组件实现多数据源 一、背景介绍二、 思路方案三、过程四、总结五、升华 一、背景介绍 博主最近研发的项目中由于业务需要&#xff0c;在项目中使用到多个数据源。使用到了baomidou的dynamic-datasource组件来实现访问不同的数据源。觉得挺有意思的也是进行了…

[JAVASE] 类和对象综合应用 -- 图书管理系统

目录 零. 概览 一. 抽象出图书管理系统所涉及的对象 1.1 Book 1.2 User 1.3 Operation 二. 实现 User 包中的对象 2.1 User父类 2.2 NormalUser 对象 2.3 AdminUser 对象 2.4 小总结(1) 三. 实现Book包中的对象 3.1 Book 对象 3.2 BookList 对象 四. 实现 Operation…

为什么单片机不能直接驱动继电器和电磁阀

文章是瑞生网转载&#xff0c;PDF格式文章下载&#xff1a; 为什么单片机不能直接驱动继电器和电磁阀.pdf: https://url83.ctfile.com/f/45573183-1247189072-10b6d1?p7526 (访问密码: 7526)

Vitis HLS 学习笔记--控制驱动TLP-处理deadlock

目录 1. 简介 2. 代码解析 2.1 HLS kernel代码 2.2 查看接口报告 2.3 TestBench 2.4 Dataflow 报告 3. Takeaways 4. 总结 1. 简介 本文是对《Hardware Acceleration Tutorials: FIFO Sizing for Performance and Avoiding Deadlocks》实验内容的详细解释。 首先需要…

蜜罐技术是一种什么防御技术?实现原理是什么?

前言&#xff1a;蜜罐技术的出现改变了这种被动态势&#xff0c;它通过吸引、诱骗攻击者&#xff0c;研究学习攻击者的攻击目的和攻击手段&#xff0c;从而延缓乃至阻止攻击破坏行为的发生&#xff0c;有效保护真实服务资源。 自网络诞生以来&#xff0c;攻击威胁事件层出不穷…

【数据结构(邓俊辉)学习笔记】图01——若干定义

文章目录 1. 概述1.1 邻接 关联1.2 无向 有向1.3 路径 环路 2. 邻接矩阵2.1 接口2.2 邻接矩阵 关联矩阵2.3 实例2.4 顶点和边2.5 邻接矩阵2.6 顶点静态操作2.7 边操作2.7 顶点动态操作2.8 综合评价 1. 概述 1.1 邻接 关联 相对于此前的线性以及半线性结构&#xff0c;图…

AT指令配置模块

图为用串口一发送字符串来配置AT指令模块的字符串发送格式。 后续更新接收字符串的数据处理。 利用stm32给WiFi模块发送AT指令&#xff0c;所以32的发送端连接WiFi模块的接收端&#xff0c;WiFi模块接收AT指令的返回值发送给ch340由电脑显示&#xff0c;所以WiFi模块的TX连接C…

2024年5月大语言模型论文推荐:模型优化、缩放到推理、基准测试和增强性能

前一篇文章总结了关于计算机视觉方面的论文&#xff0c;这篇文章将要总结了2024年5月发表的一些最重要的大语言模型的论文。这些论文涵盖了塑造下一代语言模型的各种主题&#xff0c;从模型优化和缩放到推理、基准测试和增强性能。 大型语言模型(llm)发展迅速&#xff0c;跟上…

0元入驻抖音小店,真的是好事吗?

大家好&#xff0c;我是喷火龙。 抖音小店去年推出0元入驻抖音小店个人店的政策&#xff0c;简而言之就是只要一张身份证就可以开店&#xff0c;不需要营业执照&#xff0c;也不需要交保证金。 很多人一听很心动&#xff0c;因为没有任何成本就可以开店&#xff0c;于是纷纷跑…

echarts配置记录,一些已经废弃的写法

1、normal&#xff0c;4.0以后无需将样式写在normal中了 改前&#xff1a; 改后&#xff1a; DEPRECATED: normal hierarchy in labelLine has been removed since 4.0. All style properties are configured in labelLine directly now. 2、axisLabel中的文字样式无需使用te…

C++Qt操作Lotus Domino数据库 Lotus Domino C++连接Lotus Domino C++快速开发Lotus Domino

java连接domino C#连接domino python连接domino go连接domino,delphi连接domino Excel连接domino Flutter、微信小程序连接domino C 操作 Lotus Domino 数据库&#xff1a;自动化与效率的结合 引言 在企业级应用中&#xff0c;Lotus Domino 提供了一个强大的协作平台&#xff0…

牛客NC324 下一个更大的数(三)【中等 双指针 Java/Go/PHP/C++】参考lintcode 52 · 下一个排列

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/475da0d4e37a481bacf9a09b5a059199 思路 第一步&#xff1a;获取数字上每一个数&#xff0c;组成数组arr 第二步&#xff1a;利用“下一个排列” 问题解题方法来继续作答&#xff0c;步骤&#xff1a;利用lintc…