二叉树代码(较全) (四)

if(tree != NULL)
{
leftDepth = 1;
leftDepth += CaculateDepth(tree->leftChild);

rightDepth = 1;
rightDepth += CaculateDepth(tree->rightChild);
}

return leftDepth > rightDepth leftDepth : rightDepth;
}

//******************************************************************************
// Name: CaculateWidth
// Desc: 计算二叉树的宽度
//******************************************************************************
int CaculateWidth(Node* tree)
{
if (tree == NULL)
{
return 0;
}

typedef list QueueNode;
QueueNode queue;
unsigned int width = 0;
queue.push_back(tree);

while (queue.size() > 0)
{
unsigned int size = queue.size();

for (unsigned int i = 0; i < size; ++i) // 上一层的节点全部出列,并压入下一层节点
{
Node* curNode = queue.front();
queue.pop_front();

if (curNode->leftChild != NULL)
{
queue.push_back(curNode->leftChild);
}

if (curNode->rightChild != NULL)
{
queue.push_back(curNode->rightChild);
}

}
width = max(width, size); // 与每一个size比较，取最大者
}

return width;
}

//******************************************************************************
// Name: Release
// Desc: 释放资源
//******************************************************************************
void Release(Node* tree)
{
if(tree != NULL)
{
Release(tree->leftChild);
Release(tree->rightChild);
delete tree;
tree = NULL;
}
}

int main()

{
// 数据输入
vector dataVec;
int tempValue;
cout<<"请输入二叉树的先序扩展序列(-1为空):"< while(cin>>tempValue)
{
dataVec.push_back(tempValue);
}

// 二叉树的创建
Node* root = NULL;
root = CreateTree(root, dataVec);

// 二叉显示
DisplayTree(root);

// 递归先根遍历
FirstVisite(root);
cout<

// 递归中根遍历
CenterVisite(root);
cout<

// 递归后根遍历
AfterVisite(root);
cout<

cout<<"----------------------------"<

// 非递归先根遍历
_FirstVisite(root);
cout<

// 非递归先根遍历二
__FirstVisite(root);
cout<

// 非递归中根遍历
_CenterVisite(root);
cout<

// 非递归中根遍历思路二
__CenterVisite(root);
cout<

// 非递归后根遍历
_AfterVisite(root);
cout<

// 非递归后根遍历思路二
__AfterVisite(root);
cout<

// 层次遍历
LevelVisite(root);
cout<

// 计算叶子节点数量
cout<

// 计算所有节点数量
cout<

// 计算二叉树深度
cout<

// 计算二叉树宽度
cout<

// 释放资源
Release(root);

system("pause");
return 0;
}