devbox
小蓝xlanll
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：小蓝xlanll | 2024-06-11 13:40:57

赞

踩

二叉链表

目录

一、引言

二、什么是二叉链表

三、二叉链表的结构

四、二叉链表的实现

1. 创建二叉链表

2. 遍历二叉链表

3. 插入节点

4. 删除节点

五、应用场景

六、总结

七、代码示例

一、引言

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

二、什么是二叉链表

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

三、二叉链表的结构

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

  1. struct TreeNode {
  2.     int val;
  3.     TreeNode *left;
  4.     TreeNode *right;
  5.     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  6. };

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

四、二叉链表的实现

1. 创建二叉链表

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

  1. TreeNode* createTree() {
  2.     int val;
  3.     cin >> val;
  4.     if (val == -1) {
  5.         return NULL;
  6.     }
  7.     TreeNode* root = new TreeNode(val);
  8.     root->left = createTree();
  9.     root->right = createTree();
  10.     return root;
  11. }

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

2. 遍历二叉链表

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

前序遍历的实现如下：

  1. void preOrder(TreeNode* root) {
  2.     if (root == NULL) {
  3.         return;
  4.     }
  5.     cout << root->val << " ";
  6.     preOrder(root->left);
  7.     preOrder(root->right);
  8. }

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

中序遍历的实现如下：

  1. void inOrder(TreeNode* root) {
  2.     if (root == NULL) {
  3.         return;
  4.     }
  5.     inOrder(root->left);
  6.     cout << root->val << " ";
  7.     inOrder(root->right);
  8. }

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

后序遍历的实现如下：

  1. void postOrder(TreeNode* root) {
  2.     if (root == NULL) {
  3.         return;
  4.     }
  5.     postOrder(root->left);
  6.     postOrder(root->right);
  7.     cout << root->val << " ";
  8. }

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

3. 插入节点

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

  1. TreeNode* insertNode(TreeNode* root, int val) {
  2.     if (root == NULL) {
  3.         return new TreeNode(val);
  4.     }
  5.     if (val < root->val) {
  6.         root->left = insertNode(root->left, val);
  7.     } else {
  8.         root->right = insertNode(root->right, val);
  9.     }
  10.     return root;
  11. }

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

4. 删除节点

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

  1. TreeNode* deleteNode(TreeNode* root, int val) {
  2.     if (root == NULL) {
  3.         return NULL;
  4.     }
  5.     if (val < root->val) {
  6.         root->left = deleteNode(root->left, val);
  7.     } else if (val > root->val) {
  8.         root->right = deleteNode(root->right, val);
  9.     } else {
  10.         if (root->left == NULL) {
  11.             TreeNode* tmp = root->right;
  12.             delete root;
  13.             return tmp;
  14.         } else if (root->right == NULL) {
  15.             TreeNode* tmp = root->left;
  16.             delete root;
  17.             return tmp;
  18.         } else {
  19.             TreeNode* tmp = root->right;
  20.             while (tmp->left != NULL) {
  21.                 tmp = tmp->left;
  22.             }
  23.             root->val = tmp->val;
  24.             root->right = deleteNode(root->right, tmp->val);
  25.         }
  26.     }
  27.     return root;
  28. }

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

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

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

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

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

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

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

五、应用场景

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

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

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

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

六、总结

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

七、代码示例

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

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. // 二叉树节点定义
  5. struct TreeNode {
  6.     int val;
  7.     TreeNode* left;
  8.     TreeNode* right;
  9.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  10. };
  11.  
  12. // 二叉树类定义
  13. class BinaryTree {
  14. public:
  15.     BinaryTree() : root(nullptr) {}
  16.     ~BinaryTree() { destroy(root); }
  17.  
  18.     // 插入节点
  19.     void insert(int val) {
  20.         insert(root, val);
  21.     }
  22.  
  23.     // 删除节点
  24.     void remove(int val) {
  25.         remove(root, val);
  26.     }
  27.  
  28.     // 查找节点
  29.     bool find(int val) {
  30.         return find(root, val);
  31.     }
  32.  
  33.     // 前序遍历
  34.     void preOrder() {
  35.         preOrder(root);
  36.     }
  37.  
  38.     // 中序遍历
  39.     void inOrder() {
  40.         inOrder(root);
  41.     }
  42.  
  43.     // 后序遍历
  44.     void postOrder() {
  45.         postOrder(root);
  46.     }
  47.  
  48. private:
  49.     TreeNode* root;
  50.  
  51.     // 插入节点
  52.     void insert(TreeNode*& node, int val) {
  53.         if (node == nullptr) {
  54.             node = new TreeNode(val);
  55.         } else if (val < node->val) {
  56.             insert(node->left, val);
  57.         } else if (val > node->val) {
  58.             insert(node->right, val);
  59.         }
  60.     }
  61.  
  62.     // 删除节点
  63.     void remove(TreeNode*& node, int val) {
  64.         if (node == nullptr) {
  65.             return;
  66.         } else if (val < node->val) {
  67.             remove(node->left, val);
  68.         } else if (val > node->val) {
  69.             remove(node->right, val);
  70.         } else {
  71.             if (node->left == nullptr && node->right == nullptr) {
  72.                 delete node;
  73.                 node = nullptr;
  74.             } else if (node->left == nullptr) {
  75.                 TreeNode* temp = node;
  76.                 node = node->right;
  77.                 delete temp;
  78.             } else if (node->right == nullptr) {
  79.                 TreeNode* temp = node;
  80.                 node = node->left;
  81.                 delete temp;
  82.             } else {
  83.                 TreeNode* temp = findMin(node->right);
  84.                 node->val = temp->val;
  85.                 remove(node->right, temp->val);
  86.             }
  87.         }
  88.     }
  89.  
  90.     // 查找节点
  91.     bool find(TreeNode* node, int val) {
  92.         if (node == nullptr) {
  93.             return false;
  94.         } else if (val < node->val) {
  95.             return find(node->left, val);
  96.         } else if (val > node->val) {
  97.             return find(node->right, val);
  98.         } else {
  99.             return true;
  100.         }
  101.     }
  102.  
  103.     // 查找最小节点
  104.     TreeNode* findMin(TreeNode* node) {
  105.         while (node->left != nullptr) {
  106.             node = node->left;
  107.         }
  108.         return node;
  109.     }
  110.  
  111.     // 前序遍历
  112.     void preOrder(TreeNode* node) {
  113.         if (node != nullptr) {
  114.             cout << node->val << " ";
  115.             preOrder(node->left);
  116.             preOrder(node->right);
  117.         }
  118.     }
  119.  
  120.     // 中序遍历
  121.     void inOrder(TreeNode* node) {
  122.         if (node != nullptr) {
  123.             inOrder(node->left);
  124.             cout << node->val << " ";
  125.             inOrder(node->right);
  126.         }
  127.     }
  128.  
  129.     // 后序遍历
  130.     void postOrder(TreeNode* node) {
  131.         if (node != nullptr) {
  132.             postOrder(node->left);
  133.             postOrder(node->right);
  134.             cout << node->val << " ";
  135.         }
  136.     }
  137.  
  138.     // 销毁节点
  139.     void destroy(TreeNode* node) {
  140.         if (node != nullptr) {
  141.             destroy(node->left);
  142.             destroy(node->right);
  143.             delete node;
  144.         }
  145.     }
  146. };
  147.  
  148. // 测试代码
  149. int main() {
  150.     BinaryTree tree;
  151.     tree.insert(5);
  152.     tree.insert(3);
  153.     tree.insert(7);
  154.     tree.insert(1);
  155.     tree.insert(4);
  156.     tree.insert(6);
  157.     tree.insert(8);
  158.  
  159.     cout << "前序遍历: ";
  160.     tree.preOrder();
  161.     cout << endl;
  162.  
  163.     cout << "中序遍历: ";
  164.     tree.inOrder();
  165.     cout << endl;
  166.  
  167.     cout << "后序遍历: ";
  168.     tree.postOrder();
  169.     cout << endl;
  170.  
  171.     cout << "查找节点 4: " << (tree.find(4) ? "存在" : "不存在") << endl;
  172.  
  173.     tree.remove(3);
  174.     cout << "删除节点 3 后的中序遍历: ";
  175.     tree.inOrder();
  176.     cout << endl;
  177.  
  178.     return 0;
  179. }

输出示例：
前序遍历: 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 
 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/703414
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号