树上最远距离
题目：如果我们把二叉树看做图，父子节点之间的连线看成是双向的，我们姑且定义“距离”为两个节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。
如下图所示，树中相距最远的两个节点为A,B，最大距离为6。
书上对这个问题的分析是很清楚的，计算一个二叉树的最大距离有两个情况：
情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者
对于情况A来说，只需要知道左右子树的深度，然后加起来即可。
对于情况B来说，需要知道左子树的最远距离，右子树的最远距离。
只需要计算这两种情况的路径距离，并取其最大值，就是该二叉树的最大距离。
#include <iostream>
#include <stack>
#include <queue>using namespace std;
typedef struct node
{
int val;
struct node *left;
struct node *right;
//node(int x):val(x),left(NULL),right(NULL){}
}BiTreeNode,*BiTree;
class tree
{
public:
void createBiTree(BiTree &T) //&的意思是传进来节点指针的引用，括号内等价于 BiTreeNode* &T,目的是让传递进来的指针发生改变
{
int c;
cin >> c;
if(0 == c) //当遇到#时，令树的根节点为NULL，从而结束该分支的递归
T = NULL;
else
{
T = new BiTreeNode;
T->val=c;
createBiTree(T->left);
createBiTree(T->right);
}
}
queue<int> strtoint(string str)
{
int i=0,j=0,temp=0;
queue<int> res;
while (i<str.length())
{
if(str[i]=='#')
{
res.push(INT_MIN);
i=i+2;
continue;
}
j=i;
while(str[i]!='!')
i++;
while(j!=i)
{
temp=(str[j]-'0') + temp * 10;
j++;
}
res.push(temp);
temp=0;
i++;
}
return res;
}
bool Des(BiTree &T,queue<int> &res)
{
if(res.front()==INT_MIN)
{
res.pop();
return false;
}
T = new BiTreeNode;
T->val=res.front();
T->left=NULL;
T->right=NULL;
res.pop();
Des(T->left,res);
Des(T->right,res);
}
BiTree createBiTree2(string str)
{
queue<int> res;
node* root=NULL;
res=strtoint(str);
Des(root,res);
return root;
}
//前序遍历二叉树并打印
void preTraverse(BiTree T)
{
if(T)
{
cout<<T->val<<" ";
preTraverse(T->left);
preTraverse(T->right);
}
}
void PrevOrder_NonR(BiTree T)
{
if(T)
{
stack<node *>s;
while(T||!s.empty())
{
while(T)
{
s.push(T);
cout<<T->val<<" ";
T=T->left;
}
node *top=s.top();
s.pop();
T=top->right;
}
cout<<endl;
}
}
//中序遍历二叉树并打印
void midTraverse(BiTree T)
{
if(T)
{
midTraverse(T->left);
cout<<T->val<<" ";
midTraverse(T->right);
}
}
void MidvOrder_NonR(BiTree T)
{
if(T)
{
stack<node *>s;
while(T||!s.empty())
{
while(T)
{
s.push(T);
T=T->left;
}
node *top=s.top();
cout<<top->val<<" ";
s.pop();
T=top->right;
}
cout<<endl;
}
}
//后续遍历二叉树并打印
void postTraverse(BiTree T)
{
if(T)
{
postTraverse(T->left);
postTraverse(T->right);
cout<<T->val<<" ";
}
}
void PostvOrder_NonR(BiTree T)
{
if(T)
{
stack<node *>s;
node *pre=NULL;
while(T||!s.empty())
{
while(T)
{
s.push(T);
T=T->left;
}
node *top=s.top();
if(top->right==NULL||pre==top->right)
{
cout<<top->val<<" ";
pre=top;
s.pop();
}
else
T=top->right;
}
cout<<endl;
}
}
//层序遍历二叉树
void print_tree(BiTree T)
{
queue<node *> rel;
rel.push(T);
while(!rel.empty())
{
node *front=rel.front();
cout<<front->val<<" ";
rel.pop();
if(front->left !=NULL)
rel.push(front->left);
if(front->right !=NULL)
rel.push(front->right);
}
cout<<endl;
}
};
class Dist_long
{
public :
int find_longest(BiTree T)
{
vector<int> temp;
temp = PostOrder_reverse(T);
return temp[0];
}
vector<int> PostOrder_reverse(BiTree T)
{
vector<int> res(2,0);
//RES[0]记录节点间最大距离，res[1]记录从该节点到最左或最右节点的距离的最大值
if(!T)
return res;
vector<int> ltemp,rtemp;
int temp;
ltemp=PostOrder_reverse(T->left);
rtemp=PostOrder_reverse(T->right);
res[1] = ((ltemp[1]> rtemp[1])) ? ltemp[1]:rtemp[1]+1;
temp = ltemp[0]> rtemp[0] ? ltemp[0]:rtemp[0];
res[0] = ((ltemp[1] + rtemp[1] +1)> temp ) ? (ltemp[1] + rtemp[1] +1):temp;
}
};
int main()
{
string str="1!2!4!#!#!5!#!#!3!6!#!#!7!#!#!";
tree s;
BiTree T; //声明一个指向二叉树根节点的指针
T=s.createBiTree2(str);
cout<<"二叉树创建完成！"<<endl;
cout<<"前序遍历二叉树1："<<endl;
s.preTraverse(T);
cout<<endl;
cout<<"前序遍历二叉树2："<<endl;
s.PrevOrder_NonR(T);
cout<<"中序遍历二叉树1："<<endl;
s.midTraverse(T);
cout<<endl;
cout<<"中序遍历二叉树2："<<endl;
s.MidvOrder_NonR(T);
cout<<"后序遍历二叉树1："<<endl;
s.postTraverse(T);
cout<<endl;
cout<<"后序遍历二叉树2："<<endl;
s.PostvOrder_NonR(T);
cout<<"层序遍历二叉树2："<<endl;
s.print_tree(T);
Dist_long d;
int len= d.find_longest(T);
cout<<"len is "<<len<<endl;
return 0;
}