欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實(shí)現(xiàn)尋找最低公共父節(jié)點(diǎn)的方法

 更新時(shí)間:2014年09月18日 09:53:08   投稿:shichen2014  
這篇文章主要介紹了C++實(shí)現(xiàn)尋找最低公共父節(jié)點(diǎn)的方法,是數(shù)據(jù)結(jié)構(gòu)中二叉樹的一個(gè)經(jīng)典算法,有一定的借鑒價(jià)值,需要的朋友可以參考下

本文實(shí)例講述了C++實(shí)現(xiàn)尋找最低公共父節(jié)點(diǎn)的方法,是數(shù)據(jù)結(jié)構(gòu)中二叉樹的經(jīng)典算法。分享給大家供大家參考。具體方法如下:

最低公共父節(jié)點(diǎn),意思很好理解。

思路1:最低公共父節(jié)點(diǎn)滿足這樣的條件:兩個(gè)節(jié)點(diǎn)分別位于其左子樹和右子樹,那么定義兩個(gè)bool變量,leftFlag和rightFlag,如果在左子樹中,leftFlag為true,如果在右子樹中,rightFlag為true,僅當(dāng)leftFlag == rightFlag == true時(shí),才能滿足條件。

實(shí)現(xiàn)代碼如下:

#include <iostream>

using namespace std;

struct Node
{
 Node(int i = 0, Node *pLeft = NULL, Node *pRight = NULL) : data(i), left(pLeft),
 right(pRight) {}
 Node *left;
 Node *right;
 int data;
};

Node *constructNode(Node **pNode1, Node **pNode2)
{
 Node *node12 = new Node(12);
 Node *node11 = new Node(11);
 Node *node10 = new Node(10);
 Node *node9 = new Node(9, NULL, node12);
 Node *node8 = new Node(8, node11, NULL);
 Node *node7 = new Node(7);
 Node *node6 = new Node(6);
 Node *node5 = new Node(5, node8, node9);
 Node *node4 = new Node(4, node10);
 Node *node3 = new Node(3, node6, node7);
 Node *node2 = new Node(2, node4, node5);
 Node *node1 = new Node(1, node2, node3);

 *pNode1 = node6;
 *pNode2 = node12;

 return node1;
}

bool isNodeIn(Node *root, Node *node1, Node *node2)
{
 if (node1 == NULL || node2 == NULL)
 {
 throw("invalid node1 and node2");
 return false;
 }
 if (root == NULL)
 return false;

 if (root == node1 || root == node2)
 {
 return true;
 }
 else
 {
 return isNodeIn(root->left, node1, node2) || isNodeIn(root->right, node1, node2);
 }
}

Node *lowestFarther(Node *root, Node *node1, Node *node2)
{
 if (root == NULL || node1 == NULL || node2 == NULL || node1 == node2)
 {
 return NULL;
 }
 
 bool leftFlag = false;
 bool rightFlag = false;
 leftFlag = isNodeIn(root->left, node1, node2);
 rightFlag = isNodeIn(root->right, node1, node2);

 if (leftFlag == true && rightFlag == true)
 {
 return root;
 }
 else if (leftFlag == true)
 {
 return lowestFarther(root->left, node1, node2);
 }
 else
 {
 return lowestFarther(root->right, node1, node2);
 }
}

void main()
{
 Node *node1 = NULL;
 Node *node2 = NULL;
 Node *root = constructNode(&node1, &node2);

 cout << "node1: " << node1->data << endl;
 cout << "node2: " << node2->data << endl;
 cout << "root: " << root->data << endl;

 Node *father = lowestFarther(root, node1, node2);

 if (father == NULL)
 {
 cout << "no common father" << endl;
 }
 else
 {
 cout << "father: " << father->data << endl;
 }
}

這類問題在面試的時(shí)候常會遇到,對此需要考慮以下情形:

1. node1和node2指向同一節(jié)點(diǎn),這個(gè)如何處理
2. node1或node2有不為葉子節(jié)點(diǎn)的可能性嗎
3. node1或node2一定在樹中嗎

還要考慮一個(gè)效率問題,上述代碼中用了兩個(gè)遞歸函數(shù),而且存在不必要的遞歸過程,仔細(xì)思考,其實(shí)一個(gè)遞歸過程足以解決此問題

實(shí)現(xiàn)代碼如下:

#include <iostream>

using namespace std;

struct Node
{
 Node(int i = 0, Node *pLeft = NULL, Node *pRight = NULL) : data(i),
 left(pLeft), right(pRight) {}
 int data;
 Node *left;
 Node *right;
};

Node *constructNode(Node **pNode1, Node **pNode2) 
{ 
 Node *node12 = new Node(12); 
 Node *node11 = new Node(11); 
 Node *node10 = new Node(10); 
 Node *node9 = new Node(9, NULL, node12); 
 Node *node8 = new Node(8, node11, NULL); 
 Node *node7 = new Node(7); 
 Node *node6 = new Node(6); 
 Node *node5 = new Node(5, node8, node9); 
 Node *node4 = new Node(4, node10); 
 Node *node3 = new Node(3, node6, node7); 
 Node *node2 = new Node(2, node4, node5); 
 Node *node1 = new Node(1, node2, node3); 

 *pNode1 = node6; 
 *pNode2 = node5; 

 return node1; 
}

bool lowestFather(Node *root, Node *node1, Node *node2, Node *&dest)
{
 if (root == NULL || node1 == NULL || node2 == NULL || node1 == node2)
 return false;
 if (root == node1 || root == node2)
 return true;

 bool leftFlag = lowestFather(root->left, node1, node2, dest);
 bool rightFlag = lowestFather(root->right, node1, node2, dest);
 
 if (leftFlag == true && rightFlag == true)
 {
 dest = root;
 }
 if (leftFlag == true || rightFlag == true)
 return true;
}

int main()
{
 Node *node1 = NULL;
 Node *node2 = NULL;
 Node *root = constructNode(&node1, &node2);

 bool flag1 = false;
 bool flag2 = false;
 Node *dest = NULL;
 bool flag = lowestFather(root, node1, node2, dest);

 if (dest != NULL)
 {
 cout << "lowest common father: " << dest->data << endl;
 }
 else
 {
 cout << "no common father!" << endl;
 }

 return 0;
}

下面再換一種方式的寫法如下:

#include <iostream>

using namespace std;

struct Node
{
 Node(int i = 0, Node *pLeft = NULL, Node *pRight = NULL) : data(i),
 left(pLeft), right(pRight) {}
 int data;
 Node *left;
 Node *right;
};

Node *constructNode(Node **pNode1, Node **pNode2) 
{ 
 Node *node12 = new Node(12); 
 Node *node11 = new Node(11); 
 Node *node10 = new Node(10); 
 Node *node9 = new Node(9, NULL, node12); 
 Node *node8 = new Node(8, node11, NULL); 
 Node *node7 = new Node(7); 
 Node *node6 = new Node(6); 
 Node *node5 = new Node(5, node8, node9); 
 Node *node4 = new Node(4, node10); 
 Node *node3 = new Node(3, node6, node7); 
 Node *node2 = new Node(2, node4, node5); 
 Node *node1 = new Node(1, node2, node3); 

 *pNode1 = node11; 
 *pNode2 = node12; 

 return node1; 
}

Node* lowestFather(Node *root, Node *node1, Node *node2)
{
 if (root == NULL || node1 == NULL || node2 == NULL || node1 == node2)
 return NULL;
 if (root == node1 || root == node2)
 return root;

 Node* leftFlag = lowestFather(root->left, node1, node2);
 Node* rightFlag = lowestFather(root->right, node1, node2);

 if (leftFlag == NULL)
 return rightFlag;
 else if (rightFlag == NULL)
 return leftFlag;
 else
 return root;
}

int main()
{
 Node *node1 = NULL;
 Node *node2 = NULL;
 Node *root = constructNode(&node1, &node2);

 bool flag1 = false;
 bool flag2 = false;
 Node *dest = NULL;
 Node* flag = lowestFather(root, node1, node2);

 if (flag != NULL)
 {
 cout << "lowest common father: " << flag->data << endl;
 }
 else
 {
 cout << "no common father!" << endl;
 }

 return 0;
}

希望本文所述對大家C++程序算法設(shè)計(jì)的學(xué)習(xí)有所幫助。

相關(guān)文章

  • 應(yīng)用程序操作NorFlash示例代碼分享(norflash接口使用方法)

    應(yīng)用程序操作NorFlash示例代碼分享(norflash接口使用方法)

    相對于操作NandFlash,操作NorFlash相對簡單,因?yàn)榛静恍枰紤]壞塊,NorFlash也沒有OOB區(qū)域,也跟ECC沒有關(guān)系。讀寫擦除相對容易,下面看個(gè)例子吧
    2013-12-12
  • C++中的動(dòng)態(tài)分派在HotSpot?VM中的應(yīng)用小結(jié)

    C++中的動(dòng)態(tài)分派在HotSpot?VM中的應(yīng)用小結(jié)

    多態(tài)是面向?qū)ο缶幊陶Z言的重要特性,它允許基類的指針或引用指向派生類的對象,而在具體訪問時(shí)實(shí)現(xiàn)方法的動(dòng)態(tài)綁定,這篇文章主要介紹了C++的動(dòng)態(tài)分派在HotSpot?VM中的重要應(yīng)用,需要的朋友可以參考下
    2023-09-09
  • C語言基礎(chǔ)知識點(diǎn)解析(extern,static,typedef,const)

    C語言基礎(chǔ)知識點(diǎn)解析(extern,static,typedef,const)

    本篇文章是對C語言基礎(chǔ)知識點(diǎn)(extern,static,typedef,const)的用法進(jìn)行了詳細(xì)的分析介紹,需要的朋友可以過來參考下
    2013-10-10
  • C++詳細(xì)講解互斥量與lock_guard類模板及死鎖

    C++詳細(xì)講解互斥量與lock_guard類模板及死鎖

    線程的主要優(yōu)勢在于,能夠通過全局變量來共享信息。不過,這種便捷的共享是有代價(jià)的:必須確保多個(gè)線程不會同時(shí)修改同一變量,或者某一線程不會讀取正由其他線程修改的變量。為了防止出現(xiàn)線程某甲試圖訪 問一共享變量時(shí),線程某乙正在對其進(jìn)行修改。引入了互斥量
    2022-07-07
  • 老生常談c++中的靜態(tài)成員

    老生常談c++中的靜態(tài)成員

    有時(shí)候需要類的一些成員與類本身相關(guān)聯(lián),而不是與類的每個(gè)對象相關(guān)聯(lián)。比如類的所有對象都要共享的變量,這個(gè)時(shí)候我們就要用到類的靜態(tài)成員,今天通過實(shí)例代碼給大家詳細(xì)介紹,需要的朋友參考下吧
    2021-07-07
  • C語言輸出唯一的子串

    C語言輸出唯一的子串

    這篇文章主要介紹了C語言輸出唯一的子串,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2021-12-12
  • C語言實(shí)現(xiàn)文件內(nèi)容按行隨機(jī)排列的算法示例

    C語言實(shí)現(xiàn)文件內(nèi)容按行隨機(jī)排列的算法示例

    這篇文章主要介紹了C語言實(shí)現(xiàn)文件內(nèi)容按行隨機(jī)排列的算法,涉及C語言字符串、數(shù)組遍歷與隨機(jī)數(shù)相關(guān)算法實(shí)現(xiàn)技巧,需要的朋友可以參考下
    2017-09-09
  • Qt實(shí)現(xiàn)簡單五子棋小游戲

    Qt實(shí)現(xiàn)簡單五子棋小游戲

    這篇文章主要為大家詳細(xì)介紹了Qt實(shí)現(xiàn)簡單五子棋小游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-08-08
  • 解析VC中創(chuàng)建DLL,導(dǎo)出全局變量,函數(shù)和類的深入分析

    解析VC中創(chuàng)建DLL,導(dǎo)出全局變量,函數(shù)和類的深入分析

    本篇文章是對VC中創(chuàng)建DLL,導(dǎo)出全局變量,函數(shù)和類進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
    2013-05-05
  • C++中的數(shù)組、鏈表與哈希表

    C++中的數(shù)組、鏈表與哈希表

    這篇文章主要介紹了C++中的數(shù)組、鏈表與哈希表,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-09-09

最新評論