二级公共基础之数据结构与算法篇(五)树和二叉树

前言

一、树的基本概念

1.父结点和根节点

2.子节点和叶子节点

3.度和深度

4.子树

二、二叉树及其基本性质

1. 二叉树的定义

2. 二叉树的基本性质

性质1

性质2

性质3

性质4

性质5

性质6

三、二叉树的存储结构

四、二叉树的遍历

1.遍历二叉树的概念

1. 前序遍历二叉树

2. 中序遍历二叉树

3. 后序遍历二叉树

4. 层次遍历二叉树

2.常考题目

五、二叉树中常考题目

1.完全二叉树

前言

这篇博客主要介绍树和二叉树。树是一种常见的数据结构，广泛应用于计算机科学和工程领域，如文件系统、数据库索引、表达式解析等。二叉树是树的一种特殊形式，具有许多独特的性质和应用。

一、树的基本概念

树（Tree）是一种简单的非线性结构。

图1.二叉树

1.父结点和根节点

在树结构中，每一个结点有一个直接前驱，称为父节点。

没有前驱的节点只有一个，称为树的根节点。

在图1中，A节点是树的根节点。

2.子节点和叶子节点

在树结构中，每一个节点可以有多个直接后继，称为子节点。

没有子节点的节点称为叶子节点。

叶子节点是树的最底层节点。

在图1中D、H、I、F、G均为叶子节点。

3.度和深度

在树结构中，节点所拥有的子节点的个数称为该节点的度。

在图1中节点A和节点E的度为2，节点C的度为1。

节点的深度是从根节点到该节点的路径长度。

树的深度是所有节点深度的最大值。

4.子树

在树结构中，以某节点的一个子节点为根构成的树称为该节点的一棵子树。

二、二叉树及其基本性质

二叉树是一种特殊的树，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。

1. 二叉树的定义

二叉树可以为空，也可以由一个根节点和两个互不相交的子树组成，分别称为左子树和右子树。

2. 二叉树的基本性质

性质1

在二叉树的第k层上最多有 $2^{k-1}$ 个节点（k≥1）。

性质2

深度为k的二叉树中，最多有 $2^{k-1}$ 个节点。

性质3

对任意一棵二叉树，度为0的节点(即叶子节点)总比度为2的节点多一个。

性质4

具有n个节点的二叉树，其深度至少为[ $\log_{2} n$ ]+1，其中 $\log_{2} n$ 表示表达式的整数部分。

性质5

具有n个节点的完全二叉树的深度为[ $\log_{2} n$ ]+1

性质6

图2.二叉树的性质6

三、二叉树的存储结构

二叉树通常采用链式存储结构。用于存储二叉树中数据元素的存储节点由数据域和指针域两部分组成。指针域包括左指针域和右指针域。

四、二叉树的遍历

1.遍历二叉树的概念

二叉树的遍历是指按照某种顺序访问二叉树中的所有节点。常见的遍历方法有前序遍历、中序遍历和后序遍历。

1. 前序遍历二叉树

前序遍历二叉树(Pre_order Traversal)是先遍历左子树，然后遍历根节点和右子树。

访问顺序：根节点 -> 左子树 -> 右子树。

2. 中序遍历二叉树

前序遍历二叉树(In_order Traversal)是先遍历根节点，然后遍历左子树和右子树。

访问顺序：左子树 -> 根节点 -> 右子树。

3. 后序遍历二叉树

前序遍历二叉树(Post_order Traversal)是先遍历左子树，然后遍历根节点和右子树。

访问顺序：左子树 -> 右子树 -> 根节点。

4. 层次遍历二叉树

层次遍历二叉树(Level_order Traversal)是按照树的层次从上到下，从左到右依次访问每个节点。用队列实现，先访问根节点。

访问顺序：左子树 -> 右子树 -> 根节点。

以下是二叉树的前序、中序和后序遍历的实现：

#include <stdio.h>
#include <stdlib.h>// 定义二叉树节点
typedef struct TreeNode {int data;struct TreeNode *left;struct TreeNode *right;
} TreeNode;// 定义队列节点
typedef struct QueueNode {TreeNode *treeNode;struct QueueNode *next;
} QueueNode;// 定义队列
typedef struct Queue {QueueNode *front;QueueNode *rear;
} Queue;// 创建新节点
TreeNode* createNode(int data) {TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));newNode->data = data;newNode->left = NULL;newNode->right = NULL;return newNode;
}// 创建队列
Queue* createQueue() {Queue* queue = (Queue*)malloc(sizeof(Queue));queue->front = NULL;queue->rear = NULL;return queue;
}// 入队
void enqueue(Queue* queue, TreeNode* treeNode) {QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));newNode->treeNode = treeNode;newNode->next = NULL;if (queue->rear == NULL) {queue->front = newNode;queue->rear = newNode;} else {queue->rear->next = newNode;queue->rear = newNode;}
}// 出队
TreeNode* dequeue(Queue* queue) {if (queue->front == NULL) {return NULL;}QueueNode* temp = queue->front;TreeNode* treeNode = temp->treeNode;queue->front = queue->front->next;if (queue->front == NULL) {queue->rear = NULL;}free(temp);return treeNode;
}// 判断队列是否为空
int isEmpty(Queue* queue) {return queue->front == NULL;
}// 层次遍历
void levelOrderTraversal(TreeNode* root) {if (root == NULL) return;Queue* queue = createQueue();enqueue(queue, root);while (!isEmpty(queue)) {TreeNode* currentNode = dequeue(queue);printf("%d ", currentNode->data);if (currentNode->left != NULL) {enqueue(queue, currentNode->left);}if (currentNode->right != NULL) {enqueue(queue, currentNode->right);}}free(queue);
}// 前序遍历
void preOrderTraversal(TreeNode* root) {if (root == NULL) return;printf("%d ", root->data);preOrderTraversal(root->left);preOrderTraversal(root->right);
}// 中序遍历
void inOrderTraversal(TreeNode* root) {if (root == NULL) return;inOrderTraversal(root->left);printf("%d ", root->data);inOrderTraversal(root->right);
}// 后序遍历
void postOrderTraversal(TreeNode* root) {if (root == NULL) return;postOrderTraversal(root->left);postOrderTraversal(root->right);printf("%d ", root->data);
}// 主函数
int main() {// 创建一个简单的二叉树TreeNode* root = createNode(1);root->left = createNode(2);root->right = createNode(3);root->left->left = createNode(4);root->left->right = createNode(5);printf("前序遍历: ");preOrderTraversal(root);printf("\n");printf("中序遍历: ");inOrderTraversal(root);printf("\n");printf("后序遍历: ");postOrderTraversal(root);printf("\n");printf("层次遍历: ");levelOrderTraversal(root);printf("\n");return 0;
}