UC知道求二叉树上结点的路径（二叉树）
来源：百度知道 编辑：UC知道 时间：2024/05/14 19:45:54
实现功能：在采用链式存储结构存储的二叉树上，以bt指向根结点，p指向任一给定的结点，编程实现求出从根结点bt到给定结点p之间的路径。
实验机时：6
设计思路：
数据结构：
typedef struct node{
char data; //数据域
struct node *lchild , *rchild; //左右孩子指针
}BinTNode; //树中结点类型
typedef BinTNode *BinTree;
主要实现函数：
二叉树的建立
求指定结点路径
二叉树的前、中、后序非递归遍历算法
查找函数
主控函数及运行环境设置
实验机时：6
设计思路：
数据结构：
typedef struct node{
char data; //数据域
struct node *lchild , *rchild; //左右孩子指针
}BinTNode; //树中结点类型
typedef BinTNode *BinTree;
主要实现函数：
二叉树的建立
求指定结点路径
二叉树的前、中、后序非递归遍历算法
查找函数
主控函数及运行环境设置
这实际上是找p的所有祖先，给你一个找祖先的算法，其余自己弄
我程序里的bitree＝BinTree，bitnode＝BinTNode
void ancestor(bitree root,char x) //找x的祖先
{
typedef struct
{
bitree t;
int tag;//tag=0表示访问左子树，tag=1表示访问右子树
}stack;
stack s[100];int top=0;
while(root||top)
{
while(root&&root->data!=x)
{
s[++top].t=root;s[top].tag=0;root=root->lchild;//访问左子树
}
if(root&&root->data==x)
{
printf("%c的祖先节点为:\n",x);
for(int i=1;i<=top;i++)printf("%c\n",s[i].t->data);return;
}
while(top&&s[top].tag==1)top--;//退栈
if(top)
{
s[top].tag=1;root=s[top].t->rchild;//访问右子树
}
}
}