前言
在前面的二叉树讲解中，使用了非递归的方式遍历二叉树基本上都是使用栈来辅助。
二叉树的遍历（非递归）
【点此查看】
二叉树的层序遍历
二叉树如图所示：
请按照层序遍历
方法
层序遍历就不能借助栈了，但可以借助队列。
初始状态
将队头结点出队并打印该结点的值，并看该结点有没有左右子树，有就入队列
循环，继续出队，直到队列为NULL
代码
void LevelOrder(BtNode* ptr)
{
if (nullptr == ptr) return;
queue<BtNode*> qu;
qu.push(ptr);
while (!qu.empty())
{
ptr = qu.front(); qu.pop();
cout << ptr->data << " ";
if (ptr->leftchild != nullptr)
qu.push(ptr->leftchild);
if (ptr->rightchild != nullptr)
qu.push(ptr->rightchild);
}
cout << endl;
}
示例：
计算二叉树结点个数
代码
二叉树结点个数就是左子树加右子树加自身根节点。
那么使用递归就很好写：
int Count(BtNode* ptr)
{
if (ptr == nullptr) return 0;
else return Count(ptr->leftchild) + Count(ptr->rightchild) + 1;
}
计算二叉树的深度
代码
递归判断左子树和右子树哪个高度高，再加一后，就是二叉树深度
// 深度
int Depth(BtNode* ptr)
{
if (ptr == nullptr) return 0;
else return std::max(Depth(ptr->leftchild), Depth(ptr->rightchild)) + 1;
}
运行示例：
cout << "count = " << Count(root) << endl;
cout << "Depth = " << Depth(root) << endl;
二叉树的锯齿形层序遍历
遍历规则如图
方法
利用两个栈a和b，先将根节点入栈a，如果根节点有左右子树，就将左右子树入到b栈中
初始状态:
将入到a栈的结点出栈，并从左向右将子树入到b栈
那么到下一行时，就出b栈的结点，从右向左入栈它的子树。
以此类推
代码
void ZLevelOrder(BtNode* ptr)
{
if (ptr == nullptr) return;
stack<BtNode*> ast;
stack<BtNode*> bst;
ast.push(ptr);
while (!ast.empty() || !bst.empty())
{
while (!ast.empty())
{
ptr = ast.top(); ast.pop();
cout << ptr->data << " ";
if (ptr->leftchild != nullptr)
{
bst.push(ptr->leftchild);
}
if (ptr->rightchild != nullptr)
{
bst.push(ptr->rightchild);
}
}
while (!bst.empty())
{
ptr = bst.top(); bst.pop();
cout << ptr->data << " ";
if (ptr->rightchild != nullptr)
{
ast.push(ptr->rightchild);
}
if (ptr->leftchild != nullptr)
{
ast.push(ptr->leftchild);
}
}
}
cout << endl;
}
运行示例：
cout << "count = " << Count(root) << endl;
cout << "Depth = " << Depth(root) << endl;
ZLevelOrder(root);
二叉树判满
代码
利用栈的话很好控制，变量s是每一层的节点个数，如果每层入队的节点数和s不同，就说明不是满二叉树。
bool isFull(BtNode* ptr)
{
bool tag = true;
if (ptr == nullptr) return tag;
queue<BtNode*> aqu;
queue<BtNode*> bqu;
int s = 1;
aqu.push(ptr);
while (!aqu.empty() || !bqu.empty())
{
if (s != aqu.size())
{
tag = false;
break;
}
while (!aqu.empty())
{
ptr = aqu.front(); aqu.pop();
if (ptr->leftchild != nullptr) bqu.push(ptr->leftchild);
if (ptr->rightchild != nullptr) bqu.push(ptr->rightchild);
}
s += s;
if (s != bqu.size())
{
tag = false;
break;
}
while (!bqu.empty())
{
ptr = bqu.front(); bqu.pop();
if (ptr->leftchild != nullptr) aqu.push(ptr->leftchild);
if (ptr->rightchild != nullptr) aqu.push(ptr->rightchild);
}
s += s;
}
return tag;
}
运行示例：
对于上面的例子，这个二叉树不是满二叉树
cout << "This tree is a full Tree ? " << (isFull(root) ? "Yes." : "No" )<< endl;
