二叉链表存储的时候可以很方便地找到某个结点的左右孩子,但是一般情况下,无法直接找到该结点在某种遍历序列中的前驱和后继结点。
线索二叉树(Threaded Binary Tree):
线索化:对二叉树按某种遍历次序使其变为线索二叉树的过程
增加了头结点的二叉树:
代码实现:
#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
typedef int Status;
typedef char TElemType;
using namespace std;
//线索二叉树的结点类型
typedef struct BiTreNode {
TElemType data;//数据域
int ltag, rtag;
BiTreNode* lchild,*rchild;
}BiTreNode, * BiTreTree;
typedef BiTreTree SElemType;//定义顺序栈的元素为BiTNode的结点
typedef struct {
SElemType* base;
SElemType* top;
int stacksize;
}SqStack;
//栈的初始化
Status Init(SqStack& S) {
//分配空间
//S.base = (SElemType*)malloc(sizeof(SElemType)*MAXSIZE);
S.base = new SElemType[MAXSIZE];
if (!S.base) return ERROR;
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
//判断栈是否为空
Status StackEmpty(SqStack S) {
if (S.top==S.base)
{
return TRUE;
}
return FALSE;
}
//入栈
Status StackPush(SqStack& S, SElemType e) {
if (S.top - S.base == S.stacksize) {
//栈满了
return ERROR;
}
*S.top = e;//*代表取S.top指针的空间进行运算
S.top++;//即*S.top++=e;
return OK;
}
//出栈
Status StackPop(SqStack& S, SElemType &e) {
if (S.top == S.base) {
return ERROR;
}
S.top--;
e = *S.top;//相当于e=*--S.top
return OK;
}
//使用先序遍历创建二叉树
void createTreTree(BiTreTree& T) {
T = new BiTreNode;
char ch;
cin >> ch;
if (ch == '#') {
T = NULL;
}
else {
T->data = ch;
T->ltag = 0;
T->rtag = 0;
createTreTree(T->lchild);
createTreTree(T->rchild);
}
}
//根据中序遍历的顺序创建线索二叉树
BiTreTree createInTraverseTreTree(BiTreTree& T) {
BiTreNode* p,*pre;
BiTreNode* head=new BiTreNode;
pre = NULL;
//head的左孩子指向是根结点
head->ltag = 0;
head->lchild = T;
head->data = '#';
p = T;
SqStack S;
Init(S);
bool flag = false;
while (p||!StackEmpty(S))
{
if (p)
{
StackPush(S, p);
p = p->lchild;
if (!p)
{
flag = true;//flag为true说明等一下d出的是一个左子树为空的结点
}
}
else
{
BiTreNode* q = new BiTreNode;
StackPop(S, q);
//左子树为空的情况
if (flag)//即说明d出的是左子树为空的结点
{
if (pre == NULL) {//说明该结点没有中序遍历的结点,即这是中序遍历中的第一个结点
q->ltag = 1;
q->lchild = head;
}
else
{
q->ltag = 1;
q->lchild = pre;
}
flag = false;//修改flag值
}
pre = q;
p = q->rchild;
if (!p)//右子树为空
{
if (StackEmpty(S))//即这是中序遍历中的最后一个结点
{
head->rtag = 1;
head->rchild = q;
//头结点的后序结点指向中序遍历中的最后一个结点
q->rtag = 1;
q->rchild = head;
//中序遍历中的最后一个结点指向head头结点
}
else {//p为空说明q结点的右子树为空,等一下该d出结点输出了,等一下d出的就是现在q结点在中序遍历中的后序结点
q->rtag = 1;
BiTreNode* temp=new BiTreNode;
StackPop(S, temp);
q->rchild = temp;
StackPush(S, temp);//记得放回栈中
}
}
}
}
return head;//返回新创建的左子树指向根结点的头结点
}
//先序遍历输出tag域不为空的值即输出该结点的中序遍历的前序结点/后序结点,而不是该结点的孩子结点
void PreTraverseTreTree(BiTreTree T) {
if (T)
{
if (T->ltag != 0)//
{
printf("本结点为:%c 中序遍历前序结点为:%c \n", T->data, T->lchild->data);
}
if (T->rtag != 0)
{
printf("本结点为:%c 中序遍历后序结点为:%c \n", T->data, T->rchild->data);
}
if (T->ltag == 0)
{
PreTraverseTreTree(T->lchild);
}
if (T->rtag == 0)
{
PreTraverseTreTree(T->rchild);
}
}
}
int main() {
BiTreTree T;
createTreTree(T);
BiTreTree newT=createInTraverseTreTree(T);
PreTraverseTreTree(newT);
return 0;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)