编程之美求二叉树中节点之间最大的距离

#include<iostream>using namespace std;//二叉树节点结构typedef struct TNODE_{int data;struct TNODE_*left;struct TNODE_*right;}TNode;//获取树的高度=路径+1（最长路径经过的边数+1）int GetLRDistance(TNode*t){int len=0;if(t==NULL){return 0;}else{int lenL=GetLRDistance(t->left);int lenR=GetLRDistance(t->right);len=(lenL>lenR)?lenL:lenR;len+=1;//return (len+1);}return len;}//获取树中节点之间的最大距离（可能是两个叶子节点或叶子节点与根节点）int GetMaxDistance(TNode*t){int distance=0;if(t==NULL){distance=0;//return 0;}else if(t->left!=NULL && t->right==NULL){//判断是否是子树的两个叶子节点之间，，还是其中的一个叶子节点与根节点int temp_distance=GetMaxDistance(t->left);int max_RootLeft=GetLRDistance(t->left);distance=temp_distance>max_RootLeft?temp_distance:max_RootLeft;}else if(t->left==NULL && t->right!=NULL){//判断是否是子树的两个叶子节点之间，还是其中的一个叶子节点与根节点int temp_distance=GetMaxDistance(t->right);int max_RootLeft=GetLRDistance(t->right);distance=temp_distance>max_RootLeft?temp_distance:max_RootLeft;}else if(t->left!=NULL && t->right!=NULL){//判断是否左右子树之间（左子树的高度+右子树的高度），还是左子树的节点之间，还是右子树的节点之间int maxLeft=GetMaxDistance(t->left);int maxRight=GetMaxDistance(t->right);int max_RootLeft=0,max_RootRight=0;max_RootLeft=GetLRDistance(t->left);max_RootRight=GetLRDistance(t->right);if(maxRight<maxLeft)distance=maxLeft;else distance=maxRight;int temp=max_RootRight+max_RootLeft;if(temp>distance)distance=temp;}return distance;}void OutputF(TNode*t){if(t!=NULL)cout<<t->data<<" ";else return;OutputF(t->left);OutputF(t->right);}void Test(){TNode*t=new TNode();t->data=1;t->left=t->right=NULL;TNode*t1=new TNode();t1->data=2;t1->left=t1->right=NULL;t->left=t1;TNode*t2=new TNode();t2->data=3;t2->left=t2->right=NULL;t1->left=t2;TNode*t3=new TNode();t3->data=4;t3->left=t3->right=NULL;t->right=t3;TNode*t4=new TNode();t4->data=5;t4->left=t4->right=NULL;t2->right=t4;TNode*t5=new TNode();t5->data=6;t5->left=t5->right=NULL;t3->right=t5;TNode*t6=new TNode();t6->data=7;t6->left=t6->right=NULL;t3->left=t6;TNode*t7=new TNode();t7->data=8;t7->left=t7->right=NULL;t6->left=t7;//打印先序遍历的结果；OutputF(t);cout<<endl;cout<<"树的最大距离值： "<<GetMaxDistance(t)<<endl;}int main(){Test();return 0;}

生活的最大悲剧不是失败，而是一个人已经习惯于失败。

相关文章：

你感兴趣的文章：

标签云：