#include
#include
#define MAXSIZE 100
// 树结构定义
typedef char datatype ;
typedef struct node {
datatype data;
struct node *lchild, *rchild;
} treenode;
typedef treenode *BiTree;
// 栈
typedef struct stack {
BiTree data[MAXSIZE];
int tag[MAXSIZE];
int top;
} seqstack;
// 出栈操作
BiTree pop (seqstack *s)
{
// 若栈顶不为空
if (s->top != 0) {
// 减一个
s->top--;
// 返回减掉的data
return s->data[s->top];
} else return NULL;
// 否则返回空
}
// 入栈操作
void push (BiTree t, seqstack *s)
{
// 把t放上栈顶
s->data[s->top] = t;
// 栈顶递增
s->top++;
}
// 生成树
void creatree (BiTree &T)
{
char ch;
// 读取字符
ch = getchar();
// 输入#结束输入
if (ch == '#') T = NULL;
// 录入
else {
// 分配
T = (BiTree) malloc (sizeof (treenode));
// 放入data
T->data = ch;
// 继续二叉
creatree (T->lchild);
creatree (T->rchild);
}
}
// 前序遍历
void preorder (BiTree T)
{
if (T) {
// 前序、中序的区别自个弄清概念
printf ("%c", T->data);
preorder (T->lchild);
preorder (T->rchild);
}
}
// 中序遍历
void inorder (BiTree T)
{
if (T) {
// 顺藤摸瓜
inorder (T->lchild);
printf ("%c", T->data);
inorder (T->rchild);
}
}
// 查找树
int find (BiTree T, BiTree x, seqstack *s)
{
// 栈顶复0
s->top = 0;
// 若T不为空
while (T || s->top) {
// 能进来当然不空
if (T) {
s->tag[s->top] = 0;
push (T, s);
T = T->lchild;
// 这函数似乎乱七八糟的,这程序是谁写的,你读别人的吗,这是个正常的程序吗
} else {
if (s->top && s->tag[s->top-1]) {
T = pop (s);
if (T && T->data == x->data)
return s->top;
T = NULL;
} else {
T = s->data[s->top-1];
s->tag[s->top-1] = 1;
T = T->rchild;
}
}
}
return -1;
}
// 查找共同祖先
void grandpar (seqstack *sq, seqstack *sp)
{
// 先把栈顶砍平
while (sq->top != sp->top) {
if ( (sq->top - 1) > (sp->top - 1)) {
pop (sq);
} else {
pop (sp);
}
}
// 平了开始比较对应元素
while (sp->top) {
if (sq->data[sq->top-1] == sp->data[sp->top-1]) {
// 若找到相同的就打印
printf ("%4c", sq->data[sq->top-1]->data);
}
pop (sq);
pop (sp);
}
}
int main()
{
BiTree root, p, q;
seqstack *sp, *sq;
int x, y;
root = (BiTree) malloc (sizeof (treenode));
p = (BiTree) malloc (sizeof (treenode));
q = (BiTree) malloc (sizeof (treenode));
sq = (seqstack *) malloc (sizeof (seqstack));
sp = (seqstack *) malloc (sizeof (seqstack));
printf ("请用前序遍历创建一棵二叉树:");
creatree (root);
printf ("该二叉树为");
preorder (root);
printf ("\n请输入要查找共同祖先的两个结点:");
getchar();
scanf ("%c%c", &p->data, &q->data);
x = find (root, p, sp);
y = find (root, q, sq);
printf ("这两个结点的共同祖先为");
grandpar (sq, sp);
}
我们Q上讨论