源代码网盘地址：点击打开链接
三叉 链表 比 二叉链表多了 一个指向 父节点 的指针，这在 需要 找 父亲，祖先 ，求任意两个节点的最近祖先等算法的 实现 ，很有帮助。所以当算法中 有大量这样的操作就需要把数据结构定义为三叉链表。
当 算法中 经常需要 遍历 或者 查找 节点 在 遍历过程中的 前驱 后继 指针，就需要 把数据结构 定义为 线索 二叉链表。
其实 写 数据结构 不难，但是 如何 从 实际问题中 选择 合适的 数据结构，这就不容易了。计算机里 有一句 至理名言：程序 = 数据结构+ 算法。
闲话不多说了，下面的代码没什么难的。
主要 说一下 三叉链表的创建，用 层序法 来 创建 再合适 不过了。算法 也比较简单。仔细看一下，应该会明白。
特别说明：《数据结构.严蔚敏版》 一书中，说到 在 用 三叉链表 实现 先序，中序，，后序遍历时，不需要借助栈，但 算法比较 复杂。
一直 想用 代码 实现一下。苦于 时间问题 和 无 算法 思路。待 以后 慢慢填补。
// BinaryTree3.cpp : 三叉链表//#include "stdafx.h"#include "stack.h"#include "queue.h"typedef char ElementType;typedef struct TreeNode{ElementType data;TreeNode * father;TreeNode * leftChild;TreeNode * rightChild;}*Tree;void treeInit(Tree * tree){* tree = NULL;}//分配一个节点Tree makeNode(){ElementType data = ' ';scanf("%c\n",&data);if (data == '#'){return NULL;}Tree t = (Tree)malloc(sizeof(TreeNode));t->data = data;return t;}//根据层序 来 建立 三叉链表 再合适不过了void treeCreate(Tree * tree){*tree = makeNode();if (*tree != NULL){LinkQueue queue;queueInit(&queue);enqueue(&queue,*tree);(*tree)->father = NULL;//根节点父亲是空..while (!queueEmpty(queue)){Tree father;dequeue(&queue,&father);Tree left = makeNode();father->leftChild = left;if(left != NULL){left->father = father;enqueue(&queue,left);}Tree right = makeNode();father->rightChild = right;if (right != NULL){right->father = father;enqueue(&queue,right);}}//释放队列内存queueDestory(&queue);}}//按照先序非递归 来清空void treeClear(Tree * tree){if (tree != NULL){linkStack stack;stackInit(&stack);stackPush(&stack,*tree);while (!stackEmpty(stack)){Tree t;stackPop(&stack,&t);//必须先 右子树 进栈，后左子树进栈if (t->rightChild != NULL){stackPush(&stack,t->rightChild);}if (t->leftChild != NULL){stackPush(&stack,t->leftChild);}//必须最后释放，不然 会出 内存问题..free(t);}*tree = NULL;//空树..stackDestory(&stack);}}void treeDestory(Tree * tree){treeClear(tree);}// 当 tree == null 时，树为空..bool treeEmpty(Tree tree){return tree == NULL ? true : false;}//中序非递归…int treeLen(Tree tree){int len = 0;linkStack stack;stackInit(&stack);stackPush(&stack,tree);while (!stackEmpty(stack)){Tree t;while (stackGetTop(stack,&t) && t) stackPush(&stack,t->leftChild);stackPop(&stack,&t);//空指针退栈if (!stackEmpty(stack)){stackPop(&stack,&t);len ++;stackPush(&stack,t->rightChild);}}//释放栈空间stackDestory(&stack);return len;}//三叉链表先序void preOrderTraverse(Tree t){}//三叉链表中序void inOrderTraverse(Tree t){}//三叉链表后序void postOrderTraverse(Tree t){}//层序 //利用队列 void levelOrderTraverse(Tree tree){if (tree != NULL){LinkQueue queue;queueInit(&queue);enqueue(&queue,tree);while (dequeue(&queue,&tree) && tree){printf("%c\t",tree->data);if (tree->leftChild != NULL){enqueue(&queue,tree->leftChild);}if (tree->rightChild != NULL){enqueue(&queue,tree->rightChild);}}queueDestory(&queue);} } Tree treeGetNode(Tree t, ElementType data){Tree findTree = NULL;if (t != NULL){if (t->data == data){return t;}findTree = treeGetNode(t->leftChild,data);if (findTree == NULL){findTree = treeGetNode(t->rightChild,data);}}return findTree;}void treeGetAllParent(Tree t,ElementType data){Tree findTree = treeGetNode(t,data);if (findTree != NULL){printf("%c 节点的 祖先是：",data);Tree father = findTree->father;while (father != NULL){printf("%c\t",father->data);father = father->father;}printf("\n");}else{printf("%c 节点的无祖先 ",data);}}int _tmain(int argc, _TCHAR* argv[]){Tree tree;printf("—————层序生成三叉链表————-\n");treeCreate(&tree);levelOrderTraverse(tree);char * isEmpyt = treeEmpty(tree) ? "是" : "不是";int len = treeLen(tree);printf("树是否为空：%s,树的长度为：%d\n",isEmpyt,len);printf("—————查找祖先问题（用三叉链表）————-\n");treeGetAllParent(tree,'i');treeDestory(&tree);return 0;}运行截图：
与其临渊羡鱼，不如退而结网。
