相关文章推荐
树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。
二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right ...
先说说二叉树的存储结构，跟很多其它模型一样，也有顺序和链式两种方式。前者虽然使用简单，但是存在浪费空间的问题，举个例子，下图的二叉树，用顺序的方式存储(0表示空，没有子树)是:
二叉树就是每个结点最...
我在前面的博客中讲解了链表、栈和队列，这些数据结构其实都是线性表，并且给出了详细的实现。从今天开始，我们将要来学习树，树作为一种数据结构我们经常会用到，作为起步和基础，我们先来实现二叉树，也就是每个节...
我们在上一篇博客中讲解了二叉树，这一次我们来实现二叉树的进阶——二叉查找树（Binary Search Tree），又称二插排序树(Binary Sort Tree)。所以简称为BST。二插查找树的定...
1、基本概念
树是树型结构的简称，它是一种重要的非线性数据结构。
树的表示：通常使用广义表表示方法，即每棵树的根作为由子树构成的表的名字而放在表的前面，如下图的树对应的广义表表示为：
A（B（D，E（...
//c语言实现二叉树层次遍历（借助队列实现）
//二叉链表类型定义
typedef struct btnode
#define MAXSIZE 30
typedef char ElemT
typedef struct TNode *BiT
问题（假定根节点位于第0层）
1. 层次遍历二叉树（每层换行分开）
2. 层次遍历二叉树指定的某层
本文转自/kaituorensheng/p/355...
他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)数据结构 C语言 求二叉树中任意两结点间距离 - 『编程语言讨论求助区』
- 吾爱破解 - LCG - LSG |安卓破解|病毒分析|破解软件|
后使用快捷导航没有帐号？
只需一步，快速开始
请完成以下验证码
请完成以下验证码
查看: 805|回复: 2
数据结构 C语言 求二叉树中任意两结点间距离
阅读权限10
发帖求助前要善用【】功能，那里可能会有你要找的答案；
求助软件脱壳或者破解思路时，请务必在主题帖中描述清楚你的分析思路与方法，否则会当作求脱求破处理；
如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子分类改成【已解决】；
如何回报帮助你解决问题的坛友，一个好办法就是给对方加【热心】和【CB】，加分不会扣除自己的积分，做一个热心并受欢迎的人。
本帖最后由 流浪的二胡 于
07:12 编辑
现在求最大路径长度倒是没问题，路径长度小于10的是最后一位，大于10的后两位，类推。
遇到的问题：不知道该怎样实现输入两个节点，并求这两个节点的距离这个功能。求距离程序参考的是/articles/FZjye2
运行软件：Dev C/C++
QQ图片16.png (39.87 KB, 下载次数: 1)
17:07 上传
#include &stdio.h&
#include &stdlib.h&
#include &malloc.h&
#define TREEMAX 100
typedef struct BT
& & struct BT *lchild,*& && & //左子树& & 右子树
& & int NL,NR;& && && && && &&&//左孩子最长距离，右孩子最长距离&&
& & char S1,S2;& && && && && && &&&//该结点的値
//创建一个二叉树
BT *CreateTree();
void ShowTree(BT *T);
void PreOrder(BT *T);
void PostOrder(BT *T);
void LevelOrder(BT *T);
void InOrder(BT *T);
void FindMaxLen(BT *T);
int TreeDepth(BT *T);
int count = 0;
int main(void)
& && &&&BT *T=NULL;
& && &&&char ch1,ch2,a;
& && &&&ch1='y';
& && &&&while(ch1=='y'||ch1=='Y')
& && && && && & printf(&\n&);
& && && && && & printf(&\n\t\t& && && & 二叉树&);
& && && && && & printf(&\n\t\t**************************************************&);
& && && && && & printf(&\n\t\t*& && & 1-----建立二叉树& && && && && && && && & *&);
& && && && && & printf(&\n\t\t*& && & 2-----凹入显示& && && && && && && && && &*&);
& && && && && & printf(&\n\t\t*& && & 3-----先序遍历& && && && && && && && && &*&);
& && && && && & printf(&\n\t\t*& && & 4-----中序遍历& && && && && && && && && &*&);
& && && && && & printf(&\n\t\t*& && & 5-----后序遍历& && && && && && && && && &*&);
& && && && && & printf(&\n\t\t*& && & 6-----层次遍历& && && && && && && && && &*&);
& && && && && & printf(&\n\t\t*& && & 7-----二叉树中任意两结点间的距离& && && &*&);
& && && && && & printf(&\n\t\t*& && & 8-----求树深度& && && && && && && && && &*&);
& && && && && & printf(&\n\t\t*& && & 0-----返& & 回& && && && && && && && && &*&);
& && && && && & printf(&\n\t\t**************************************************&);
& && && && && & printf(&\n\t\t*& && &请选择菜单号（0--8）:& && && && && && && &*&);
& && && && && & scanf(&%c&,&ch2);
& && && && && & getchar();
& && && && && & printf(&\n&);
& && && && && & switch(ch2)
& && && && && & {
& && && && && && && && &case '1':
& && && && && && && && && && &&&printf(&\n\t\t 请按先序序列输入二叉树节点：\n&);
& && && && && && && && && && &&&printf(&\n\t\t 说明：输入结点（‘0’表示后继结点为空）后按回车.\n&);
& && && && && && && && && && &&&printf(&\n\t\t 请输入根节点：&);
& && && && && && && && && && &&&T=CreateTree();
& && && && && && && && && && &&&printf(&\n\t\t 二叉树成功建立！\n&);
& && && && && && && && &case '2':
& && && && && && && && && && &&&ShowTree(T);
& && && && && && && && &case '3':
& && && && && && && && && && &&&printf(&\n\t\t 该二叉树的先序遍历为：&);
& && && && && && && && && && &&&PreOrder(T);
& && && && && && && && &case '4':
& && && && && && && && && && &&&printf(&\n\t\t 该二叉树的中序遍历为：&);
& && && && && && && && && && &&&InOrder(T);
& && && && && && && && &case '5':
& && && && && && && && && & printf(&\n\t\t 该二叉树的后序遍历为：&);
& && && && && && && && && & PostOrder(T);
& && && && && && && && &case '6':
& && && && && && && && && && &&&printf(&\n\t\t 该二叉树的层次遍历为：&);
& && && && && && && && && && &&&LevelOrder(T);
& && && && && && && && &case '7':
& && && && && && && && && && &&&printf(&\n\t\t 二叉树中任意两结点间的距离: &);FindMaxLen(T);& && &&&
& && && && && && && && &case '8':
& && && && && && && && && && &&&printf(&\n\t\t 该树的深度是: %d&,TreeDepth(T));
& && && && && && && && &case '0':
& && && && && && && && && && &&&ch1='n';
& && && && && && && && &default:
& && && && && && && && && && &&&printf(&\n\t\t***请注意：输入有误！***&);
& && && && && & }
& && && && && & if(ch2!=0)
& && && && && & {
& && && && && && && && &printf(&\n\t\t按【enter】键继续，按任意键返回主菜单！\n&);
& && && && && && && && &a=getchar();
& && && && && && && && &if(a!='\xA')& &&&{&&getchar();ch1='n';&&}
& && && && && & }
& && && && && && && && &
//建立二叉树
BT *CreateTree()
& && &&&BT *t;
& && &&&scanf(&%c&,&x);
& && &&&getchar();
& && &&&if(x=='0')& & t=NULL;
& && &&&else
& && && && && & t=(BT *)malloc(100);
& && && && && & t-&data=x;
& && && && && & printf(&\n\t\t 请输入%c结点的左子结点：&,t-&data);
& && && && && & t-&lchild=CreateTree();
& && && && && & printf(&\n\t\t 请输入%c结点的右子结点：&,t-&data);
& && && && && & t-&rchild=CreateTree();
//先序遍历
void PreOrder(BT *T)
& && && &if(T)
& && && &{
& && && && && &&&printf(&%3c&,T-&data);
& && && && && &&&PreOrder(T-&lchild);
& && && && && &&&PreOrder(T-&rchild);
& && && &}
//中序遍历
void InOrder(BT *T)
& && && &if(T)
& && && &{
& && && && && &&&InOrder(T-&lchild);
& && && && && &&&printf(&%3c&,T-&data);
& && && && && &&&InOrder(T-&rchild);
& && && &}
//后序遍历
void PostOrder(BT *T)
& && && &if(T)
& && && &{
& && && && && &&&PostOrder(T-&lchild);
& && && && && &&&PostOrder(T-&rchild);
& && && && && &&&printf(&%3c&,T-&data);
& && && &}
//层次遍历
void LevelOrder(BT *T)
& && && &int i,j;
& && && &BT *q[100],*p;
& && && &p=T;
& && && &if(p!=NULL)&&{&&i=1;q=p;j=2;&&}
& && && &while(i!=j)
& && && &{
& && && && && &&&p=q;printf(&%3c&,p-&data);
& && && && && &&&if(p-&lchild!=NULL)& && &&&{&&q[j]=p-&j++;& &}
& && && && && &&&if(p-&rchild!=NULL)& && &&&{&&q[j]=p-&j++;& &}
& && && && && &&&i++;
& && && &}
//求树深度
& &int TreeDepth(BT *T)
& && && &int ldep,
& && && &if(T==NULL) return 0;
& && && &else
& && && &{
& && && && && &&&ldep=TreeDepth(T-&lchild);
& && && && && &&&rdep=TreeDepth(T-&rchild);
& && && && && &&&if(ldep&rdep)& & return ldep+1;
& && && && && &&&else&&return rdep+1;
& && && &}
int nMaxLen=0;
//寻找树最长的两端距离
void FindMaxLen(BT *T)
& && &&&int nMaxLen=0;
& && &&&//遍历到叶子结点，返回
& && &&&if(T==NULL)
& && && & {
& && && && && &
& && && & }
& && &&&//如果左子树为空，那么该结点的左边最长距离为0
& && &&&if(T-&lchild==NULL)
& && && & {
& && && && && & T-&NL=0;
& && && &&&}
& && && &//如果右子树为空，那么该结点的右边最长距离为0
& && && &if(T-&rchild==NULL)
& && && & {
& && && && && && &T-&NR=0;
& && && && && &&&}
& && &&&//如果左子树不为空，递归寻找左子树最长距离& && && &
& && &&&if(T-&lchild!=NULL)
& && && & {
& && && && && && &FindMaxLen(T-&lchild);
& && && && && && &}
& && &&&//如果右子树不为空，递归寻找右子树最长距离
& && && &if(T-&rchild!=NULL)
& && && &&&{
& && && && && && & FindMaxLen(T-&rchild);
& && && && && && &}
& && &&&//计算左子树最长结点距离& && && &
& &&&if(T-&lchild!=NULL)
& && && &{
& && && && && &&&int nTempMax=0;
& && && && && &&&if(T-&lchild-&NL&T-&lchild-&NR)
& && && && && && && &nTempMax=T-&lchild-&NL;
& && && && && &&&else
& && && && && && && &nTempMax=T-&lchild-&NR;
& && && && && && && &T-&NL=nTempMax+1;
& && && && && & }
& && &&&//计算右子树最长结点距离
& && &&&if(T-&rchild!=NULL)
& && && && && & int nTempMax=0;
& && && && && & if(T-&rchild-&NL&T-&rchild-&NR)
& && && && && && &&&nTempMax=T-&rchild-&NL;
& && && && && & else
& && && && && && &&&nTempMax=T-&rchild-&NR;
& && && && && && &&&T-&NR=nTempMax+1;
& && && & }
& && &&&//更新最长距离&&
& && && & if(T-&NL+T-&NR&nMaxLen)
& && && & nMaxLen=T-&NL+T-&NR;
& && && & printf(&%d&,nMaxLen);
void ShowTree(BT *T)
& && && &BT *stack[TREEMAX],*p;
& && && &int level[TREEMAX][2],top,n,i,width=4;
& && && &if(T!=NULL)
& && && &{
& && && && && &&&printf(&\n\t\t 凹入表示法：\n\t\t&);
& && && && && &&&top=1;
& && && && && &&&stack[top]=T;
& && && && && &&&level[top][0]=
& && && && && &&&while(top&0)
& && && && && &&&{
& && && && && && && && & p=stack[top];
& && && && && && && && & n=level[top][0];
& && && && && && && && & for(i=1;i&=n;i++)& & printf(&&&&);
& && && && && && && && & printf(&%c&,p-&data);
& && && && && && && && & for(i=n+1;i&30;i+=2)& & printf(&︻&);
& && && && && && && && & printf(&\n\t\t&);
& && && && && && && && & top--;
& && && && && && && && & if(p-&rchild!=NULL)
& && && && && && && && & {
& && && && && && && && && && && &top++;
& && && && && && && && && && && &stack[top]=p-&
& && && && && && && && && && && &level[top][0]=n+
& && && && && && && && && && && &level[top][1]=2;
& && && && && && && && & }
& && && && && && && && & if(p-&lchild!=NULL)
& && && && && && && && & {
& && && && && && && && && && && &top++;
& && && && && && && && && && && &stack[top]=p-&
& && && && && && && && && && && &level[top][0]=n+
& && && && && && && && && && && &level[top][1]=1;
& && && && && && && && & }
& && && && && && && && &&&
& && && && && &&&}
& && && &}
输入二叉树
& && && && && && && && && && && && && && && & a
& && && && && && && && && && &b& && && && && && && && && && &&&c
& && && && && && && & d& && && && &e& && && && && && &&&f& && && &&&k
选项7运行后结果0020024
热心回复！
发帖求助前要善用【】功能，那里可能会有你要找的答案；如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子分类或者标题加上【已解决】；如何回报帮助你解决问题的坛友，一个好办法就是给对方加【热心】和【CB】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
阅读权限20
可以，感谢分享
发帖求助前要善用【】功能，那里可能会有你要找的答案；如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子分类或者标题加上【已解决】；如何回报帮助你解决问题的坛友，一个好办法就是给对方加【热心】和【CB】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
阅读权限10
两个点a b分别往上一直走到根节点，会出现2种情况，
1、b(a)是a(b)若干次向上迭代后的父节点，距离为迭代的次数
2、a b会路过同一个节点，距离为两点到该节点的距离之和
发帖求助前要善用【】功能，那里可能会有你要找的答案；如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子分类或者标题加上【已解决】；如何回报帮助你解决问题的坛友，一个好办法就是给对方加【热心】和【CB】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
免责声明：吾爱破解所发布的一切破解补丁、注册机和注册信息及软件的解密分析文章仅限用于学习和研究目的；不得将上述内容用于商业或者非法用途，否则，一切后果请用户自负。本站信息来自网络，版权争议与本站无关。您必须在下载后的24个小时之内，从您的电脑中彻底删除上述内容。如果您喜欢该程序，请支持正版软件，购买注册，得到更好的正版服务。如有侵权请邮件与我们联系处理。
( 京ICP备号 | 京公网安备 87号 )
Powered by Discuz!
Comsenz Inc.实验六 二叉树实验报告(1)_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
实验六 二叉树实验报告(1)
&&数据结构 C语言描写的二叉树实验报告
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩4页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢编程c语言-求二叉树问题的C程序代码
作者：用户
浏览：291 次
求二叉树问题的C程序代码//从终端输入一个整数序列，构建一棵允许具有重复结点的二叉排序树（左子树元素小，右子树不小）：//(1)使用依次插入元素的方法（InsertBST）构建二叉排序树；//(2)分
求二叉树问题的C程序代码
//从终端输入一个整数序列，构建一棵允许具有重复结点的二叉排序树（左子树元素小，右子树不小）：
使用依次插入元素的方法（InsertBST）构建二叉排序树；
分别写出二叉树的前序、中序、后序遍历递归算法；
写出前序遍历序列的非递归算法（使用以前写好的堆栈代码）；
使用递归算法求该二叉树中叶子结点和非叶子结点的个数；
使用递归算法求该二叉树的高度；
层次遍历该二叉树（使用以前写好的队列代码）；
从终端输入一个整数，查找这个整数是否在该二叉树中，成功返回true，否则false（要求使用非递归）；
销毁这个二叉树，释放其中的每一个结点；
搜搜吧，网上很多。
解决方案二：
既然问题这么清楚，每一个都可以上网查查才是，何必做伸手党呢？
任何一本数据结构的书都会把链表讲清楚的~
【云栖快讯】2017互联网超级工程阿里双11完美落幕，交易额突破1682亿，但阿里工程师如何玩转“超级工程”，背后黑科技又是如何？12月13-14日，12位大咖直播分享揭秘1682亿背后技术实践，马上预约&&
稳定可靠、可弹性伸缩的在线数据库服务，全球最受欢迎的开源数据库之一
6款热门基础云产品6个月免费体验；2款产品1年体验;1款产品2年体验
弹性可伸缩的计算服务，助您降低 IT 成本，提升运维效率
开发者常用软件，超百款实用软件一站式提供如何求二叉树深度的递归算法是什么？
如何求二叉树深度的递归算法是什么？
09-03-12 &
首先你要清楚Bitree的数据结构 左分支T-&lchild 和右分支T-&rchild 同时叶子节点也有2个分支 都为null好了 现在我们分析一下这个函数 当所给的参数T是null时，返回0 说明这个树只有一个叶子节点 深度为0 当所给的参数不是null时 函数调用自己看看这个参数的左分支是不是null 如果不是继续调用自己看看左分支的左分支是不是null 直到最后一个的左分支是null 然后看与最后一个左分支并列的右分支是不是null 不是的话自动调用自己 直到是null 然后u（左分支深度）和v（右分支深度）比较 返回 值大的作为深度第一次到null返回的值为0 然后调用这个函数的上一层函数就得到一个返回值0 比如u=0假设此时v也=0 那么这个上一层函数就会判断（0&0） 然后运行v+1（因为0不大于0所以运行的是v+1） 向他的上一层返回1 以此类推 就返回了树的深度
请登录后再发表评论!
首先你要清楚Bitree的数据结构 左分支T-&lchild 和右分支T-&rchild 同时叶子节点也有2个分支 都为null 好了 现在我们分析一下这个函数 当所给的参数T是null时，返回0 说明这个树只有一个叶子节点 深度为0 当所给的参数不是null时 函数调用自己看看这个参数的左分支是不是null 如果不是继续调用自己看看左分支的左分支是不是null 直到最后一个的左分支是null 然后看与最后一个左分支并列的右分支是不是null 不是的话自动调用自己 直到是null 然后u（左分支深度）和v（右分支深度）比较 返回 值大的作为深度 第一次到null返回的值为0 然后调用这个函数的上一层函数就得到一个返回值0 比如u=0假设此时v也=0 那么这个上一层函数就会判断（0&0） 然后运行v+1（因为0不大于0所以运行的是v+1） 向他的上一层返回1 以此类推 就返回了树的深度
请登录后再发表评论!