二叉木の2つの結点の最近の共通の祖先の結点を求めます
二叉木の2つの結点の最近の共通の祖先の結点を求めます
テーマの要求と構想の分析タイトル要件:二叉木では*rootがルートノードであることが知られており、*pと*qが二叉木の2つのノードであり、それらの最も近い共通の祖先を求めるアルゴリズムを作成してみます.-『データ構造練習問題集(C言語版)』 考え方: 明らかにこの問題では,再帰遍歴は適用されない.同時に先中後の3つの順序で、先序遍歴が適切である. は、最後に祖先ノードを検索するためにスタックの特性を利用して、ターゲットノードにアクセスするパスを格納する. *pと*qのパスが見つかった後、ルートノードがスタックの底にあり、ターゲットノードがスタックの頂上にあることがわかります.これは、2つのパス上の共通の祖先ノードを比較するのに不利です.したがって、2つのターゲットノードのパススタックを逆にして、スタックトップ要素をルートノードにすると、スタックを出るときに2つのスタックトップ要素が指すノードを比較できます.最初の異なるノードが現れるまで、2つのターゲットノードに最も近い共通の祖先ノードであるスタック要素を取ります.
アルゴリズム実装の2種類のデータ型の構造体定義 で使用するスタックの基本動作関数 で使用するツリーの基本動作関数 は、宛先ノードにアクセスするパス を格納するためにスタックを利用する.は*p、*qに対してそれぞれ第4ステップの関数を呼び出し、得られた2つのパススタックを逆置きし、逆置き後のスタックからスタックトップ要素を出て同時に比較し、共通祖先ノード を得る.
テーマの要求と構想の分析
アルゴリズム実装
/*------- ------*/
#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;
/---------------------------/
/*------- -------*/
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
/*----- -----*//*------ ------*/
//
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;
}
/*---- ----*/
/* */
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;
}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;
}