分析数据结构（27） 三叉链表的实现

源代码网盘地址：点击打开链接

三叉链表相较于二叉链表多出一个用于指向父节点的指针，这种结构在需要查找父节点、祖先节点或确定任意两个节点的最近公共祖先等操作时具有显著优势。因此，当算法中频繁出现此类操作时，应当将数据结构定义为三叉链表。

若在算法执行过程中经常涉及遍历操作或需要获取当前节点的前驱与后继指针，则应将数据结构设计为线索二叉链表。

实际上，编写数据结构本身并不困难，然而如何从实际问题出发选择最合适的结构则并非易事。计算机领域有一条经典原则：程序 = 数据结构 + 算法。

此处暂不赘述其他内容，下方的代码实现并不复杂。

重点说明一下三叉链表的构建过程，采用层序法进行创建无疑是最为恰当的选择。相关算法逻辑也较为直观，只要仔细阅读便能理解。

特别说明：《数据结构.严蔚敏版》一书中提到，在使用三叉链表实现先序、中序及后序遍历时，并不需要借助栈结构，但相应的算法实现则较为复杂。

一直以来都希望用代码实现这一部分功能，但由于时间限制以及缺乏明确的算法思路，暂时搁置。未来将逐步完善相关内容。

 // BinaryTree3.cpp : 三叉链表

    
 //
    
  
    
 #include "stdafx.h"
    
 #i