[数据结构与算法]线索二叉树--中序遍历算法

//还有求任意结点的的后继结点与前驱结点的函数以及遍历的函数，明天再更新
#include<stdio.h>
#include<stdlib.h>
typedef struct btnode {
	char element;
	int RTag ; 
	int LTag ;
	struct btnode* Lchild, * Rchild;
}BTNode;
typedef struct btree {
	struct btnode* Root;
}BTree;
//创建新节点
BTNode* NewNode() {
	BTNode* p = (BTNode*)malloc(sizeof(BTNode));
	p->LTag = p->RTag = 0;
	return p;
}
//创建二叉树
void CreateBT(BTree* bt) {
	bt->Root = NULL;
}
//将两个二叉树组建为一个二叉树
void MakeBT(BTree* bt, char x, BTree* lt, BTree* rt) {
	BTNode* p = NewNode();
	p->element = x;
	p->Rchild = rt->Root;
	p->Lchild = lt->Root;
	lt->Root = rt->Root = NULL;
	bt->Root = p;
}


void Visit(BTNode* p) {
	printf("%c ", p->element);
}
//构造中序线索二叉树  为被调函数
void MakeThread(BTNode * t, BTNode** ppr) {
	if (t) {
		MakeThread(t->Lchild, ppr);
		if (*ppr) {
			if (!(*ppr)->Rchild) {
				(*ppr)->RTag = 1;
				(*ppr)->Rchild = t;
			}
			else {
				(*ppr)->RTag = 0;
			}
		}
		if (!t->Lchild) {
			t->LTag = 1;
			t->Lchild = *ppr;
		}
		else {
			t->LTag = 0;
		}
		*ppr = t;
		MakeThread(t->Rchild, ppr);
	}
}
//调用 构造中序线索二叉树 的函数，为调用函数
void BuildThreadBT(BTree bt) {
	BTNode* pr = NULL;
	if (bt.Root) {
		pr = NULL;
		MakeThread(bt.Root, &pr);
		pr->RTag = 1;
	}
}
//返回中序线索二叉树的第一个结点
BTNode* GetFirstNode(BTree bt) {
	BTNode* p = bt.Root;
	if (p) {
		while (p->Lchild) {
			p = p->Lchild;
		}
	}
	return p;
}
//返回任一节点的后继结点
BTNode* NextNode(BTNode* p) {
	BTNode* q = p->Rchild;
	if (!p->RTag) {
		while (!q->LTag) {
			q = q->Lchild;
		}
	}
	return q;
}
void main() {
	BTree* a, * x, * y, * z, * s, * t;
	BTNode* first, * next;
	a = (BTree*)malloc(sizeof(BTree));
	x = (BTree*)malloc(sizeof(BTree));
	y = (BTree*)malloc(sizeof(BTree));
	z = (BTree*)malloc(sizeof(BTree));
	s = (BTree*)malloc(sizeof(BTree));
	t = (BTree*)malloc(sizeof(BTree));
	CreateBT(a);
	CreateBT(x);
	CreateBT(y);
	CreateBT(z);
	CreateBT(s);
	CreateBT(t);
	MakeBT(s, 'E', a, a);
	MakeBT(t, 'F', a, a);
	MakeBT(y, 'C', s, t);
	MakeBT(t, 'D', a, a);
	MakeBT(x, 'B', t, a);
	MakeBT(z, 'A', x, y);

	BuildThreadBT(*z);
	first = GetFirstNode(*z);
	printf("%c\n", first->element);
	next = NextNode(z->Root->Rchild);
	printf("%c\n", next->element);
	printf("hhhhhhhhhhh\n");
}
}