首页 / 算法 / DS树--二叉树之最大路径
DS树--二叉树之最大路径
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了DS树--二叉树之最大路径,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1820字,纯文字阅读大概需要3分钟。
内容图文
![DS树--二叉树之最大路径](/upload/InfoBanner/zyjiaocheng/1057/3d7ee0e22fd04224ad9590e23ed68797.jpg)
题目描述
给定一颗二叉树的逻辑结构(先序遍历的结果,空树用字符‘0’表示,例如AB0C00D00),建立该二叉树的二叉链式存储结构
二叉树的每个结点都有一个权值,从根结点到每个叶子结点将形成一条路径,每条路径的权值等于路径上所有结点的权值和。编程求出二叉树的最大路径权值。如下图所示,共有4个叶子即有4条路径,
路径1权值=5 + 4 + 11 + 7 = 27 路径2权值=5 + 4 + 11 + 2 = 22
路径3权值=5 + 8 + 13 = 26 路径4权值=5 + 8 + 4 + 1 = 18
可计算出最大路径权值是27。
该树输入的先序遍历结果为ABCD00E000FG00H0I00,各结点权值为:
A-5,B-4,C-11,D-7,E-2,F-8,G-13,H-4,I-1
输入
第一行输入一个整数t,表示有t个测试数据
第二行输入一棵二叉树的先序遍历,每个结点用字母表示
第三行先输入n表示二叉树的结点数量,然后输入每个结点的权值,权值顺序与前面结点输入顺序对应
以此类推输入下一棵二叉树
输出
每行输出每棵二叉树的最大路径权值,如果最大路径权值有重复,只输出1个
样例输入
样例输出
提示
#include<iostream> #include<string> usingnamespace std; class BitreeNode { public: char data; int weight; BitreeNode *left; BitreeNode *right; BitreeNode() { weight=0; left=right=NULL; } }; class Bitree { public: BitreeNode *Root; int pos,index;///pos控制字符,index控制权值int maxpath; string strtree; Bitree(int *w,string str) { pos=index=0; maxpath=0; strtree=str; Root=CreateBitree(w,0); }; BitreeNode *CreateBitree(int *w,int fatherweight) { char ch=strtree[pos]; pos++; if(ch==‘0‘) { return NULL; } else { BitreeNode *T=new BitreeNode(); T->data=ch; T->weight=w[index]+fatherweight; index++; T->left=CreateBitree(w,T->weight); T->right=CreateBitree(w,T->weight); return T; } } void preorder(BitreeNode *T) { if(T!=NULL) { if(T->left==NULL&&T->right==NULL) { if(T->weight>maxpath) maxpath=T->weight; } preorder(T->left); preorder(T->right); } return; } }; int main() { int T; cin>>T; while(T--) { string str; cin>>str; int n; cin>>n; int *a=newint[n]; for(int i=0;i<n;i++) cin>>a[i]; Bitree Tree(a,str); Tree.preorder(Tree.Root); cout<<Tree.maxpath<<endl; delete []a; } return0; }
原文:https://www.cnblogs.com/SZU-DS-wys/p/12180828.html
内容总结
以上是互联网集市为您收集整理的DS树--二叉树之最大路径全部内容,希望文章能够帮你解决DS树--二叉树之最大路径所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。