数据结构-二叉链表的结构与实现

爱被打了一巴掌 2024-03-22 15:14 61阅读 0赞

**目录**

一、引言

二、什么是二叉链表

三、二叉链表的结构

四、二叉链表的实现

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  
>