二叉树的一些操作：
本文参考了何海涛老师的《剑指Offer——名企面试官精讲典型编程题》一书。
头文件：BinaryTree.h
/***********
BinaryTree.h
************/
struct BinaryTreeNode
{
char m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
//创建节点
BinaryTreeNode* CreateNode(char value);
//将pNode加到pRoot的左子树上
void AddLeft(BinaryTreeNode* pRoot,BinaryTreeNode* pNode);
//将pNode加到pRoot的右子树上
void AddRight(BinaryTreeNode* pRoot,BinaryTreeNode* pNode);
//打印节点的值
void Print(BinaryTreeNode* pNode);
//先序遍历
void DLR(BinaryTreeNode* pRoot,void(*func)(BinaryTreeNode* pNode));
//中序遍历
void LDR(BinaryTreeNode* pRoot,void(*func)(BinaryTreeNode* pNode));
//后序遍历
void LRD(BinaryTreeNode* pRoot,void(*func)(BinaryTreeNode* pNode));
//层次遍历
void CengCi(BinaryTreeNode* pRoot,void(*func)(BinaryTreeNode* pNode));
//根据先序序列preOrder,中序序列inOrder构建二叉树并返回根指针。
BinaryTreeNode* BuildTree(char preOrder[],char inOrder[],int len);
//二叉树的镜像
void MirrorTree(BinaryTreeNode** pHead);
//判断Root2是否是pRoot1的子树
bool DoesHasSubTree(BinaryTreeNode* pRoot1,BinaryTreeNode* pRoot2);
//返回二叉树的深度
int TreeDepth(BinaryTreeNode* pRoot);
//判断二叉树是否是平衡的二叉树
bool IsBlance(BinaryTreeNode* pRoot);
源文件：BinaryTree.cpp
#include <iostream>
#include <stdio.h>
#include <queue>
#include "BinaryTree.h"
using namespace std;
BinaryTreeNode* CreateNode(char value)
{
BinaryTreeNode* pNode = new BinaryTreeNode;
if(NULL == pNode)
return NULL;
pNode->m_nValue = value;
pNode->m_pLeft = NULL;
pNode->m_pRight = NULL;
return pNode;
}
void AddLeft(BinaryTreeNode* pRoot,BinaryTreeNode* pNode)
{
if(NULL == pRoot || NULL == pNode)
return;
if(NULL != pRoot->m_pLeft)
return;
else
pRoot->m_pLeft = pNode;
}
void AddRight(BinaryTreeNode* pRoot,BinaryTreeNode* pNode)
{
if(NULL == pRoot || NULL == pNode)
return;
if(NULL != pRoot->m_pRight)
return;
else
pRoot->m_pRight = pNode;
}
void Print(BinaryTreeNode* pNode)
{
if(NULL == pNode)
return;
else
printf("%c ",pNode->m_nValue);
}
void DLR(BinaryTreeNode* pRoot,void(*func)(BinaryTreeNode* pNode))
{
if(NULL == pRoot)
return;
func(pRoot);
DLR(pRoot->m_pLeft,func);
DLR(pRoot->m_pRight,func);
}
void LDR(BinaryTreeNode* pRoot,void(*func)(BinaryTreeNode* pNode))
{
if(NULL == pRoot)
return;
LDR(pRoot->m_pLeft,func);
func(pRoot);
LDR(pRoot->m_pRight,func);
}
void LRD(BinaryTreeNode* pRoot,void(*func)(BinaryTreeNode* pNode))
{
if(NULL == pRoot)
return;
LRD(pRoot->m_pLeft,func);
LRD(pRoot->m_pRight,func);
func(pRoot);
}
void CengCi(BinaryTreeNode* pRoot,void(*func)(BinaryTreeNode* pNode))
{
if(NULL == pRoot)
return;
queue<BinaryTreeNode*> queueNode;
BinaryTreeNode* BinTreeNode;
queueNode.push(pRoot);
while(!queueNode.empty())
{
BinTreeNode = queueNode.front();
func(BinTreeNode);
if(BinTreeNode->m_pLeft != NULL)
queueNode.push(BinTreeNode->m_pLeft);
if(BinTreeNode->m_pRight != NULL)
queueNode.push(BinTreeNode->m_pRight);
queueNode.pop();
}
}
BinaryTreeNode* BuildTree(char preOrder[],char inOrder[],int len)
{
if(NULL == preOrder || NULL == inOrder || len<=0)
return NULL;
BinaryTreeNode* pRoot = new BinaryTreeNode;
pRoot->m_nValue = preOrder[0];
pRoot->m_pLeft = pRoot->m_pRight = NULL;
if(1 == len)
return pRoot;
char tmp = preOrder[0];
int i = 0;
for(i=0; i<len; i++)
{
if(inOrder[i] == preOrder[0])
break;
}
int leftLen = i;
int rightLen = len - i - 1;
if(leftLen>0 && leftLen<len)
pRoot->m_pLeft = BuildTree(&preOrder[1],inOrder,leftLen);
if(rightLen>0 && rightLen<len)
pRoot->m_pRight = BuildTree(&preOrder[leftLen+1],&inOrder[leftLen+1],rightLen);
return pRoot;
}
void MirrorTree(BinaryTreeNode** pHead)
{
if(NULL == pHead || NULL == *pHead)
return;
BinaryTreeNode* pTmp;
pTmp = (*pHead)->m_pLeft;
(*pHead)->m_pLeft = (*pHead)->m_pRight;
(*pHead)->m_pRight = pTmp;
MirrorTree(&((*pHead)->m_pLeft));
MirrorTree(&((*pHead)->m_pRight));
}
bool DoesHasSubTree(BinaryTreeNode* pRoot1,BinaryTreeNode* pRoot2)
{
if(NULL == pRoot2)
return true;
if(NULL == pRoot1)
return false;
if(pRoot1->m_nValue != pRoot2->m_nValue)
return false;
return (DoesHasSubTree(pRoot1->m_pLeft,pRoot2->m_pLeft)&&DoesHasSubTree(pRoot1->m_pRight,pRoot2->m_pRight));
}
bool HasSubTree(BinaryTreeNode* pRoot1,BinaryTreeNode* pRoot2)
{
bool result = false;
if(NULL != pRoot1 && NULL != pRoot2)
{
if(pRoot1->m_nValue == pRoot2->m_nValue)
result = DoesHasSubTree(pRoot1,pRoot2);
if(!result)
result = HasSubTree(pRoot1->m_pLeft,pRoot2);
if(!result)
result = HasSubTree(pRoot1->m_pRight,pRoot2);
}
return result;
}
int TreeDepth(BinaryTreeNode* pRoot)
{
if(NULL == pRoot)
return 0;
int left = TreeDepth(pRoot->m_pLeft);
int right = TreeDepth(pRoot->m_pRight);
int max = left > right ? left:right;
return 1+max;
}
bool IsBlance(BinaryTreeNode* pRoot)
{
if(NULL == pRoot)
return true;
int left = TreeDepth(pRoot->m_pLeft);
int right = TreeDepth(pRoot->m_pRight);
int mins = left - right;
if(mins>1 || mins<-1)
return false;
else
return IsBlance(pRoot->m_pLeft) && IsBlance(pRoot->m_pRight);
}
主程序文件：main.cpp
#include <stdio.h>
#include <string>
#include <iostream>
#include "BinaryTree.h"
using namespace std;
int main()
{
BinaryTreeNode* pNode8 = CreateNode('8');
BinaryTreeNode* pNode6 = CreateNode('6');
BinaryTreeNode* pNode10 = CreateNode('0');
BinaryTreeNode* pNode5 = CreateNode('5');
BinaryTreeNode* pNode7 = CreateNode('7');
BinaryTreeNode* pNode9 = CreateNode('9');
BinaryTreeNode* pNode11 = CreateNode('1');
AddLeft(pNode8,pNode6);
AddRight(pNode8,pNode10);
AddLeft(pNode6,pNode5);
AddRight(pNode6,pNode7);
AddLeft(pNode10,pNode9);
AddRight(pNode10,pNode11);
int depth = TreeDepth(pNode8);
cout<<depth<<endl;
/*DLR(pNode8,Print);
printf("\n");
LDR(pNode8,Print);
printf("\n");
LRD(pNode8,Print);
printf("\n");
CengCi(pNode8,Print);
printf("\n");
MirrorTree(&pNode8);
DLR(pNode8,Print);
printf("\n");
LDR(pNode8,Print);
printf("\n");
LRD(pNode8,Print);
printf("\n");
CengCi(pNode8,Print);
printf("\n");*/
/*char preOrder[] = "12473568";
char inOrder[] = "47215386";
int len = strlen(preOrder);
BinaryTreeNode* pRoot = BuildTree2(preOrder,inOrder,len);
DLR(pRoot,Print);
printf("\n");
LDR(pRoot,Print);
printf("\n");
LRD(pRoot,Print);
printf("\n");
CengCi(pRoot,Print);
printf("\n");*/
return 0;
}