二叉树基本操作 - c++编程基础

//BiTree.h

#ifndef BITREE_H
#define BITREE_H

#include 
#include 
#define ERROR -1 
#define OVERFLOW -2 
#define SUCCESS 0

#pragma pack(push)
#pragma pack(4)

struct _Node
{
	int iValue;
	struct _Node* pParent;
	struct _Node* pLChild;
	struct _Node* pRChild;
};

typedef struct _Node Node;

typedef struct
{
	Node* pRoot;//Root
	int iSize;
}BiTree;

#pragma pack(pop)


BiTree* InitTree();
Node* CreateNode( int iValue );
void ClearTree( BiTree** pTree );
void DestroyTree( BiTree** pTree );
int TreeEmpty( BiTree* pTree );
int GetTreeDepth( Node* pNode );
Node* GetRoot( BiTree* pTree );
void Assign( BiTree* pTree, Node* pNode, Node* pValue );
Node* GetParent( BiTree* pTree, Node* pNode );
Node* GetLeftChild( BiTree* pTree, Node* pNode );
Node* GetRightChild( BiTree* pTree, Node* pNode );
Node* GetLeftSibling( BiTree* pTree, Node* pNode );
Node* GetRightSibling( BiTree* pTree, Node* pNode );
void DeleteEntireNode( BiTree* pTree, Node** pNode );
void DeleteNode( BiTree* pTree, Node* pNode );
Node* AppendLeftChild( BiTree* pTree, Node* pNode, Node* pValue );
Node* AppendRightChild( BiTree* pTree, Node* pNode, Node* pValue );
void PrintNode( Node* pNode );
void PreTraverseTree( Node* pNode );
void MidTraverseTree( Node* pNode );
void PostTraverseTree( Node* pNode );
void Traverese( Node* pNode );
int GetTreeLeaves( Node* pNode );

#endif

//BitTree.cpp

#include "BiTree.h"


BiTree* InitTree()
{//初始化树
	BiTree* pTree = (BiTree*)malloc( sizeof( BiTree ) );

	if( !pTree )
		return NULL;

	pTree->iSize = 0;
	pTree->pRoot = NULL;

	return pTree;
}

Node* CreateNode( int iValue )
{
	Node* pNode = (Node*)malloc( sizeof( Node ) );

	if( !pNode )
		return NULL;

	pNode->pLChild = NULL;
	pNode->pRChild = NULL;
	pNode->pParent = NULL;

	pNode->iValue = iValue;

	return pNode;
}

void ClearTree( BiTree** pTree )
{//清空 树
	if( !(*pTree) )
		return;

	DeleteEntireNode( *pTree, &((*pTree)->pRoot) );

	(*pTree)->iSize = 0;

	(*pTree)->pRoot = NULL;

}

void DestroyTree( BiTree** pTree )
{//销毁树
	ClearTree( pTree );

	free( *pTree );
	*pTree = NULL;

}

int TreeEmpty( BiTree* pTree )
{//测试树是否为空
	if( !pTree || 0 == pTree->iSize )
		return 0;

	return pTree->iSize;
}

static int iMaxDepth = 0;
int GetTreeDepth( Node* pNode )
{//后序遍历树
	if( !pNode )
		return 0;

	GetTreeDepth( pNode->pLChild );
	GetTreeDepth( pNode->pRChild );
	
	Node* pCur = pNode;
	int iDepth = 0;
	while( pCur )
	{
		pCur = pCur->pParent;
		iDepth++;
	}

	if( iDepth > iMaxDepth )
		iMaxDepth = iDepth;

	return iMaxDepth;
}


Node* GetRoot( BiTree* pTree )
{//树的根
	if( !pTree )
		return NULL;

	return pTree->pRoot;
}

void Assign( BiTree* pTree, Node* pNode, Node* pValue )
{//给结点赋值
	if( !pTree || 0 == pTree->iSize || !pNode || !pValue )
		return;

	pNode->iValue = pValue->iValue;
}

Node* GetParent( BiTree* pTree, Node* pNode )
{//取结点的父结点
	if( !pTree || 0 == pTree->iSize || !pNode )
		return NULL;

	return pNode->pParent;
}

Node* GetLeftChild( BiTree* pTree, Node* pNode )
{//取结点pNode的最左端孩子
	if( !pTree || 0 == pTree->iSize || !pNode || !pNode->pLChild )
		return NULL;

	return pNode->pLChild;
}

Node* GetRightChild( BiTree* pTree, Node* pNode )

二叉树基本操作 (一)