加载中…
个人资料
竹叶青
竹叶青
  • 博客等级:
  • 博客积分:0
  • 博客访问:64,960
  • 关注人气:3
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

【编程之美】3.8 求二叉树中节点的最大距离——按自己理解写的

(2013-03-06 20:09:57)
标签:

二叉树

分类: 学习

 

写完后才发现和http://www.cnblogs.com/miloyip/archive/2010/02/25/1673114.html的思路一致。不过我的写得直白繁冗,没有他的那么简洁优美,。

 

#include <iostream>

using namespace std;

 

 

struct NODE
{
 NODE* pLeft;        // 左子树
 NODE* pRight;       // 右子树
 int depth;          // 树的深度
 int maxDis;         // 树的最大距离
 char chValue;       // 该节点的值

 NODE(char c = '\0'):pLeft(NULL), pRight(NULL), maxDis(0), chValue(c){}
};

 

 

//最大距离的两个节点可能出现在树的左右子树上,也可能是某一子树上。
//以当前节点为根节点的树的最大距离,是左右子树的深度之和+2
//与
//左右子树的最大距离分别比较,
//取其最大值。
void FindMaxLen(NODE* pRoot)
{
 if (pRoot == NULL)
 {
  return;
 }

 //叶子节点的深度为0
 if (pRoot->pLeft == NULL && pRoot->pRight == NULL)
 {
  pRoot->depth = 0;
 }

 if(pRoot->pLeft)
 {
  FindMaxLen(pRoot->pLeft);
 }

 if (pRoot->pRight)
 {
  FindMaxLen(pRoot->pRight);
 }


 //比较左右子树的深度,取较大者+1作为树的深度,并求最大距离
 if (pRoot->pLeft && pRoot->pRight)
 {
  //深度
  pRoot->depth = pRoot->pLeft->depth > pRoot->pRight->depth ? pRoot->pLeft->depth : pRoot->pRight->depth;
  pRoot->depth += 1;

  //距离……
  int maxDisTmp = 0;
  //左右子树的最大距离取较大者
  maxDisTmp = pRoot->pLeft->maxDis > pRoot->pRight->maxDis ? pRoot->pLeft->maxDis : pRoot->pRight->maxDis;
  //左右子树的深度和+2(子树根节点与树的根节点之间还有一条连线)
  int sumDepth = pRoot->pLeft->depth + pRoot->pRight->depth + 2;
  //树的最大距离取深度和、左右子树最大值三者的max
  pRoot->maxDis = maxDisTmp > sumDepth ?  maxDisTmp : sumDepth;
 }
 else if (pRoot->pLeft)
 {
  //深度
  pRoot->depth = pRoot->pLeft->depth + 1;

  //距离……
  pRoot->maxDis = pRoot->depth > pRoot->pLeft->maxDis ? pRoot->depth : pRoot->pLeft->maxDis;
 }
 else if (pRoot->pRight)
 {
  //深度
  pRoot->depth = pRoot->pRight->depth + 1;

  //距离……
  pRoot->maxDis = pRoot->depth > pRoot->pRight->maxDis ? pRoot->depth : pRoot->pRight->maxDis;
 }
}

 

 

 

int main()
{
 //树的形状如下图
 NODE node[9];
 for (char i = '1'; i <= '9'; ++i)
 {
  node[i-'1'].chValue = i;
 }
 node[0].pLeft = &node[1];
 node[0].pRight = &node[8];
 node[1].pLeft = &node[2];
 node[1].pRight = &node[5];
 node[2].pLeft = &node[3];
 node[3].pLeft = &node[4];
 node[5].pRight = &node[6];
 node[6].pRight = &node[7];


 FindMaxLen(&node[0]);
 cout << node[0].maxDis << endl;
 return 0;
}

 

【编程之美】3.8 <wbr>求二叉树中节点的最大距离——按自己理解写的

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有