140
二叉樹中序線索化算法
//
// 二叉樹線索化的頭文件：BinaryThreadTree.h
#ifndef B_T_T_H
#define B_T_T_H
#include <stdio.h>
//
// 返回OK表示正常返回
#define OK 1
//
// 返回ERROR，表示異常返回
#define ERROR 0
//
// 返回OVERFLOW，表示內存溢出
#define OVERFLOW -1
//
// 線索結構體
typedef enum
{
Link = 0, // 指針
Thread = 1 // 線索
}PointerTag;
//
// 樹結點的數據的類型
typedef char ElemType;
//
// 返回值類型
typedef int Status;
//
// 線索二叉樹結構體
typedef struct tagBinaryThreadTree
{
ElemType data;
struct tagBinaryThreadTree *lchild; // 左孩子指針
struct tagBinaryThreadTree *rchild; // 右孩子指針
PointerTag leftTag; // 左標誌
PointerTag rightTag; // 右標誌
}BinThrTree, *LinkBinThrTree;
//
// 按先序順序輸入數據，以建立線索二叉樹
// 輸入的#表示子樹為空
Status CreateBinaryThreadTree(LinkBinThrTree *pBinThrTree);
//
// 中序遍曆線索化二叉樹
Status InOrderTraverse(LinkBinThrTree pBinThrTree);
//
// 線索化
void InThreading(LinkBinThrTree p);
//
// 中序線索化二叉樹
Status InOrderThreading(LinkBinThrTree *threadTree, LinkBinThrTree tree);
#endif
//
// 線索二叉線的實現文件：BinaryThreadTree.c
#include <stdio.h>
#include <stdlib.h>
#include "BinaryThreadTree.h"
LinkBinThrTree pre = NULL; //定義pre為函數InThreading的外部變量，使其指向最後一個節點
//
// 按先序順序輸入數據，以建立線索二叉樹
// 輸入的#表示子樹為空
Status CreateBinaryThreadTree(BinThrTree **pBinThrTree)
{
char ch;
scanf ("%c", &ch);
if (ch == '#')
{
*pBinThrTree = NULL;
}
else
{
*pBinThrTree = (LinkBinThrTree)malloc(sizeof(BinThrTree));
if (!(*pBinThrTree))
{
exit(OVERFLOW);
}
(*pBinThrTree)->data = ch;
(*pBinThrTree)->leftTag = Link;
(*pBinThrTree)->rightTag = Link;
CreateBinaryThreadTree(&(*pBinThrTree)->lchild);
CreateBinaryThreadTree(&(*pBinThrTree)->rchild);
}
return OK;
}
//
// 中序遍曆線索化二叉樹
Status InOrderTraverse(LinkBinThrTree pBinThrTree)
{
LinkBinThrTree p = NULL;
p = pBinThrTree->lchild;
while (p != pBinThrTree)
{
while (p->leftTag == Link)
{
p = p->lchild; // 沿著根向左走到盡頭
}
printf("%c", p->data); // 輸出
// 沿著線索向右走到盡頭
while (p->rightTag == Thread && p->rchild != pBinThrTree)
{
p = p->rchild;
printf("%c", p->data); // 輸出
}
p = p->rchild;
}
return OK;
}
//
// 線索化
void InThreading(LinkBinThrTree p)
{
if (p)
{
InThreading(p->lchild);
if (!p->lchild)
{
p->leftTag = Thread;
p->lchild = pre;
}
if (!pre->rchild)
{
pre->rightTag = Thread;
pre->rchild = p;
}
pre = p;
InThreading(p->rchild);
}
}
//
// 中序線索化二叉樹
Status InOrderThreading(LinkBinThrTree *threadTree, LinkBinThrTree tree)
{
if (!((*threadTree) = (LinkBinThrTree)malloc(sizeof(BinThrTree))))
{
exit(OVERFLOW);
}
(*threadTree)->leftTag = Link;
(*threadTree)->rightTag = Thread;
(*threadTree)->rchild = (*threadTree);
if (!tree) // 若樹空，左指針回指
{
(*threadTree)->lchild = (*threadTree);
}
else
{
(*threadTree)->lchild = tree;
pre = (*threadTree);
InThreading(tree);
pre->rchild = tree;
pre->rightTag = Thread;
tree->rchild = pre;
}
return OK;
}
//
// 測試線索二叉樹的算法的使用
#include <stdio.h>
#include <stdlib.h>
#include "BinaryThreadTree.h"
int main()
{
BinThrTree *tree = NULL, *head = NULL;
freopen("test.txt", "r", stdin);
if (CreateBinaryThreadTree(&tree))
{
printf("二叉樹創建成功！\n");
}
if (InOrderThreading(&head, tree))
{
printf("\n中序線索化二叉樹完畢！\n");
}
printf("\n中序遍曆線索化二叉樹：\n");
InOrderTraverse(tree);
fclose(stdin);
putchar(10);
return 0;
}
最後更新：2017-04-03 18:51:56