二叉树结点路径求解

来源：百度知道 编辑：UC知道 时间：2024/06/02 07:07:53
问题描述：在采用二叉链表的二叉树上，bt指向根结点，p指向任意给定的结点，编程实现求出从根结点到给定结点的路径。
要求：要求采用非递归遍历算法。

#include <stdio.h>/* 头文件 */
#include <stdlib.h>
#include <malloc.h>
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild,*parent;
}
BiTNode,*BiTree;/* 定义结点类型 */
typedef struct QNode
{
BiTree data;
struct QNode *next;
} /* 定义队列的节点类型 */
QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}
LinkQueue;/* 队列 */
void InitQueue(LinkQueue *Q)/* 创建队列 */
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
Q->front->next=NULL;
}
void EnQueue(LinkQueue *Q,BiTree e)/* 将元素入队 */
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));/* 为结点开辟空间 */
p->data=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
}
BiTree DeQueue(LinkQueue *Q)/* 将元素出列并返回元素的值。 */
{
BiTree e;QueuePtr p;
p=Q->f