#include <iostream>
using namespace std;
//树的存储结构与设计
struct BitNode
{
int data;
BitNode* leftChild;
BitNode* rightChild;
BitNode()
{
leftChild = NULL;
rightChild = NULL;
}
BitNode(int x) :data(x), leftChild(NULL), rightChild(NULL)
{
}
};
//树的先序遍历
void PreOrder(BitNode* T)
{
if (T == NULL)
{
return;
}
cout << T->data;
PreOrder(T->leftChild);
PreOrder(T->rightChild);
return;
}
//树的中序遍历
void InOrder(BitNode* T)
{
if (T == NULL)
{
return;
}
InOrder(T->leftChild);
cout << T->data;
InOrder(T->rightChild);
return;
}
//树的后序遍历
void PostOrder(BitNode* T)
{
if (T == NULL)
{
return;
}
PostOrder(T->leftChild);
PostOrder(T->rightChild);
cout << T->data;
}
//求树的叶子结点个数
int sum = ;
int CountLeafNum(BitNode* T)
{
if (T == NULL)
{
return ;
}
if (T->leftChild == NULL && T->rightChild == NULL)
{
sum++;
}
CountLeafNum(T->leftChild);
CountLeafNum(T->rightChild);
return sum;
}
//求树的叶子结点个数-两个参数
void CountLeafNum(BitNode* T, int* sum)
{
if (T == NULL)
{
return;
}
if (T->leftChild == NULL && T->rightChild == NULL)
{
*sum = *sum + ; //等价于(*sum)++
}
CountLeafNum(T->leftChild, sum);
CountLeafNum(T->rightChild, sum);
}
//求树的深度
int DepthOfTree(BitNode* T)
{
int depthLeft = ;
int depthRight = ;
int depth = ;
if (T == NULL)
return ;
depthLeft = DepthOfTree(T->leftChild);
depthRight = DepthOfTree(T->rightChild);
depth = + ((depthLeft >depthRight)? depthLeft : depthRight);
return depth;
}
//复制二叉树--用递归的思想，必须先根据返回值，定义新的变量类型用于递归的返回值赋值
BitNode* Copy(BitNode* T)
{
if (T == NULL)
{
return NULL;
}
//用的前序遍历思想
BitNode* newTreeLeft = Copy(T->leftChild);
BitNode* newTreeRight = Copy(T->rightChild);
//建立一个结点
BitNode* newNode = new BitNode();
if (newNode == NULL)
{
return NULL;
}
newNode->data = T->data;
newNode->leftChild = newTreeLeft;
newNode->rightChild = newTreeRight;
return newNode;
}
int main()
{
BitNode nodeA();
BitNode nodeB();
BitNode nodeC();
BitNode nodeD();
BitNode nodeE();
BitNode nodeF();
nodeA.leftChild = &nodeB;
nodeA.rightChild = &nodeC;
nodeB.leftChild = &nodeD;
nodeB.rightChild = &nodeE;
nodeC.leftChild = &nodeF;
//前序遍历二叉树
cout << "前序遍历二叉树 " << ":";
PreOrder(&nodeA);
cout << endl;
//中序遍历二叉树
cout << "中序遍历二叉树 " << ":";
InOrder(&nodeA);
cout << endl;
//后序遍历二叉树
cout << "后序遍历二叉树 " << ":";
PostOrder(&nodeA);
cout << endl;
//树的结点个数
int leafCount = CountLeafNum(&nodeA);
cout << "树的结点个数:" << leafCount << endl;
//树的深度
int depth = DepthOfTree(&nodeA);
cout << "树的深度:" << depth << endl;
//赋值一棵树
BitNode* newNode = Copy(&nodeA);
//后序遍历二叉树
cout << "后序遍历二叉树 " << ":";
PostOrder(newNode);
cout << endl;
system("pause");
return ;
}