看数据结构写代码（27) 三叉链表的实现

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

三叉 链表 比 二叉链表多了 一个指向 父节点 的指针，这在 需要 找 父亲，祖先 ，求任意两个节点的最近祖先等算法的 实现 ，很有帮助。所以当算法中 有大量这样的操作就需要把数据结构定义为三叉链表。

 当 算法中 经常需要 遍历 或者 查找 节点 在 遍历过程中的 前驱 后继 指针，就需要 把数据结构 定义为 线索 二叉链表。

其实 写 数据结构 不难，但是 如何 从 实际问题中 选择 合适的 数据结构，这就不容易了。计算机里 有一句 至理名言：程序 = 数据结构+ 算法。

闲话不多说了，下面的代码没什么难的。

主要 说一下 三叉链表的创建，用 层序法 来 创建 再合适 不过了。算法 也比较简单。仔细看一下，应该会明白。

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

一直 想用 代码 实现一下。苦于 时间问题 和 无 算法 思路。待 以后  慢慢填补。

// 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;
}

看数据结构写代码（27) 三叉链表的实现

原文：http://blog.csdn.net/fuming0210sc/article/details/44621023