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

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

二叉树

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

一、什么是二叉树

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

     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;
}
阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
标签: c++
返回列表

上一篇：mac 文件批量重命名001开始

下一篇：JavaWeb——2.注解

“【二叉树教程详解以及C语言/C++实现二叉树】” 的相关文章

从使用角度解读c++20 协程_c++20 协程1年前 (2023-02-02)
c++基础篇之C++ STL 教程1年前 (2023-02-02)
c++入门篇之C++ 引用1年前 (2023-02-02)
c++11 标准模板（STL）（std::forward1年前 (2023-02-02)
C++基于STL的演讲比赛流程管理系统1年前 (2023-02-02)
【C++】map和set的使用1年前 (2023-02-02)
C++设计模式（2）——工厂方法模式1年前 (2023-02-02)
第13届蓝桥杯青少组C++中级组省赛1年前 (2023-02-02)
C++：C++全局变量：看完还不懂全局变量来捶我1年前 (2023-02-02)
【C++】从0到1入门C++编程学习笔记 - 基础入门篇：运算符1年前 (2023-02-02)

阿里云国际版