二叉树基本操作 (二)
{//取结点pNode的最右端孩子
if( !pTree || pTree->iSize == 0 || !pNode->pRChild )
return NULL;
return pNode->pRChild;
}
Node* GetLeftSibling( BiTree* pTree, Node* pNode )
{//pNode的左侧兄弟
if( !pTree || 0 == pTree->iSize || !pNode )
return NULL;
Node* pParent = GetParent( pTree, pNode );
if( !pParent )
return NULL;
return pParent->pLChild;
}
Node* GetRightSibling( BiTree* pTree, Node* pNode )
{//pNode的右侧兄弟
if( !pTree || pTree->iSize == 0 || !pNode )
return NULL;
Node* pParent = GetParent( pTree, pNode );
if( !pParent )
return NULL;
return pNode->pRChild;
}
void DeleteEntireNode( BiTree* pTree, Node** pNode )
{//LRM 后序
if( !pTree || !(*pNode) )
return;
if( (*pNode) && (*pNode)->pLChild )
{
DeleteEntireNode( pTree, &((*pNode)->pLChild) );
(*pNode)->pLChild = NULL;
}
if( (*pNode) && (*pNode)->pRChild )
{
DeleteEntireNode( pTree, &((*pNode)->pRChild) );
(*pNode)->pRChild = NULL;
}
Node* pParent = GetParent( pTree, *pNode );
if( pParent )
{
if( pParent->pLChild == (*pNode) )
{
pParent->pLChild = NULL;
}
else if( pParent->pRChild == (*pNode) )
{
pParent->pRChild = NULL;
}
}
delete (*pNode);
(*pNode) = NULL;
pTree->iSize--;
}
void DeleteNode( BiTree* pTree, Node* pNode )
{//删除pNode结点
if( !pTree || !pTree->iSize || !pNode )
return;
DeleteEntireNode( pTree, &pNode );
}
Node* AppendLeftChild( BiTree* pTree, Node* pNode, Node* pValue )
{//追加孩子结点
if( !pTree || !pNode || !pValue )
return NULL;
if( pNode->pLChild )
return NULL;
pNode->pLChild = pValue;
pValue->pParent = pNode;
pValue->pLChild = NULL;
pValue->pRChild = NULL;
pTree->iSize++;
return pValue;
}
Node* AppendRightChild( BiTree* pTree, Node* pNode, Node* pValue )
{//追加孩子结点
if( !pTree || !pNode || !pValue )
return NULL;
if( pNode->pRChild )
return NULL;
pNode->pRChild = pValue;
pValue->pParent = pNode;
pValue->pLChild = NULL;
pValue->pRChild = NULL;
pTree->iSize++;
return pValue;
}
void PrintNode( Node* pNode )
{//输出结点
if( pNode )
printf( "%d ", pNode->iValue );
}
void PreTraverseTree( Node* pNode )
{//前序遍历树
if( !pNode )
return;
PrintNode( pNode );//根
PreTraverseTree( pNode->pLChild );
PreTraverseTree( pNode->pRChild );
}
void MidTraverseTree( Node* pNode )
{
if( !pNode )
return;
MidTraverseTree( pNode->pLChild );
PrintNode( pNode );
MidTraverseTree( pNode->pRChild );
}
void PostTraverseTree( Node* pNode )
{//后序遍历树
if( !pNode )
return;
PostTraverseTree( pNode->pLChild );
PostTraverseTree( pNode->pRChild );
PrintNode( pNode );
}
void Traverese( Node* pNode )
{
if( !pNode )
return;
puts( "Pre" );
PreTraverseTree( pNode );
puts( "" );
puts( "Mid" );
MidTraverseTree( pNode );
puts( "" );
puts( "Post" );
PostTraverseTree( pNode );
puts( "" );
}
int GetTreeLeaves( Node* pNode )
{
if( !pNode )
return 0;
if( !pNode->pLChild && !pNode->pRChild )
return 1;
return GetTreeLeaves( pNode->pLChild ) + GetTreeLeaves( pNode->pRChild );
}
int main( int argc, char* argv[] )
{
BiTree* pTree = InitTree();
pTree->pRoot = CreateNode( 0 );
Node* pLeft = AppendLeft