关于双向链表和二叉树链表的区别

本是古典何须时尚 2023-10-05 11:36 37阅读 0赞

双向链表和二叉树链表区别为：**节点指针数量不同**、**访问方向权限不同**、**节点存储内容不同**。双向链表和二叉树链表都能从链表中的任何一个结点出发能找到任何其他结点。都用来存放线性数组中的数据元素。

**一、节点指针数量不同**

1、双向链表：双向链表的每个数据结点中包含一个元素和两个指针。

2、二叉树链表：二叉树链表的每个数据结点中包含一个元素和只有一个指针。

**二、访问方向权限不同**

1、双向链表：双向链表除了首尾节点，其他节点都能访问他的前节点和后节点。双向链表节点两个指针分别指向前一节点和后一节点。

2、二叉树链表：二叉树链表是单向链表，只能指向前面节点。不能向后。二叉树链表的每个节点只能访问他的左右孩子节点，不能向上访问他的父节点。

**三、节点存储内容不同**

二叉树与双向链表都是一种极其重要的数据结构。它们与数组、向量、链表一样都是一种顺序容器，提供了按位置访问数据的方法。但是有一个缺点，它们都是按照位置来确定数据，想要通过值来查找数据，只能通过遍历的方式实现。而二叉树在很大程度上解决了这个缺点，二叉树是按值来保存元素，也按值来访问元素。而双向链表的每个节点都只能保存两个指针。

**举例：**

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。

下图为一个最基本的普通二叉树链表。

![199f6b54d29d41a6e832c0acf0041103.png][]

**二叉树的存储**

**1,顺序存储**

使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。

![8c14058d3516aef083eaeda2952f7da5.png][]

![c120334c24808c0b06b6c26bb3988119.png][]

用数组顺序存储一般只适合完全二叉树，如果二叉树出现倾斜情况，采用顺序存储的方式将是十分浪费空间

比如上面的489没有的话

![0e3506451720ff764c3b20018777d63f.png][]

存储表现形式将是如下（^代表为空）：

![da535ed91faece96394e61a3e97149b1.png][]

**2，二叉链表存储**

这个就跟双向链表有点儿像了

采用链式存储。由二叉树定义可知，二叉树的每个结点最多有两个孩子。因此，可以将结点数据结构定义为一个数据和两个指针域

![1f484c7d2c42463d3b6774e4777a2050.png][]

![45f48df0e32b04c26ddc430c03ac8917.png][]

下面为二叉树链表节点定义代码：

//定义结点代码：
    typedef struct BiTNode{
        TElemType data;//数据
        struct BiTNode *lchild, *rchild;//左右孩子指针
    } BiTNode, *BiTree;

下面为双向链表结构定义：

// C++ 64位双向链表
    typedef struct LIST_ENTRY64 {
        ULONGLONG Flink;
        ULONGLONG Blink;
      } LIST_ENTRY64;
    typedef LIST_ENTRY64 *PLIST_ENTRY64;
    
    // Delphi 64位双向链表
       PLIST_ENTRY64 =^LIST_ENTRY64;
       LIST_ENTRY64 =packed record
         Flink:PVOID64;//ULONGLONG;   //8Byte
         Blink:PVOID64;//ULONGLONG;
       end;
    
    // Delphi 32位双向链表
      PListEntry = ^TListEntry;
      _LIST_ENTRY = record
        Flink: PListEntry;
        Blink: PListEntry;
      end;
      TListEntry = _LIST_ENTRY;
      LIST_ENTRY = _LIST_ENTRY;
    
    // C++ 32位双向链表
      typedef struct _LIST_ENTRY {
        struct _LIST_ENTRY *Flink;
        struct _LIST_ENTRY *Blink;
      } LIST_ENTRY,*PLIST_ENTRY,*RESTRICTED_POINTER PRLIST_ENTRY;

**注：LIST\_ENTRY 双向链表结构在WINDOWS中一般主要用于内核态**

**一句话总结：**

双向链表是指除了首尾节点，其他节点都能访问他的前节点和后节点。二叉树链表就是二叉树，每个节点只能访问他的左右孩子节点，不能向上访问他的父节点，所以二叉树是单向的

[199f6b54d29d41a6e832c0acf0041103.png]: https://img-blog.csdnimg.cn/img_convert/199f6b54d29d41a6e832c0acf0041103.png
[8c14058d3516aef083eaeda2952f7da5.png]: https://img-blog.csdnimg.cn/img_convert/8c14058d3516aef083eaeda2952f7da5.png
[c120334c24808c0b06b6c26bb3988119.png]: https://img-blog.csdnimg.cn/img_convert/c120334c24808c0b06b6c26bb3988119.png
[0e3506451720ff764c3b20018777d63f.png]: https://img-blog.csdnimg.cn/img_convert/0e3506451720ff764c3b20018777d63f.png
[da535ed91faece96394e61a3e97149b1.png]: https://img-blog.csdnimg.cn/img_convert/da535ed91faece96394e61a3e97149b1.png
[1f484c7d2c42463d3b6774e4777a2050.png]: https://img-blog.csdnimg.cn/img_convert/1f484c7d2c42463d3b6774e4777a2050.png
[45f48df0e32b04c26ddc430c03ac8917.png]: https://img-blog.csdnimg.cn/img_convert/45f48df0e32b04c26ddc430c03ac8917.png