求二叉树上结点的路径（二叉树）

数据结构课程设计 求二叉树上结点的路径~

#include
#include
#define MAXSIZE 20
#define exit 0
typedef struct btnode
{
char cdata;
struct btnode *lchild,*rchild;
}BTNode;
BTNode *Create_BiTree()/*二叉树的建立*/
{
/*用辅助数组建立二叉树*/
int i,j;
char ch;
BTNode *s,*t,*p[MAXSIZE];
printf("=========数据结构=======RANBO========
");
printf("=========二叉树基本操作==============
");
printf("输入顶点编号及信息，输入0和#结束:i,ch
");
scanf("%d,%c",&i,&ch);
while (i!=0 &&ch!='#')/*建立二叉树的存储结构*/
{
s=(BTNode *)malloc(sizeof(BTNode));
s->cdata=ch;
s->lchild=s->rchild=NULL;
p[i]=s;
if (i==1) t=s;/*判断输入结点是根结点、左孩子还是右孩子*/
else
{
j=i/2;
if (i%2==0) p[j]->lchild=s;
else p[j]->rchild=s;
}
printf("输入顶点编号及信息，输入0和#结束:i,ch
");
scanf("%d,%c",&i,&ch);
}
return t;
}/* Create_BiTree1*/
void Preorder(BTNode *bt)
{
/*前序递归遍历*/
if (bt)
{
printf("%c",bt->cdata);
Preorder(bt->lchild);
Preorder(bt->rchild);
}
}/* Preorder*/
void Inorder(BTNode *bt)
{
/*中序递归遍历*/
if (bt)
{
Inorder(bt->lchild);
printf("%c",bt->cdata);
Inorder(bt->rchild);
}
}/* Inorder*/
void Postorder(BTNode *bt)
{
/*后序递归遍历*/
if (bt)
{
Postorder(bt->lchild);
Postorder(bt->rchild);
printf("%c",bt->cdata);
}
}/* Postorder*/
void LevelOrder(BTNode *bt) /*层次遍历二叉树bt*/
{
BTNode* queue[MAXSIZE];
int front,rear;
if (bt==NULL) return;
front=0; /*非循环队列*/
rear=0;
queue[rear++]=bt;
while (front!=rear)
{
printf("%c",queue[front]->cdata); /*访问队首结点的数据域*/
if (queue[front]->lchild!=NULL) /*将队首结点的左孩子指针入队列*/
{
queue[rear]=queue[front]->lchild;
rear++;
}
if (queue[front]->rchild!=NULL) /*将队首结点的右孩子指针入队列*/
{
queue[rear]=queue[front]->rchild;
rear++;
}
front++;
} /* while */
}/* LevelOrder*/
int main()
{
int i,j=1;
BTNode *t;
t=Create_BiTree();
while (j)
{
printf("
"); /*功能菜单*/
printf("请选择操作:
");
printf("1: 二叉树的前序遍历
");
printf("2: 二叉树的中序遍历
");
printf("3: 二叉树的后序遍历
");
printf("4: 二叉树的层次遍历
");
printf("0: 退出程序
");
scanf("%d",&j);
switch (j)
{
case 0:
printf(" 程序退出!
");
exit(0);
case 1:
printf("前序遍历结果:
");
Preorder(t);
break;
case 2:
printf("中序遍历结果:
");
Inorder(t);
break;
case 3:
printf("后序遍历结果:
");
Postorder(t);
break;
case 4:
printf("按层遍历结果:
");
LevelOrder(t);
break;
default :
printf("
输入无效，请重新选择操作!
" );
break;
}
}
}

#include /* 头文件 */
#include
#include
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->front->next;
e=p->data;
Q->front->next=p->next;
if(Q->rear==p)
Q->rear=Q->front;
free(p);/* 释放节点 */
return (e);

}
int QueueEmpty(LinkQueue *Q)/* 判断队列是否为空 */
{
if(Q->front==Q->rear )
return 1;
else
return 0;
}
BiTree CreateBiTree()/* 创建树 */
{
char p;
BiTree T;
scanf("%c",&p);
if(p==' ')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));/* 为结点开辟空间 */
T->parent=NULL;
T->data=p;
T->lchild=CreateBiTree();
T->rchild=CreateBiTree();
}
return (T);
}
BiTree Road(BiTree T,char a)
{
LinkQueue Q;
BiTree p;
InitQueue(&Q);
EnQueue(&Q,T);
while(!QueueEmpty(&Q))
{
p = DeQueue(&Q);
if(p->data==a)
return(p);
if(p->lchild!=NULL)
{
p->lchild->parent=(BiTNode *)malloc(sizeof(BiTNode));
*(p->lchild->parent)=*p;
EnQueue(&Q,p->lchild);
}
if(p->rchild!=NULL)
{
p->rchild->parent=(BiTNode *)malloc(sizeof(BiTNode));
*(p->rchild->parent)=*p;
EnQueue(&Q,p->rchild);
}
}
return(NULL);
}

void main()/* 主函数 */
{
BiTree Ta,p,L;char a;
printf("请创建树：
");
Ta=CreateBiTree();
getchar();
printf("输入查找的元素");
scanf("%c",&a);
p=Road(Ta,a);
while(p)
{
printf("%c",p->data);
L=p;
p=p->parent;
free(L);
}
}

这实际上是找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;//访问右子树
}
}
}

本题使用树的递归遍历思想
就很容易做了
假设结点
struct
node
{
int
data;
node
*lchild,
*rchild;
};
//
返回值为路径长度
如果查找失败
则返回负值
//
具体找到后的路径存在path中
path中存的只是指向结点的指针
int
findpath(node
*root,
node
*p,
node
*path[],
int
count
=
0)
{
path[count]
=
root;
//
如果要存结点中的值
在这里改
还有上面的参数的类型
if(root
==
p)
{
return
++count;
}
if(root)
{
int
ret
=
findpath(root->lchild,
p,
path,
count+1);
if(ret
>
0)
return
ret;
//
如果已经在左子树中找到
就不用再在右子数中找了
return
findpath(root->rchild,
p,
path,
count+1);
}
return
-1;
//
没找到
返回负值
}

线索二叉树：二叉树的结点上加上线索的二叉树

---

延平区19733569798： 求二叉树上结点的路径 - ？
滕爸丹珍： 本题使用树的递归遍历思想 就很容易做了 假设结点 struct Node { int data; Node *lchild, *rchild; }; // 返回值为路径长度 如果查找失败 则返回负值 // 具体找到后的路径存在path中 path中存的只是指向结点的指针 int FindPath(Node *root, Node *p, ...

延平区19733569798： 二叉树结点路径求解 - ？
滕爸丹珍： #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;} /* ...

延平区19733569798： 求二叉树任意两结点的最短路径 - ？
滕爸丹珍： 最好使用双向链表 如a与b相连则a连b b连a 然后在树上做bfs 复杂度o(n) 为什么树的最短路径做bfs而图的最短路径要spfa或dijkstra呢 因为树中没有回路 任意两点的路径仅有一条 故结点搜到一次即可 而图中有回路 意味着两点间可能有多条路径 有边少权大和变多权小的可能 一个点要多次进队 ps 建立在边权不为负的情况下

延平区19733569798： 中序遍历地求解二叉树中从根到叶子结点的所有路径. - ？
滕爸丹珍： 为什么一定要用中序?? 我觉得先序的效率更高些,当然,如果一定用中序的话,换下下面递归函数中的相关语句的顺序即可.思路:当前节点是么?--〉不是:判断左右子树;若当前节点或左右子树是:将当前节点插入链表.(只写了功能实...

延平区19733569798： 如何找出二叉树两结点之间的路径,并嫠薪岬 - ？
滕爸丹珍： 使用中序遍历即可.bool getPath(TreeNode *root, TreeNode *one, TreeNode *two) { int getNodes = 0; if (root == NULL) return false; if (getPath(root->left, one, two)) {//当前节点入队 if (getPath(root->right, one, two)) //如果两个节点刚好位于当前节...

延平区19733569798： 求二叉树的指定节点路径. - ？
滕爸丹珍： 这实际上是找p的所有祖先,给你一个找祖先的算法,其余自己弄 我程序里的bitree=BinTree,bitnode=BinTNode void ancestor(bitree root,char x) //找x的祖先 { typedef struct { bitree t; int tag;//tag=0表示访问左子树,tag=1表示访问右子树 }stack; ...

延平区19733569798： 二叉树求指定结点到根结点的路径怎样用C++语言描述....? - ？
滕爸丹珍： bool printPath(TreeNode *root, int data) {if (root == NULL)return false; if (root->data == data || printPath(root->left) || printPath(root->right)){cout<<root->data; //路径上的结点标识打印出来return true;} return false; }

延平区19733569798： 求二叉树中从根结点到叶子节点的路径 - ？
滕爸丹珍： #include<stdio.h> #include<malloc.h> #define MaxSize 100 typedef char ElemType; typedef struct node{ElemType data; //数据元素struct node *lchild; //指向左孩子struct node *rchild; //指向右孩子 }BTNode; void CreateBTNode(BTNode *&b,...

延平区19733569798： C++如何求二叉树中一个结点到根节点的路径? - ？
滕爸丹珍： if((R->data==x) || (GetPath(char x,R->lch)==true) ||(GetPath(char x,R->rch)==true)) 有语法错误,由于GetPath(char x,R->lch)的第一个参数处的char关键字造成,修改为:if((R->data==x) || (GetPath(x,R->lch)==true) ||(GetPath(x,R->rch)==true))

延平区19733569798： 怎样得到二叉树根节点到叶子节点的最远路径 算法 - ？
滕爸丹珍： 用后序遍历或层次遍历.到叶子节点,判断当前的深度与当前最大深度值得大小,更新当前的深度值.