【数据结构】初识二叉树+C语言实现

课堂笔记

数组,链表它们有一个共同的特点——线性表

线性表由若干元素按照线性结构(一对一的关系)组成的有限序列,是一对一的关系。

那么一对多是由什么实现的呢?树!

树是一个由n个节点组成的有限集合,子树是该集合的子集。

度:节点所拥有的子树个数。二叉树:度小于等于2,大于等于0。度为0的节点叫做叶子节点。

深度:树的最大层次

二叉树是有序树,完全二叉树的节点从上到下,从左到右的节点顺序不能中断。

满二叉树,完全二叉树,非完全二叉树

二叉树遍历方式:先序,中序,后序

C语言实现

#include <stdio.h>
#include <stdlib.h>
​
// 定义二叉树节点结构体
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};
​
// 创建新节点
struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}
​
// 插入节点
struct TreeNode* insert(struct TreeNode* root, int val) {
    if (root == NULL) {
        return createNode(val);
    }
    if (val < root->val) {
        root->left = insert(root->left, val);
    } else if (val > root->val) {
        root->right = insert(root->right, val);
    }
    return root;
}
​
// 中序遍历二叉树
void inorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}
​
int main() {
    int a[] = {5, 3, 7, 1, 9, 4};
    int len = sizeof(a) / sizeof(a[0]);
​
    struct TreeNode* root = NULL;
    root = insert(root, a[0]);
    for (int i = 1; i < len; i++) {
        insert(root, a[i]);
    }
​
    inorderTraversal(root); // 输出:1 3 4 5 7 9
}

三种遍历方式

二叉树先序遍历.gif
二叉树中序遍历.gif
二叉树后序遍历.gif
© 版权声明
THE END
点赞14 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容