链表为线性数据结构，为何可用于实现非线性的树结构？

首先要明确：数据结构的线性/非线性分类，核心看的是整体元素间的逻辑关系，而非单个节点的实现结构。

1. 线性数据结构的本质 #

链表被定义为线性结构，是因为它的元素之间是一对一的逻辑关系：每个节点（除首尾）只有一个前驱节点和一个后继节点，整体形成一条单一的遍历路径——你只能从表头开始，沿着指针依次走到表尾，没有任何分支。

比如单链表的节点结构是：

typedef struct ListNode
{
    int key;
    struct ListNode *next;
} ListNode;

单个节点只有一个指向后继的指针，决定了整个链表的逻辑关系是线性的。

2. 树的非线性核心 #

树属于非线性结构，原因是它的元素之间是一对多的逻辑关系：一个父节点可以有多个子节点，遍历过程中会出现分支（比如二叉树的左、右子树路径）。

你给出的二叉树节点结构：

typedef struct Node
{
   int key;
   struct Node *left;
   struct Node *right;
} Node;

单个节点有两个子节点指针，这直接导致整体结构呈现分层分支的逻辑关系——从根节点出发，你可以选择走左子树或右子树，这和链表的单一遍历路径完全不同，这才是树被归为非线性的关键。

3. 为啥链表能用来实现树？ #

这里的"用来实现"指的是复用了"带指针的结构体"这种底层实现方式，而非链表本身的结构特性。链表的节点是一种基础的、可扩展的存储单元设计，我们可以给它增加更多指针，改变元素间的逻辑关系，从而构建出树这种非线性结构。但这并不意味着树是"复杂的链表"——两者的整体逻辑模型完全不同：链表是线性链，树是分支层级结构。

简单总结：

• 链表的线性，是整体逻辑关系的线性；
• 树的非线性，是整体逻辑关系的非线性；
• 两者只是共享了"用指针结构体存储元素"的实现方式，但本质是完全不同的数据结构。

内容的提问来源于stack exchange，提问作者Kausthubha RS