[数据结构与算法]查询给定二叉树节点的双亲节点

利用二叉树的层序遍历，借助队列。

#define INITSIZE 20

//二叉树
typedef int ElemType;
typedef struct Node
{
    struct Node *lchild;
    ElemType data;
    struct Node *rchild; 
    /* data */
}Node,Tree;

//队列，存储指向二叉树节点的指针
typedef struct{
    int front,rear;
	Node *nodes[INITSIZE];
    int length;
    int size;
}Queue;

void init_queue(Queue *q){
    q->front = 0;
	q->rear = -1;
    q->length = 0;
    q->size = INITSIZE;
}


void push(Queue *q, Node *e){

    //这个判断条件
    if(q->length >= q->size){
    //length >= size
       printf("满了\n");
    }
    q->nodes[++q->rear] = e;
    q->length++;
}

Node* pop(Queue *q){
    if(q->front == q->rear+1){
        printf("THE QUEUE IS EMPTY\n");
        return NULL;
    }
	Node *e = q->nodes[q->front];
    q->front++;
    q->length--;
	return e;
}

int empty(Queue *q){
	if(q->front == q->rear+1)
		return 1;
	return 0;
}

ElemType parent(Tree *t, Queue *q,ElemType e){
	
	push(q,t);
	while(!empty(q)){
		Node *pars = pop(q);
		if(pars->lchild && pars->lchild->data == e)
			return pars->data;
		else if(pars->lchild)
			push(q,pars->lchild);
		if(pars->rchild && pars->rchild->data == e)
			return pars->data;
		else if(pars->rchild)
			push(q,pars->rchild);

	}
	
}

int main(){
    Tree *t;
	Queue q;
	init_queue(&q);
    t = create_tree(t);
    printf("查找谁的双亲节点？：");
	ElemType e;
	scanf("%d",&e);
	printf("%2d的双亲节点是:%2d",e,parent(t,&q,e));
	printf("\n");
    return 0;
}