【二叉树教程详解以及C语言/C++实现二叉树】

秒速五厘米 2024-03-17 13:05 54阅读 0赞

## 二叉树 ##

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

### 一、什么是二叉树 ###

**二叉树是一种特殊的树状数据结构，其中每个节点最多有两个子节点。每个节点包含一个数据元素和指向其左子节点和右子节点的指针。左子节点的值小于或等于父节点的值，而右子节点的值大于父节点的值。这个特性使得二叉树在查找、插入和删除操作方面非常高效。**

A
        / \
       B   C
      / \   \
     D   E   F

二叉树通常用于模拟具有层级结构的数据。它的一些常见应用包括**搜索算法（例如二叉搜索树）、表达式树、哈夫曼编码树**等。在二叉树中，我们可以使用不同的遍历方式来访问节点，包括**先序遍历、中序遍历和后序遍历**。

### 二、二叉树遍历方式 ###

#### 1、先序遍历 ####

**从根节点开始，先访问根节点，然后递归地对左子树和右子树进行先序遍历。这种遍历方式可以用于复制整个树的结构。**

**假设我们有如下一棵二叉树：**

1
        / \
       2   3
      / \   \
     4   5   6

**首先，我们访问根节点 1，然后遍历左子树。左子树的根节点是 2，我们继续访问它，然后遍历它的左子树。左子树的根节点是 4，我们继续访问它，然后发现它没有左子树和右子树了，所以我们返回到节点 2，然后遍历它的右子树。**

**右子树的根节点是 5，我们继续访问它，然后发现它没有左子树和右子树了，所以我们返回到节点 2，然后返回到根节点 1，然后遍历根节点的右子树。**

**右子树的根节点是 3，我们继续访问它，然后遍历它的左子树。左子树是空的，所以我们返回到节点 3，然后遍历它的右子树。**

**右子树的根节点是 6，我们继续访问它，然后发现它没有左子树和右子树了，所以我们返回到节点 3，然后返回到根节点 1，遍历结束。**

最终的先序遍历结果是：1 2 4 5 3 6。

**下面是先序遍历的具体步骤图解：**

1
        / \
       2   3
      / \   \
     4   5   6

1.  **访问根节点 1**
2.  **遍历左子树**
    
     *  **访问根节点 2**
     *  **遍历左子树**
        
         *  **访问根节点 4**
         *  **左子树为空，返回**
     *  **遍历右子树**
        
         *  **访问根节点 5**
         *  **左子树为空，返回**
3.  **遍历右子树**
    
     *  **访问根节点 3**
     *  **遍历左子树（为空，返回）**
     *  **遍历右子树**
        
         *  **访问根节点 6**
         *  **左子树为空，返回**

最终的先序遍历结果是：1 2 4 5 3 6。

#### 2、中序遍历 ####

**中序遍历是二叉树遍历的一种方式，其遍历顺序为：从根节点开始，先递归地对左子树进行中序遍历，然后访问根节点，最后递归地对右子树进行中序遍历。对于二叉搜索树，中序遍历可以实现升序输出。**

**下面是一个二叉树的示例：**

1
        /   \
       2     3
      / \   / \
     4   5 6   7

中序遍历的结果为：4, 2, 5, 1, 6, 3, 7。

**中序遍历的过程可以使用递归或者栈来实现。下面详细介绍一下两种方法。**

##### （1）递归法 #####

**递归法是最简单的实现方式。具体步骤如下：**

1.  **如果当前节点为空，则返回。**
2.  **递归遍历当前节点的左子树。**
3.  **访问当前节点。**
4.  **递归遍历当前节点的右子树。**

**下面是用递归法实现中序遍历的示例代码：**

#include <stdio.h>
    #include <stdlib.h>
    
    struct Node {
        
        int val;
        struct Node* left;
        struct Node* right;
    };
    
    void inorderTraversal(struct Node* root) {
        
        if (root == NULL) {
        
            return;
        }
        inorderTraversal(root->left);
        printf("%d ", root->val);
        inorderTraversal(root->right);
    }

##### （2）栈法 #####

**栈法使用一个栈来辅助遍历过程。具体步骤如下：**

1.  **初始化一个空栈和一个指针，指向根节点。**
2.  **当栈不为空或者指针不为空时，执行以下操作：**
    
     *  **如果指针不为空，将指针压入栈，并将指针指向其左子树。**
     *  **如果指针为空，弹出栈顶元素并访问，然后将指针指向其右子树。**
3.  **当栈为空且指针为空时，遍历结束。**

**下面是用栈法实现中序遍历的示例代码：**

#include <stdio.h>
    #include <stdlib.h>
    
    struct Node {
        
        int val;
        struct Node* left;
        struct Node* right;
    };
    
    void inorderTraversal(struct Node* root) {
        
        struct Node* stack[1000];
        int top = -1;
        struct Node* curr = root;
        while (top != -1 || curr != NULL) {
        
            if (curr != NULL) {
        
                stack[++top] = curr;
                curr = curr->left;
            } else {
        
                curr = stack[top--];
                printf("%d ", curr->val);
                curr = curr->right;
            }
        }
    }

**无论是递归法还是栈法，它们的时间复杂度都是O(n)，其中n为二叉树的节点个数。**

#### 3、后序遍历 ####

**后序遍历（Postorder Traversal）是一种二叉树的遍历方式，它的遍历顺序是先遍历左子树，再遍历右子树，最后访问根节点。这种遍历方式常用于\*\*\*\*内存回收**和**析构函数调用**。

**下面是一个示例二叉树：**

1
         / \
        2   3
       / \   \
      4   5   6

**按照后序遍历的顺序，应该先遍历左子树，再遍历右子树，最后访问根节点。所以该二叉树的后序遍历结果为：**

4 -> 5 -> 2 -> 6 -> 3 -> 1

**接下来，我们使用C语言来实现二叉树的后序遍历。**

**首先，我们需要定义二叉树的结构，包括节点的值以及左右子节点的指针。**

#include <stdio.h>
    #include <stdlib.h>
    
    // 定义二叉树的结构
    struct TreeNode {
        
        int val;
        struct TreeNode* left;
        struct TreeNode* right;
    };

**然后，我们需要创建一个新的二叉树节点的函数。**

// 创建一个新的二叉树节点
    struct TreeNode* createNode(int val) {
        
        struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        newNode->val = val;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }

**接下来，我们来实现二叉树的后序遍历函数。**

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

**在后序遍历函数中，我们首先判断当前节点是否为空，如果为空则返回。然后依次递归遍历左子树和右子树，最后访问根节点。**

**最后，我们可以在主函数中创建一个示例二叉树，并调用后序遍历函数来进行遍历。**

int main() {
        
        // 创建示例二叉树
        struct TreeNode* root = createNode(1);
        root->left = createNode(2);
        root->right = createNode(3);
        root->left->left = createNode(4);
        root->left->right = createNode(5);
        root->right->right = createNode(6);
    
        // 后序遍历二叉树
        printf("后序遍历结果：");
        postorderTraversal(root);
        printf("\n");
    
        return 0;
    }

**运行上述代码，输出结果为：**

后序遍历结果：4 5 2 6 3 1。

### 三、二叉树特性 ###

**除了遍历方式，二叉树还有一些其他的特性：**

*  **完全二叉树：在完全二叉树中，除了最后一层，其他每一层的节点都被填满，且最后一层的节点从左到右依次填入。这种树结构在数组中可以高效地存储。**
 *  **满二叉树：满二叉树是一种所有节点都具有0个或2个子节点的二叉树。在满二叉树中，所有的叶子节点都在同一层。**
 *  **平衡二叉树：在平衡二叉树中，任何节点的左子树和右子树的高度差最多为1。这样可以保持树的平衡，提高搜索、插入和删除操作的效率。**
 *  **二叉搜索树：二叉搜索树（BST）是一种具有以下特性的二叉树：对于任意节点，其左子树中的所有节点的值都小于它，而右子树中的所有节点的值都大于它。这个特性使得在二叉搜索树中进行搜索、插入和删除操作非常高效。**

**总而言之，二叉树是一种重要的数据结构，具有广泛的应用。它的节点最多可以有两个子节点，并且可以使用不同的遍历方式来访问和处理节点。**

### 四、二叉树实现 ###

#### 1、定义结构体 ####

**首先，我们定义一个结构体，表示二叉树的节点。每个节点由数据部分和两个指针部分组成，分别指向左子节点和右子节点。**

typedef struct Node {
        
        int data;
        struct Node *left;
        struct Node *right;
    } Node;

#### 2、创建新节点 ####

**接下来，我们实现了一个用于创建新节点的函数**`createNode`，负责申请内存并初始化节点的数据部分。如果内存分配失败，会打印错误信息并终止程序。

Node *createNode(int data) {
        
        Node *newNode = (Node *)malloc(sizeof(Node));
        if (newNode == NULL) {
        
            printf("内存分配失败！\n");
            exit(1);
        }
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }

#### 3、插入节点 ####

**接下来，我们实现了一个插入节点的函数**`insertNode`。该函数根据传入的数据值，将新节点插入到合适的位置。如果树为空，函数会创建新节点并将其设为根节点。否则，根据数据值的大小，递归地将节点插入到左子树或右子树中。

Node *insertNode(Node *root, int data) {
        
        if (root == NULL) {
        
            return createNode(data);
        } else if (data < root->data) {
        
            root->left = insertNode(root->left, data);
        } else if (data > root->data) {
        
            root->right = insertNode(root->right, data);
        }
        return root;
    }

**之后，我们实现了三种遍历方式：先序遍历、中序遍历和后序遍历。这些遍历方式分别是按照特定顺序访问二叉树中的节点。**

#### 4、先序遍历 ####

**先序遍历函数**`preOrder`按照根节点、左子树、右子树的顺序遍历树，并打印出节点的数据值。

void preOrder(Node *root) {
        
        if (root != NULL) {
        
            printf("%d ", root->data);
            preOrder(root->left);
            preOrder(root->right);
        }
    }

#### 5、中序遍历 ####

**中序遍历函数**`inOrder`按照左子树、根节点、右子树的顺序遍历树，并打印出节点的数据值。

void inOrder(Node *root) {
        
        if (root != NULL) {
        
            inOrder(root->left);
            printf("%d ", root->data);
            inOrder(root->right);
        }
    }

#### 6、后序遍历 ####

**后序遍历函数**`postOrder`按照左子树、右子树、根节点的顺序遍历树，并打印出节点的数据值。

void postOrder(Node *root) {
        
        if (root != NULL) {
        
            postOrder(root->left);
            postOrder(root->right);
            printf("%d ", root->data);
        }
    }

#### 7、main函数 ####

**最后，在**`main`函数中，我们创建了一个空树的根节点，并通过`insertNode`函数插入一些数据。然后分别调用了三种遍历函数，并打印出遍历结果。

int main() {
        
        Node *root = NULL;
        root = insertNode(root, 50);
        insertNode(root, 30);
        insertNode(root, 20);
        insertNode(root, 40);
        insertNode(root, 70);
        insertNode(root, 60);
        insertNode(root, 80);
    
        printf("先序遍历结果：");
        preOrder(root);
    
        printf("\n中序遍历结果：");
        inOrder(root);
    
        printf("\n后序遍历结果：");
        postOrder(root);
    
        return 0;
    }

**这就是一个简单的二叉树实现的详细代码，希望这可以帮助你更好地理解二叉树的工作原理和实现方式。**

### 五、完整代码 ###

#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));
        if (newNode == NULL) {
        
            printf("内存分配失败！\n");
            exit(1);
        }
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    
    // 插入节点
    Node *insertNode(Node *root, int data) {
        
        if (root == NULL) {
        
            return createNode(data);
        } else if (data < root->data) {
        
            root->left = insertNode(root->left, data);
        } else if (data > root->data) {
        
            root->right = insertNode(root->right, data);
        }
        return root;
    }
    
    // 先序遍历
    void preOrder(Node *root) {
        
        if (root != NULL) {
        
            printf("%d ", root->data);
            preOrder(root->left);
            preOrder(root->right);
        }
    }
    
    // 中序遍历
    void inOrder(Node *root) {
        
        if (root != NULL) {
        
            inOrder(root->left);
            printf("%d ", root->data);
            inOrder(root->right);
        }
    }
    
    // 后序遍历
    void postOrder(Node *root) {
        
        if (root != NULL) {
        
            postOrder(root->left);
            postOrder(root->right);
            printf("%d ", root->data);
        }
    }
    
    int main() {
        
        Node *root = NULL;
        root = insertNode(root, 50);
        insertNode(root, 30);
        insertNode(root, 20);
        insertNode(root, 40);
        insertNode(root, 70);
        insertNode(root, 60);
        insertNode(root, 80);
    
        printf("先序遍历结果：");
        preOrder(root);
    
        printf("\n中序遍历结果：");
        inOrder(root);
    
        printf("\n后序遍历结果：");
        postOrder(root);
    
        return 0;
    }