求二叉树中从根结点到叶子节点的路径
发布网友
发布时间：2022-04-28 10:32
共2个回答
热心网友
时间：2022-04-15 05:38
b=NULL; //建立的二叉树初始时为空
ch=str[j];
while(ch!='\0'){ //str未扫描完时循环
switch(ch){
case '(':top++;St[top]=p;k=1;break; //为左结点
case ')':top--;break;
case ',':k=2;break; //为右结点
default :p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
if(b==NULL)
b=p; //p指向二叉树的根结点
else{
switch(k){
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
int main(){
BTNode *b;
ElemType path[MaxSize],longpath[MaxSize];
int i,longpathlen=0;
CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
printf("二叉树b:");DispBTNode(b);printf("\n\n");
printf("b的叶子结点：");DispLeaf(b);printf("\n\n");
printf("AllPath:\n");AllPath(b);printf("\n");
printf("AllPath1:\n");AllPath1(b,path,0);printf("\n");
LongPath(b,path,0,longpath,longpathlen);
printf("第一条最长路径长度：%d\n",longpathlen);
printf("第一条最长路径：");
for(i=longpathlen;i>=0;i--)
printf("%c ",longpath[i]);
printf("\n");
return 0;
}
扩展资料；
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。
参考资料来源：百度百科-二叉树
热心网友
时间：2022-04-15 06:56
#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,char *str){ //由str串创建二叉链
BTNode *St[MaxSize],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL; //建立的二叉树初始时为空
ch=str[j];
while(ch!='\0'){ //str未扫描完时循环
switch(ch){
case '(':top++;St[top]=p;k=1;break; //为左结点
case ')':top--;break;
case ',':k=2;break; //为右结点
default :p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
if(b==NULL)
b=p; //p指向二叉树的根结点
else{
switch(k){
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}
void DispBTNode(BTNode *b){ //以括号表示法输出二叉树
if(b!=NULL){
printf("%c",b->data);
if(b->lchild!=NULL || b->rchild!=NULL){
printf("(");
DispBTNode(b->lchild);
if(b->rchild!=NULL)
printf(",");
DispBTNode(b->rchild);
printf(")");
}
}
}
void AllPath(BTNode *b){ //采用非递归方法输出从叶子结点到根结点的路径
struct snode{
BTNode *node; //存放当前结点指针
int parent; //存放双亲结点在队列中的位置
}Qu[MaxSize]; //定义顺序队列
int front,rear,p; //定义队头和队尾指针
front=rear=-1; //置队列为空队列
rear++;
Qu[rear].node=b; //根结点指针进入队列
Qu[rear].parent=-1; //根结点没有双亲结点
while(front<rear){ //队列不为空
front++;
b=Qu[front].node; //队头出队列
if(b->lchild==NULL && b->rchild==NULL){ //*b为叶子结点
printf("%c到根结点路径：",b->data);
p=front;
while(Qu[p].parent!=-1){
printf("%c ",Qu[p].node->data);
p=Qu[p].parent;
}
printf("%c\n",Qu[p].node->data);
}
if(b->lchild!=NULL){ //左孩子入队列
rear++;
Qu[rear].node=b->lchild;
Qu[rear].parent=front;
}
if(b->rchild!=NULL){ //右孩子入队列
rear++;
Qu[rear].node=b->rchild;
Qu[rear].parent=front;
}
}
}
void AllPath1(BTNode *b,ElemType path[],int pathlen){ //采用递归方法输出从叶子结点到根结点的路径
int i;
if(b!=NULL){
if(b->lchild==NULL && b->rchild==NULL){ //*b为叶子结点
printf("%c到根结点路径：%c ",b->data,b->data);
for(i=pathlen-1;i>=0;i--)
printf("%c ",path[i]);
printf("\n");
}else{
path[pathlen]=b->data; //将当前结点放入路径中
pathlen++;
AllPath1(b->lchild,path,pathlen); //递归扫描左子树
AllPath1(b->rchild,path,pathlen); //递归扫描右子树
pathlen--;
}
}
}
void LongPath(BTNode *b,ElemType path[],int pathlen,ElemType longpath[],int &longpathlen){ //求最长路径
int i;
if(b==NULL){
if(pathlen>longpathlen){ //若当前路径更长，将路径保存在longpath中
for(i=pathlen-1;i>=0;i--)
longpath[i]=path[i];
longpathlen=pathlen;
}
}else{
path[pathlen]=b->data; //将当前结点放入路径中
pathlen++; //路径长度增1
LongPath(b->lchild,path,pathlen,longpath,longpathlen); //递归扫描左子树
LongPath(b->rchild,path,pathlen,longpath,longpathlen); //递归扫描右子树
pathlen--; //恢复环境
}
}
void DispLeaf(BTNode *b){ //输出叶子结点
if(b!=NULL){
if(b->lchild==NULL && b->rchild==NULL)
printf("%c ",b->data);
else{
DispLeaf(b->lchild);
DispLeaf(b->rchild);
}
}
}
int main(){
BTNode *b;
ElemType path[MaxSize],longpath[MaxSize];
int i,longpathlen=0;
CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
printf("二叉树b:");DispBTNode(b);printf("\n\n");
printf("b的叶子结点：");DispLeaf(b);printf("\n\n");
printf("AllPath:\n");AllPath(b);printf("\n");
printf("AllPath1:\n");AllPath1(b,path,0);printf("\n");
LongPath(b,path,0,longpath,longpathlen);
printf("第一条最长路径长度：%d\n",longpathlen);
printf("第一条最长路径：");
for(i=longpathlen;i>=0;i--)
printf("%c ",longpath[i]);
printf("\n");
return 0;
}
