注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ksnowlv的博客

积土成丘,集腋成裘,坚持再坚持!

 
 
 

日志

 
 

寻找二叉树两个节点的最近公共祖先  

2013-09-08 18:31:47|  分类: 算法与数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
// FindFirstCommonParentNodeTest.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iostream>
using namespace std;

struct TreeNode
{
    int m_nValue;
    TreeNode *m_pLeft;
    TreeNode *m_pRight;

    TreeNode()
    {
        m_pLeft = NULL;
        m_pRight = NULL;
        m_nValue = -1;
    }
};

//寻找二叉树两个结点的最低共同父节点
TreeNode *FindFirstCommonParentNode(TreeNode *pRoot, TreeNode *pNodeOne, TreeNode *pNodeTwo)
{
    if (NULL == pRoot)
    {
        printf("NULL\n");
        return NULL;
    }
    if (pRoot == pNodeOne || pRoot == pNodeTwo)
    {
        printf("pNodeOnepNodeTwo%d\n",pRoot->m_nValue);
        return pRoot;
    }

    printf("----pRoot = %d\n",pRoot->m_nValue);
    TreeNode *pLeft = FindFirstCommonParentNode(pRoot->m_pLeft, pNodeOne, pNodeTwo);
    TreeNode *pRight = FindFirstCommonParentNode(pRoot->m_pRight, pNodeOne, pNodeTwo);
   
    //1、左子树没有找到任何一个结点,则第一个公共父节点必定在右子树,而且找到第一个结点就是最低共同父节点
    if (NULL == pLeft)      
    {
        if (pRight)
        {
            printf("pLeft - right=%d\n",pRight->m_nValue);
        }
        else
        {
            printf("pLeft - right=\n");
        }
        ;
        return pRight;
    }
    //2、右子树没有找到任何一个结点,则第一个公共父节点必定在左子树,而且找到第一个结点就是最低共同父节点
    else if (NULL == pRight)
    {
        if (pLeft)
        {
            printf("right - pLeft=%d\n",pLeft->m_nValue);
        }
        else
        {
            printf("right - pLeft=\n");
        }
        
        return pLeft;
    }
    else //3、分别在结点的左右子树找到,则此节点必为第一个公共父节点
    {
        if (pRoot)
        {
            printf("pRoot=%d\n",pRoot->m_nValue);
        }
        else
        {
            printf("pRoot=NULL\n");
        }
        
        return pRoot;
    }
}


//假定所创建的二叉树如下图所示
/*
                                             1
                                          /     \
                                         2       3
                                        / \      /
                                       4   3    6
                                      / \   \  / \
                                     7   8  9  10 11
                                    /     \
                                   12      13
                                          /
                                         14
*/

int _tmain(int argc, _TCHAR* argv[])
{

    TreeNode* rootNode = new TreeNode();
    rootNode->m_nValue = 1;

    TreeNode* node2 = new TreeNode();
    node2->m_nValue = 2;
    rootNode->m_pLeft = node2;

    TreeNode* node4 = new TreeNode();
    node4->m_nValue = 4;
    node2->m_pLeft = node4;


    TreeNode* node3 = new TreeNode();
    node3->m_nValue = 3;
    node2->m_pRight = node3;

    TreeNode* node9 = new TreeNode();
    node9->m_nValue = 9;
    node3->m_pRight = node9;

    TreeNode* node7 = new TreeNode();
    node7->m_nValue = 7;
    node4->m_pLeft = node7;


    TreeNode* node8 = new TreeNode();
    node8->m_nValue = 8;
    node4->m_pRight = node8;

    TreeNode* node12 = new TreeNode();
    node12->m_nValue = 12;
    node7->m_pLeft = node12;

    TreeNode* node13 = new TreeNode();
    node13->m_nValue = 13;
    node8->m_pRight = node13;

    TreeNode* node14 = new TreeNode();
    node14->m_nValue = 14;
    node13->m_pLeft = node14;

    TreeNode* node3X = new TreeNode();
    node3X->m_nValue = 3;
    rootNode->m_pRight = node3X;


    TreeNode* node6 = new TreeNode();
    node6->m_nValue = 6;
    node3X->m_pLeft = node6;


    TreeNode* node10 = new TreeNode();
    node10->m_nValue = 10;
    node6->m_pLeft = node10;

    TreeNode* node11 = new TreeNode();
    node11->m_nValue = 11;
    node6->m_pLeft = node11;

   

    TreeNode* parentNode = FindFirstCommonParentNode(rootNode, node14, node11);

    cout<<"第一个结点为:"<<node14->m_nValue<<endl;
    cout<<"第二个结点为:"<<node11->m_nValue<<endl;
    cout<<"首个父结点为:"<<parentNode->m_nValue<<endl;

    parentNode = FindFirstCommonParentNode(rootNode, node14, node9);

    cout<<"第一个结点为:"<<node14->m_nValue<<endl;
    cout<<"第二个结点为:"<<node9->m_nValue<<endl;
    cout<<"首个父结点为:"<<parentNode->m_nValue<<endl;

    cout<<endl;
    return 0;
}
  评论这张
 
阅读(167)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018