1.两种数据类型的结构体定义
/*-------二叉树的二叉链结点结构定义------*/
#define TElemType char
typedef struct BiTNode{ // 结点结构
TElemType data; // 结点数据
struct BiTNode *lchild, *rchild; // 左右 孩子指针
} BiTNode, *BiTree;
/------栈的数据结构预定义------/
define MAXSIZE 100 // 存储空间初始分配量
typedef struct{
BiTree data[MAXSIZE];
int top; //用于栈顶指针
}SqStack;
/---------------------------/
2.用到的栈的基本操作函数
/*-------栈的基本操作函数-------*/
Status Push(SqStack *S, BiTree e){
//插入元素e 为新的栈顶元素
if (S->top = MAXSIZE - 1)return ERROR;
S->top++;
S->data[S->top] = e; //将新插入元素赋值给栈顶空间
return OK;
}
BiTree Pop(SqStack *S){
//若栈不空,则删除S的栈顶元素,用e返回其值,变返回oK;否则返回ERROR
if (S->top == -1)return ERROR;
BiTree e = S->data[S->top]; //将要删除的栈顶元素赋给e
S->top--; //栈顶指针减一
return e;
} //pop
/*-----栈的基本操作函数结束-----*/
3.用到的树的基本操作函数
*------树的基本操作的函数------*/
//按照二叉树的定义初始化一个空树
Status InitBiTree(BiTree *bt){
*bt = (BiTree)malloc(sizeof(BiTNode));
if (!bt)return OVERFLOW;
*bt = NULL;
return OK;
}
//构造二叉链表表示的二叉树T
//按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树
Status CreateBiTree(BiTree *T){
TElemType ch;
printf_s("请输入数据:");
scanf_s("%c", &ch);
getchar(); //getchar()用于处理回车占字符的问题
if (ch == '#')
*T = NULL;
else{
*T = (BiTree)malloc(sizeof(BiTNode));
if (!T)return OVERFLOW; // 若内存分配失败,则返回OVERFLOW
(*T)->data = ch; // 生成根结点
CreateBiTree(&((*T)->lchild)); //构建左子树
CreateBiTree(&((*T)->rchild)); //构建右子树
}
return OK;
}
/*----树的基本操作的函数结束----*/
4.利用栈来存储访问目标结点的路径
/*求距两个子结点最近的共同祖先结点*/
Status FindPath(BiTree root, BiTree target, SqStack *path){
SqStack* s;
s = (SqStack *)malloc(sizeof(SqStack));
BiTree node = root;
while (1){
Push(path, node); //将当前结点入栈
if (node == target)return OK; //若当前结点即为目标结点,则可直接结束
//若左孩子存在,则再看右孩子。若右孩子也存在,将右孩子存入栈s;若右孩子不存在,则直接访问下一个左孩子。
//若左孩子不存在,则访问右孩子。若左右孩子都不存在,则去查看栈s中的栈顶元素所指结点。
//重复操作,直到找到目标结点。这时栈path中存储的元素为访问到目标结点的所有元素。
if (node->lchild){
if (node->rchild){
Push(s, node->rchild);
}
node = node->lchild;
}else if (node->rchild){
node = node->rchild;
}else if (s){
while (path->data[path->top]->rchild != s->data[s->top]){
Pop(path);
}
node = s->data[s->top];
Pop(s);
}else{
break;
}
}
return OK;
}
5.对* p、* q分别调用第4步中的函数,将得到的两个路径栈逆置,在逆置后的栈中出栈顶元素同时进行比较,得到公共祖先结点
Status CommentParent(BiTree* parent, BiTree root, BiTree p, BiTree q){
SqStack *path_p, *path_q;
path_p = (SqStack *)malloc(sizeof(SqStack));
path_q = (SqStack *)malloc(sizeof(SqStack));
FindPath(root, p, path_p);
FindPath(root, q, path_q);
SqStack *reverse_p, *reverse_q;
reverse_p = (SqStack *)malloc(sizeof(SqStack));
reverse_q = (SqStack *)malloc(sizeof(SqStack));
while (path_p){
Push(reverse_p, Pop(path_p));
}
while (path_q){
Push(reverse_q, Pop(path_q));
}
while (reverse_p->data[reverse_p->top] == reverse_q->data[reverse_q->top]){
*parent = reverse_p->data[reverse_p->top];
Pop(reverse_p);
Pop(reverse_q);
}
return OK;
}