1、二叉树定义:
typedef struct BTreeNodeElement_t_ { void *data; } BTreeNodeElement_t; typedef struct BTreeNode_t_ { BTreeNodeElement_t *m_pElemt; struct BTreeNode_t_ *m_pLeft; struct BTreeNode_t_ *m_pRight; } BTreeNode_t;
2、查找二叉树中两个节点的最低祖先节点(或近期公共父节点等)
最低祖先节点就是从根节点遍历到给定节点时的最后一个同样节点
比如:
A
B C
D E F G
H I J K L M N O
如上图,H和J的最低祖先节点是B。
由于从根节点A到H的链路为: A B D H
从根节点A到J的链路为: A B E J
查看链路节点可知,B是最后一个同样节点,也就是所谓的近期公共父节点或者说最低祖先节点。
(1)递归方式
假设给定pRoot是NULL,即空树,则返回的公共节点自然就是NULL;
假设给定pRoot与两个节点中不论什么一个同样,说明,pRoot在就是所要找的两个节点之中的一个,则直接返回pRoot,表明在当前链路中找到至少一个节点;
假设给定pRoot不是两个节点中不论什么一个,则说明,须要在pRoot的左右子树中又一次查找,此时有三种情况:两个节点都在左子树上;两个节点都在右子树上;一个在左子树,一个在右子树上;详细来说,就是:
情况一:假设左子树查找出的公共节点是NULL,则表明从左子树根节点開始到左子树的全部叶子节点等全部节点中,没有找到两个节点中的不论什么一个,这就说明,这两个节点不在左子树上,不在左子树,则必然在右子树上;
情况二:假设右子树查找的公共节点是NULL,说明在右子树中无法找到不论什么一个节点,则两个节点必然在左子树上;
情况三: 假设左右子树查找的公共节点都不是NULL,说明左右子树中各包括一个节点,则当前节点pRoot就是最低公共节点,返回就能够了。
三种情况是相互排斥的, 仅仅能是当中之中的一个。
BTreeNode_t *GetLastCommonParent( BTreeNode_t *pRoot, BTreeNode_t *pNode1, BTreeNode_t *pNode2){ if( pRoot == NULL ) //说明是空树,不用查找了,也就找不到相应节点,则返回NULL return NULL; if( pRoot == pNode1 || pRoot == pNode2 )//说明在当前子树的根节点上找到两个节点之中的一个 return pRoot; BTreeNode_t *pLeft = GetLastCommonParent( pRoot->m_pLeft, pNode1, pNode2); //左子树中的查找两个节点并返回查找结果 BTreeNode_t *pRight = GetLastCommonParent( pRoot->m_pRight, pNode1, pNode2);//右子树中查找两个节点并返回查找结果 if( pLeft == NULL )//假设在左子树中没有找到,则断定两个节点都在右子树中,能够返回右子树中查询结果;否则,须要结合左右子树查询结果共同断定 return pRight; if ( pRight == NULL )//假设在右子树中没有找到,则断定两个节点都在左子树中,能够返回左子树中查询结果;否则,须要结合左右子树查询结果共同断定 return pLeft; return pRoot;//假设在左右子树中都找两个节点之中的一个,则pRoot就是最低公共祖先节点,返回就可以。 }
(2)非递归方式:
BTreeNode_t *GetLastCommonParent(BTreeNode_t *pRoot, BTreeNode_t *pNode1, BTreeNode_t *pNode2){ if( pRoot == NULL || pNode1 == NULL || pNode2 == NULL) return NULL; vector < BTreeNode_t *> vec1;//用来保存从根节点到指定节点的遍历路径,前序遍历 vector <BTreeNode_t *> vec2; stack <BTreeNode_t *> st; bool findflag1 = false; bool findflag2 = false; BTreeNode_t *commonParent = NULL; while( pRoot != NULL || !st.empty() ){ while( pRoot != NULL ){ if( findflag1 == false){//没有找出所有的节点:从根节点到指定节点,在遍历时继续入栈 vec1.push_back( pRoot); if( pRoot == pNode1)//找到,则设置标志位 findflag1 = true; } if( findflag2 == false ){ vec1.push_back( pRoot); if( pRoot == pNode2 ) findflag2 = true; } if( findflag1 == true && findflag2 == true)//假设都已找到,则退出 break; st.push( pRoot); pRoot = pRoot->m_pLeft; } while( !st.empty()){ pRoot = st.top(); st.pop(); pRoot = pRoot->right; if( findflag1 == false )//没有找到所有路径节点时,就须要将错误路径节点退出 vec1.pop_back(); if( findflag2 == false ) vec2.pop_back(); } if( findflag1 == true && findflag2 == true)//假设都已找到,则退出 break; } if( findflag1 == true && findflag2 == true){//在两个遍历路径上查找最后一个同样的节点,就是最低公共祖先节点(近期公共父节点) vector< BTreeNode_t *> ::iterator iter1 = vec1.begin(); vector< BTreeNode_t *> ::iterator iter2 = vec2.begin(); while( iter1 != vec1.end() && iter2 != vec2.end() ){ if( *iter1 == *iter2) commonParent = *iter1; else break; ++iter1; ++iter2; } } vec1.clear(); vec2.clear(); st.clear(); return commonParent; }
</pre><pre>