当前位置：首页 > news >正文

9 二叉树-添加

news 来源：原创 2024/5/6 11:13:51

二叉树是 0 或多个结点的集合，一个结点最多有两个子结点。

在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
#define printd(n) printf("%d\n", n)

typedef struct Node *Nodeptr;
typedef int ElementType;
typedef int boolean;

// 某个结点
typedef struct Node {
	// 结点保存的数据
    ElementType data;
	// 结点的左子结点
    Nodeptr left;
    // 结点的右子结点
    Nodeptr right;
} Node;

// 二叉树
typedef struct {
    // 根结点
    Nodeptr root;
} Tree;

init：初始化。

void init(Tree *tree) {
    tree->root = NULL;
}

add(ElementType e)：添加。

原则：小的放左边，大的放右边。如添加 5、3、2、4、7、6、8 时，树为：

在这里插入图片描述

过程：创建结点 node。

当树中一个结点都没有时，定 node 为根结点。

if (tree->root == NULL) {
    tree->root = node;
}

当树中一个结点至少有一个结点时，将 node 与 root 比较，才能确定 node 是放在 root 的左还是右边。

if (tree->root != NULL) {
    compare(node, root);
}

1：node 小于 root。

1.1 如果 root 的左子结点为 NULL，定 node 为 root 的左子结点。

1.2 如果 root 有左子结点，将 node 与 root.left 比较。

if (node->data < root->data) {
    if (root->left == NULL) {
        root->left = node;
    } else {
        compare(node, root->left);
    }
}

2：node 大于等于 root。

2.1 如果 root 的右子结点为 NULL，定 node 为 root 的右子结点。

2.2 如果 root 有右子结点，将 node 与 root.right 比较。

if (node->data >= root->data) {
    if (root->right == NULL) {
        root->right = node;
    } else {
        compare(node, root->right);
    }
}

综合：

void compare(Nodeptr node, Nodeptr root) {
    if (node->data < root->data) {
        if (root->left == NULL) {
            root->left = node;
        } else {
            compare(node, root->left);
        }
    } else {
        if (root->right == NULL) {
            root->right = node;
        } else {
            compare(node, root->right);
        }
    }
}

boolean add(Tree *tree, ElementType e) {
    Node *node = calloc(1, sizeof(Node));
    node->data = e;
    node->left = NULL;
    node->right = NULL;

    if (tree->root == NULL) {
        tree->root = node;
    } else {
        compare(node, tree->root);
    }
    return true;
}

测试程序：

添加 5、3、2、4、7、6、8 时，树为：

在这里插入图片描述

程序运行输出应为 root = 5、root.left = 3、root.right = 7、root.left.left = 2、root.left.right = 4、root.right.left = 6、root.right.right = 8。

而 2、4、6、8 无子结点，所以它们的左子结点、右子结点都为 NULL，转为整数输出 0。

int main() {
    Tree tree;
    init(&tree);
    add(&tree, 5);
    add(&tree, 3);
    add(&tree, 7);
    add(&tree, 2);
    add(&tree, 4);
    add(&tree, 6);
    add(&tree, 8);
    printd(tree.root->data);// 5
    printd(tree.root->left->data);// 3
    printd(tree.root->right->data);// 7
    printd(tree.root->left->left->data);// 2
    printd(tree.root->left->right->data);// 4
    printd(tree.root->right->left->data);// 6
    printd(tree.root->right->right->data);// 8

    printd(tree.root->left->left->left);// 0
    printd(tree.root->left->left->right);// 0
    printd(tree.root->left->right->left);// 0
    printd(tree.root->left->right->right);// 0
    printd(tree.root->right->left->left);// 0
    printd(tree.root->right->left->right);// 0
    printd(tree.root->right->right->left);// 0
    printd(tree.root->right->right->right);// 0
}