【数据结构】树

树型数据结构的详细解析

树是一种分层数据结构，由节点（Node）组成，具有以下特性：

1. 根节点（Root Node）：树的顶层节点。
2. 子节点（Child Node）：根节点的直接连接节点。
3. 叶子节点（Leaf Node）：没有子节点的节点。
4. 高度（Height）：从根节点到最远叶子节点的最长路径。
5. 深度（Depth）：节点到根节点的路径长度。

树的基本概念

1> 节点的度数
一个节点的子树个数被称为该节点的度数。树的度数就是指该数中节点的最大度数。

2> 树叶(叶节点)，内部节点
度数为 0 的节点被称为终端节点、树叶(叶子节点)。度数不为0的节点称为分支节点。除了根节点以外的分支节点都叫内部节点。

3> 子节点 父节点
一个节点的子树之根节点被称为该节点的子节点，该节点称为它们的父节点，同一节点的各个子节点之间称兄弟节点。

4> 根节点与树叶特性
根节点没有父节点，叶子节点没有子节点。

5> 边数
访问一个节点下的其他节点的路径称为边数。

6> 高度(层数)
把根节点定义为第一层, 节点的层数 = 父节点层数+1。

7> 有序树
若树中的每个节点的各个子树的排列按照从左往右，不能交换，即兄弟节点有顺序，该树称为有序树。

8> 森林
若干个不相交的树就是森林。树去掉根节点也是森林，森林加上根节点则称成为树。

二叉树

1> 定义
二叉树（Binary Tree）是n（n≥0）个节点的有限集合，它或者是空集（n＝0），或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。二叉树与普通有序树不同，二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右。
二叉树是树的一种特殊形式，每个节点最多有两个子节点，分别为：

• 左子节点（Left Child）
• 右子节点（Right Child）

2> 性质
二叉树第 i(i>=1) 层上的节点最大数目为 2^(i-1) 个；
在任意一颗二叉树中，树叶的数目比度数为 2 的节点数目多1。

3> 满二叉树
高度 k(k>=1) 时有 2^k-1 个节点的二叉树。

4> 完全二叉树
只有最下面的两层有度数小于2的节点；
且最下面一层的叶子节点集中在最左边若干位置。

存储结构

顺序存储结构

涉及到存储，无论哪一种，都要以 完全二叉树 去存：

链式存储结构

#define datatype char
typedef struct tree{
	datatype data;
    struct tree *lchild;  //指向左孩子的指针
    struct tree *rchild;  //指向右孩子的指针
}tree_t;

二叉树的遍历（三序遍历）

遍历是指按照某种顺序访问树的每个节点。
遍历：沿某条搜索路径周游二叉树，对树中的每个节点访问一次且仅访问一次。(即读取数据)
由于二叉树递归的性质，遍历算法也是递归的。四种基本的遍历算法如下：

1. 先序遍历（Preorder）
   • 先序遍历的算法 (根(读数据) 左 右) 遍历顺序：根 -> 左 -> 右。
   • 若二叉树为空树，则空操作；
   • 否则访问根节点，先序遍历左子树，右序遍历右子树。
2. 中序遍历（Inorder）
   • 中序遍历的算法 (左 根(读数据) 右) 遍历顺序：左 -> 根 -> 右。
   • 若二叉树为空树，则空操作；
   • 否则访问先序遍历左子树，根节点，右序遍历右子树。
3. 后序遍历（Postorder）
   • 中序遍历的算法 (左 右 根(读数据) ) 遍历顺序：左 -> 右 -> 根。
   • 若二叉树为空树，则空操作；
   • 否则访问先序遍历左子树，右序遍历右子树，根节点。
4. 层次遍历（Level Order）：
   • 按层从上到下、从左到右访问节点。
     

二叉树遍历的详细解析

1. 先序遍历（Preorder Traversal）
   • 顺序：根(读数据) -> 左 -> 右
   • 实现思想：
     • 先访问根节点。
     • 再递归遍历左子树。
     • 最后递归遍历右子树。

代码（C语言实现）

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

// 定义二叉树节点
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 先序遍历 根 -> 左 -> 右
void preorderTraversal(Node* root) {
    if (root == NULL) return;
    printf("%d ", root->data);       // 访问根节点
    preorderTraversal(root->left);  // 遍历左子树
    preorderTraversal(root->right); // 遍历右子树
}

int main() {
    // 构造二叉树
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Preorder Traversal: ");
    preorderTraversal(root);
    printf("\n");

    return 0;
}

输出：

Preorder Traversal: 1 2 4 5 3

2. 中序遍历（Inorder Traversal）
   • 顺序：左 -> 根(读数据) -> 右
   • 实现思想：
     • 先递归遍历左子树。
     • 再访问根节点。
     • 最后递归遍历右子树。

代码（C语言实现）

// 中序遍历 左 -> 根 -> 右
void inorderTraversal(Node* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);  // 遍历左子树
    printf("%d ", root->data);     // 访问根节点
    inorderTraversal(root->right); // 遍历右子树
}

int main() {
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Inorder Traversal: ");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

输出：

Inorder Traversal: 4 2 5 1 3

3. 后序遍历（Postorder Traversal）
   • 顺序：左 -> 根(读数据) -> 右
   • 实现思想：
     • 先递归遍历左子树。
     • 再递归遍历右子树。
     • 最后访问根节点。

// 后序遍历 左 -> 右 -> 根
void postorderTraversal(Node* root) {
    if (root == NULL) return;
    postorderTraversal(root->left);  // 遍历左子树
    postorderTraversal(root->right); // 遍历右子树
    printf("%d ", root->data);       // 访问根节点
}

int main() {
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Postorder Traversal: ");
    postorderTraversal(root);
    printf("\n");

    return 0;
}

输出：

Postorder Traversal: 4 5 2 3 1

4. 层次遍历（Level Order Traversal）
   • 顺序：按层从上到下，从左到右访问节点。
   • 实现思想：
     • 使用队列实现层次遍历。
     • 将根节点入队，依次访问队列中的节点，并将每个节点的子节点入队。

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

// 定义队列节点
typedef struct QueueNode {
    Node* treeNode;
    struct QueueNode* next;
} QueueNode;

// 定义队列
typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

// 创建队列
Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}

// 入队
void enqueue(Queue* queue, Node* treeNode) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->treeNode = treeNode;
    newNode->next = NULL;
    if (queue->rear == NULL) {
        queue->front = queue->rear = newNode;
        return;
    }
    queue->rear->next = newNode;
    queue->rear = newNode;
}

// 出队
Node* dequeue(Queue* queue) {
    if (queue->front == NULL) return NULL;
    QueueNode* temp = queue->front;
    Node* 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(Node* root) {
    if (root == NULL) return;
    Queue* queue = createQueue();
    enqueue(queue, root);

    while (!isEmpty(queue)) {
        Node* current = dequeue(queue);
        printf("%d ", current->data);

        if (current->left != NULL) enqueue(queue, current->left);
        if (current->right != NULL) enqueue(queue, current->right);
    }
    printf("\n");
}

int main() {
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("Level Order Traversal: ");
    levelOrderTraversal(root);

    return 0;
}

输出：

Level Order Traversal: 1 2 3 4 5

综上。二叉树是一种高效的查找和排序数据结构，特别适合动态操作（插入、删除、查找）。通过不同的遍历方式，可以实现不同的功能，如输出排序结果（中序遍历）、构建树（先序遍历）、释放树（后序遍历）或按层打印（层次遍历）。四种遍历方法各有特点，应根据具体应用场景选择合适的遍历方式。

以上。仅供学习与分享交流，请勿用于商业用途！转载需提前说明。

我是一个十分热爱技术的程序员，希望这篇文章能够对您有帮助，也希望认识更多热爱程序开发的小伙伴。
感谢！