求二叉树路径长度（C语言）
发布时间
阅读量：
阅读量
通过扩展先序遍历算法构建二叉链表结构，并对生成的树形数据进行分析处理；进而统计从根节点到各个叶子节点路径长度的总和。
此二叉树的扩展先序遍历序列是：A B D . G . . . C E . . F . .（可直接复制使用）
根到叶子结点的路径总长应为：G（3）+E（2）+F（2）=7
使用类似二叉树求最大深度的方式，不同的是每次递归返回时，
如果结点左右子树都不存在，或者只有一棵子树则return
1+左子树路径长度+右子树路径长度
如果结点同时有左子和右子树，则return
2+左子树路径长度+右子树路径长度
因为有两个子树的结点返回的时候要把返回路径算两遍，所以是+2
ps：该方法会返回一个+2，在输出时需要减去2（或许有更优的方法可以避免单独扣除这个2？目前作者尚未想到更好的解决方案）
ps:求深度返回的是1+(left>right?left:right)
#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
char data;
struct Node *lchild,*rchild;
}BiNode,*BiTree;
void createT(BiTree *bt){
char c;
c=getchar();
getchar();//getcahr用来吸收空格和回车
if(c=='.') *bt=NULL;//因为二级指针传参，所以想表示bt这个指针的值就要用*bt
else{
*bt=(BiTree)malloc(sizeof(BiNode));
(*bt)->data=c;
createT(&((*bt)->lchild));
createT(&((*bt)->rchild));
}
}
int cal(BiTree bt){
int left=0,right=0;
if(bt==NULL) return 0;
else{
left=cal(bt->lchild);
right=cal(bt->rchild);
if(bt->lchild && bt->rchild) return 2+left+right;//如果左右子树都存在就路径sum+2
else
return 1+left+right;//如果只有只有一个子树，或者是叶子结点，路径sum+1
}
}
int main(){
BiTree bt;//bt是一个结构体指针
createT(&bt);//扩展先序序列建立法 元素之间用空格或者回车隔开
int count=cal(bt);
printf("%d",count-2);//去除根节点返回时加的2
return 0;
}运行结果截图如下：
全部评论 (0)
还没有任何评论哟~