数据结构-二叉链表的结构与实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构-二叉链表的结构与实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、引言

二、什么是二叉链表

三、二叉链表的结构

四、二叉链表的实现

1. 创建二叉链表

2. 遍历二叉链表

3. 插入节点

4. 删除节点

五、应用场景

六、总结

七、代码示例

一、引言

数据结构是计算机科学中的重要概念，它是计算机程序设计的基础。二叉链表是一种常见的数据结构，它可以用来表示树形结构，如二叉树等。本篇博客将介绍二叉链表的结构与实现，以及它在实际应用中的应用场景。

二、什么是二叉链表

二叉链表是一种特殊的链表，它的每个节点都有两个指针，一个指向左子树，一个指向右子树。这种结构可以用来表示树形结构，如二叉树等。

三、二叉链表的结构

二叉链表的结构如下所示：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

其中，`val`表示节点的值，`left`和`right`分别表示左子树和右子树。

四、二叉链表的实现

1. 创建二叉链表

创建二叉链表的过程可以通过递归实现。具体实现如下：

TreeNode* createTree() {
    int val;
    cin >> val;
    if (val == -1) {
        return NULL;
    }
    TreeNode* root = new TreeNode(val);
    root->left = createTree();
    root->right = createTree();
    return root;
}

在这个函数中，我们首先读取一个整数，如果这个整数为-1，则表示当前节点为空，返回`NULL`。否则，我们创建一个新的节点，并将这个整数作为节点的值。然后，递归创建左子树和右子树，并将它们分别赋值给当前节点的`left`和`right`指针。

2. 遍历二叉链表

遍历二叉链表有三种方式：前序遍历、中序遍历和后序遍历。它们的区别在于遍历的顺序不同。

前序遍历的实现如下：

void preOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    cout << root->val << " ";
    preOrder(root->left);
    preOrder(root->right);
}

在这个函数中，我们首先输出当前节点的值，然后递归遍历左子树和右子树。

中序遍历的实现如下：

void inOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    cout << root->val << " ";
    inOrder(root->right);
}

在这个函数中，我们首先递归遍历左子树，然后输出当前节点的值，最后递归遍历右子树。

后序遍历的实现如下：

void postOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val << " ";
}

在这个函数中，我们首先递归遍历左子树和右子树，然后输出当前节点的值。

3. 插入节点

插入节点的过程可以通过递归实现。具体实现如下：

TreeNode* insertNode(TreeNode* root, int val) {
    if (root == NULL) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insertNode(root->left, val);
    } else {
        root->right = insertNode(root->right, val);
    }
    return root;
}

在这个函数中，我们首先判断当前节点是否为空，如果为空，则创建一个新的节点，并将它作为当前节点的子节点。否则，我们比较要插入的值和当前节点的值的大小关系，如果要插入的值小于当前节点的值，则递归插入到左子树中，否则递归插入到右子树中。

4. 删除节点

删除节点的过程可以通过递归实现。具体实现如下：

TreeNode* deleteNode(TreeNode* root, int val) {
    if (root == NULL) {
        return NULL;
    }
    if (val < root->val) {
        root->left = deleteNode(root->left, val);
    } else if (val > root->val) {
        root->right = deleteNode(root->right, val);
    } else {
        if (root->left == NULL) {
            TreeNode* tmp = root->right;
            delete root;
            return tmp;
        } else if (root->right == NULL) {
            TreeNode* tmp = root->left;
            delete root;
            return tmp;
        } else {
            TreeNode* tmp = root->right;
            while (tmp->left != NULL) {
                tmp = tmp->left;
            }
            root->val = tmp->val;
            root->right = deleteNode(root->right, tmp->val);
        }
    }
    return root;
}

在这个函数中，我们首先判断当前节点是否为空，如果为空，则返回`NULL`。否则，我们比较要删除的值和当前节点的值的大小关系

这段代码是一个二叉搜索树的删除节点操作。二叉搜索树是一种特殊的二叉树，它的每个节点都比它的左子树中的所有节点大，比它的右子树中的所有节点小。删除节点的操作需要考虑三种情况：

1. 要删除的节点没有子节点，直接删除即可。

2. 要删除的节点只有一个子节点，将子节点替换要删除的节点即可。

3. 要删除的节点有两个子节点，需要找到右子树中最小的节点，将它的值赋给要删除的节点，然后再删除右子树中最小的节点。

这段代码使用递归实现了二叉搜索树的删除节点操作。如果要删除的节点比当前节点小，就递归到左子树中删除；如果要删除的节点比当前节点大，就递归到右子树中删除；如果要删除的节点就是当前节点，就按照上述三种情况进行处理。最后返回根节点。

好的，下面是五、应用场景和六、总结的内容：

五、应用场景

1. 二叉链表可以用于实现二叉树，二叉树是一种常用的数据结构，广泛应用于计算机科学和工程领域。

2. 二叉链表可以用于实现哈夫曼树，哈夫曼树是一种带权路径长度最短的树，广泛应用于数据压缩和编码领域。

3. 二叉链表可以用于实现二叉堆，二叉堆是一种基于完全二叉树的数据结构，广泛应用于堆排序、优先队列等算法中。

4. 二叉链表可以用于实现二叉搜索树，二叉搜索树是一种特殊的二叉树，广泛应用于查找、排序、删除等算法中。

六、总结

二叉链表是一种常用的数据结构，它可以用于实现二叉树、哈夫曼树、二叉堆、二叉搜索树等算法。二叉链表的结构相对简单，实现起来也比较容易，但是需要注意指针的使用，避免出现空指针和死循环等问题。在实际应用中，我们需要根据具体的需求选择合适的数据结构，以提高算法的效率和性能。

七、代码示例

以下是C++的二叉链表的完整实现代码，包括节点的定义、插入、删除、查找、遍历等操作：

#include <iostream>
using namespace std;

// 二叉树节点定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 二叉树类定义
class BinaryTree {
public:
    BinaryTree() : root(nullptr) {}
    ~BinaryTree() { destroy(root); }

    // 插入节点
    void insert(int val) {
        insert(root, val);
    }

    // 删除节点
    void remove(int val) {
        remove(root, val);
    }

    // 查找节点
    bool find(int val) {
        return find(root, val);
    }

    // 前序遍历
    void preOrder() {
        preOrder(root);
    }

    // 中序遍历
    void inOrder() {
        inOrder(root);
    }

    // 后序遍历
    void postOrder() {
        postOrder(root);
    }

private:
    TreeNode* root;

    // 插入节点
    void insert(TreeNode*& node, int val) {
        if (node == nullptr) {
            node = new TreeNode(val);
        } else if (val < node->val) {
            insert(node->left, val);
        } else if (val > node->val) {
            insert(node->right, val);
        }
    }

    // 删除节点
    void remove(TreeNode*& node, int val) {
        if (node == nullptr) {
            return;
        } else if (val < node->val) {
            remove(node->left, val);
        } else if (val > node->val) {
            remove(node->right, val);
        } else {
            if (node->left == nullptr && node->right == nullptr) {
                delete node;
                node = nullptr;
            } else if (node->left == nullptr) {
                TreeNode* temp = node;
                node = node->right;
                delete temp;
            } else if (node->right == nullptr) {
                TreeNode* temp = node;
                node = node->left;
                delete temp;
            } else {
                TreeNode* temp = findMin(node->right);
                node->val = temp->val;
                remove(node->right, temp->val);
            }
        }
    }

    // 查找节点
    bool find(TreeNode* node, int val) {
        if (node == nullptr) {
            return false;
        } else if (val < node->val) {
            return find(node->left, val);
        } else if (val > node->val) {
            return find(node->right, val);
        } else {
            return true;
        }
    }

    // 查找最小节点
    TreeNode* findMin(TreeNode* node) {
        while (node->left != nullptr) {
            node = node->left;
        }
        return node;
    }

    // 前序遍历
    void preOrder(TreeNode* node) {
        if (node != nullptr) {
            cout << node->val << " ";
            preOrder(node->left);
            preOrder(node->right);
        }
    }

    // 中序遍历
    void inOrder(TreeNode* node) {
        if (node != nullptr) {
            inOrder(node->left);
            cout << node->val << " ";
            inOrder(node->right);
        }
    }

    // 后序遍历
    void postOrder(TreeNode* node) {
        if (node != nullptr) {
            postOrder(node->left);
            postOrder(node->right);
            cout << node->val << " ";
        }
    }

    // 销毁节点
    void destroy(TreeNode* node) {
        if (node != nullptr) {
            destroy(node->left);
            destroy(node->right);
            delete node;
        }
    }
};

// 测试代码
int main() {
    BinaryTree tree;
    tree.insert(5);
    tree.insert(3);
    tree.insert(7);
    tree.insert(1);
    tree.insert(4);
    tree.insert(6);
    tree.insert(8);

    cout << "前序遍历: ";
    tree.preOrder();
    cout << endl;

    cout << "中序遍历: ";
    tree.inOrder();
    cout << endl;

    cout << "后序遍历: ";
    tree.postOrder();
    cout << endl;

    cout << "查找节点 4: " << (tree.find(4) ? "存在" : "不存在") << endl;

    tree.remove(3);
    cout << "删除节点 3 后的中序遍历: ";
    tree.inOrder();
    cout << endl;

    return 0;
}

输出示例：
前序遍历: 5 3 1 4 7 6 8
中序遍历: 1 3 4 5 6 7 8
后序遍历: 1 4 3 6 8 7 5
查找节点 4: 存在
删除节点 3 后的中序遍历: 1 4 5 6 7 8
文章来源地址https://www.toymoban.com/news/detail-720882.html

到了这里，关于数据结构-二叉链表的结构与实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！