首页 / 算法 / 二叉树中第一条最长的路径并输出此路径上各结点的值

二叉树中第一条最长的路径并输出此路径上各结点的值

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了二叉树中第一条最长的路径并输出此路径上各结点的值，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1615字，纯文字阅读大概需要3分钟。

内容图文

本文采用递归方法和配合STL模板的容器实现最长结点的遍历。

实现代码如下：

             1 #include<iostream>
 2 #include<vector>
 3 4usingnamespace std;
 5 6 typedef struct node
 7{
 8char data;//结点数据 9struct node *lchild,*rchild;//二叉树结点类型10 }BSTree;//二叉树结点类型1112 vector<char> path;
1314void Createb(BSTree **p)//建立二叉树15{
16char ch;
17     cin>>ch;
18if(ch!=‘.‘)
19    {
20         *p=(BSTree*)malloc(sizeof(BSTree));//申请空间21         (*p)->data=ch;//空间赋值22         Createb(&(*p)->lchild);//生成左子树23         Createb(&(*p)->rchild);//生成右子树24    }
25else *p=NULL;//空结点26}
2728int TreeDepth(BSTree *root)//树的深度29{
30if(root==NULL)
31return0;
32int left=TreeDepth(root->lchild);
33int right=TreeDepth(root->rchild);
34return (left>right) ? (left+1) : (right+1);
35}
3637void Findlongestpath(BSTree *root)//找到第一条最长路径38{
39     path.push_back(root->data);
40if(root->lchild==NULL&&root->lchild==NULL)
41return;
42if(TreeDepth(root->lchild)>=TreeDepth(root->rchild))//如果左子树高度大于或右子树高度43     Findlongestpath(root->lchild);//遍历左子树继续查找44else Findlongestpath(root->rchild);//遍历右子树进行查找45}
4647void printpath()
48{
49     vector<char>::iterator ite;
50for(ite=path.begin();ite!=path.end();++ite)
51         cout<<*ite<<"";
52         cout<<endl;
53         path.clear();//清理容器54}
5556void main()
57{
58     BSTree *root;//二叉树根结点59     cout<<"create BSTree root:"<<endl;//创建二叉树60     Createb(&root);
61     cout<<"root‘s depth is"<<TreeDepth(root)<<endl;//二叉树深度62     Findlongestpath(root);//找到最长路径63     cout<<"the longest path is:"<<endl;
64     printpath();//打印65 }

 

原文：http://www.cnblogs.com/wxdjss/p/5471799.html

内容总结

以上是互联网集市为您收集整理的二叉树中第一条最长的路径并输出此路径上各结点的值全部内容，希望文章能够帮你解决二叉树中第一条最长的路径并输出此路径上各结点的值所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1326771.html

来源：【匿名】