首页 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
资讯 业界资讯 软件杂谈 编程开发 网站建设 网络观查 搜索引擎 移动应用 网站运营 网络地图
开发 移动开发 Web前端 架构设计 编程语言 互联网 数据库 系统运维 云计算 开发杂谈
[编程语言] 二叉树中任意两节点的最低共同父节点
二叉树中任意两节点的最低共同父节点

通过两个和二叉树相关的算法题来看看和递归在二叉树中的应用
输入二叉树中的两个结点,输出这两个结点在数中最低的共同父结点。
思路: 如果这两个节点不在同一个子树下面,那么这棵树的根节点就是他们的共同最低父节点。
如果两个都在右子树,那么以右子树的最上面的那个节点作为根节点,重新进行判断,递归调用。
同理两个都在左子树,则方法同上。  也就是说,最终的结果分别只有三种情况,一个节点在右子树,一个节点在左子树。两个节点都在右子树,两个节点都在左子树。
如果是第一种情况,那么当前的节点就是他们最低的公共节点,左右都在左子树,或者在右子树,那么就递归调用。
BinTree* GetParent(BinTree* root,BinTree* first,BinTree* second)
{
         if(root == NULL)
           return ;
         if(root == first || second == second)
         {
           return root;        
         }
         BinTree* Low_left = GetParent(root->left,first,second);
         BinTree* Low_right = GetParent(root->right,first,second);
         /*说明在左子树中没有找到和first/second中任何一个相同的节点  公共父节点右子树 而且第一个就是*/  
         if(Low_left == NULL)  
           return Low_right;
         /*在右子树中没有找到和first/second中任何一个相同的节点 公共父节点在左子树 而且第一个就是最低父节点*/
         else if(Low_right == NULL)
           return Low_left;
         else
            return root;
 } 
在左子树中没找到任何一个节点,那么就在右子树中找,在右子树中没找到任何一个节点,那么共同父节点肯定在左子树。如果在左右子树中各找到一个节点(注意并不可能同时找到两个节点的),那么当前节点就是最低共同父节点。
二叉树中任意两个节点的最远距离
这里的距离就是边的个数。
我们也同样可以使用递归来解决。所有的情况就是,最远的两个节点一个在左子树,一个在右子树,那么就是左子树中最远节点到当前节点的距离加上右子树中最远节点到当前节点的距离,也就是说最远距离跨越了根节点。第二种情况就是最远距离的两个节点都在右子树,那么我们就需要看右字数中任意两点的最远距离,第三种情况就是最远距离的两个节点都在左子树,那么我们就需要计算左子树中最远距离。然后比较三种情况中最远的距离即可
/*
  distance 是以root为根的的树,左子树到root的距离和右子树到root的距离的和  
  函数的返回值就是以root为跟的树 任意两点的最远距离 函数内部进行了比较选择
*/
int Distance(BinTree* root,int& distance)
{
    if( root == NULL)
    {
        distance = 0;
        return ; 
    }
    int left,right;
    int left_dis = Distance(root->left,left);
    int right_dis = Distance(root->right,right);
    distance = (left > right? left :right)+1;
    
    return max(left_dis,max(right_max,left+right));
} 

另外一种更加直观的比较:
int MaxDepth(BinTree* root)
{
    int depth = 0;
    if(root != NULL)
    {
       int left_depth = MaxDepth(root->left);
       int right_depth = MaxDepth(root->right);
       depth = left_depth > right_depty? left_depth : right_depth;
       depth++; 
    }
    return depth;
    }

int MaxDistance(BinTree* root)
{
    int maxdis = 0;
    if(root != NULL)
    {
        maxdis = MaxDepth(root->right) +MaxDepth(root->left);
        int left_dis = MaxDistance(root->left);
        int right_dis = MaxDistance(root->right);
        int temp = left_dis >  right_dis? left_dis:right_dis;
        maxdis = temp>maxdis ? temp :maxdis;
    }
    return maxdis;
    }



 此文从网络中自动搜索生成,不代表本网站赞成被搜索网站的内容或立场    查看原文
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2017年11日历
2017-11-18 23:50:02
 
  网站联系 软件世界网-www.sjsjw.com ©2014 蜀ICP备06016416号 三峰网旗下网站