本篇接着上一篇:第一篇。
在上一篇的最后实现了输入操作，在本篇实现一般二叉树的层序遍历、之字形遍历和二叉搜索树的前中后序遍历。
文章目录一、类的声明二、代码实现
2.1输出
2.1.1层序遍历2.1.2与真实形状更加接近的输出
2.2 其他各种遍历
2.2.1前序遍历2.2.2中序遍历2.2.3后序遍历2.2.4之字形遍历
一、类的声明class BinaryTree {
friend ostream& operator<<(ostream& out, const BinaryTree& right);//层序遍历
private:
class Node {//节点定义
public:
int value;
Node* left;//左子女
Node* right;//右子女
Node(int newval, Node* l = NULL, Node* r = NULL) :
value(newval), left(l), right(r) {};
};
Node* root;//根节点
//辅助函数
Node* ConstructAux(Node* cursubroot, Node* orgsubroot);//递归实现复制构造时的辅助函数
void GraphAux(Node* subroot, int indent) const;//实现二叉树形象输出的辅助函数
void PreAux(Node* subroot) const;//前序遍历的辅助函数
void InAux(Node* subroot) const;//中序遍历的辅助函数
void PostAux(Node* subroot) const;//后序遍历的辅助函数
public:
BinaryTree() : root(NULL) {};//默认构造
BinaryTree(const BinaryTree& origin);//复制构造
~BinaryTree();//析构
void CompleteBinaryTree();//输入完全树
void BinarySearchTree();//输入二叉搜索树
bool empty() const;//判空
void add(int newdata);//按完全树的规则添加元素
void insert(int newdata);//按二叉搜索树的规则添加元素
void graph() const;//形象输出二叉树
void preorder() const;//前序遍历
void inorder() const;//中序遍历
void postorder() const;//后序遍历
void z() const;//之字形遍历
};
声明与第一篇的不同点：
添加了在输出运算符 << 的重载中实现的层序遍历。添加了形象地输出二叉树的graph()函数。添加了二叉搜索树的前序preorder()、中序inroder()、后序postorder()遍历函数。
其他完全一致。
辅助函数为帮助实现功能的函数。
二、代码实现 2.1输出 2.1.1层序遍历在 << 重载实现了层序遍历的输出，即从上到下从左到右地输出二叉树，主要利用了队列。
ostream& operator<<(ostream& out, const BinaryTree& right)
{
queue q;
q.push(right.root);
while (!q.empty())
{
int curnumber = q.size();//当前层元素个数
for (int i = 0; i < curnumber; i++)//打印当前层
{
BinaryTree::Node* f = q.front();
if (f->left != NULL) q.push(f->left);//如果子女不空，就放入队列等待打印
if (f->right != NULL) q.push(f->right);
out << f->value << " ";//打印
q.pop();//弹出遍历过的元素
}
out << endl;
}
return out;
}
测试：
使用上一篇实现的CompleteBinaryTree()输入完全树：
使用BinarySearchTree()输入二叉搜索树：
从测试可以看到我们实现了数据的按行输出，把处于同一行的元素从左到右输出。
但是我们没有考虑二叉树的结构，没有使数据居中，也没有考虑空节点，从测试的输出中无法直观地看出谁是谁的子女。
2.1.2与真实形状更加接近的输出在2.1.1中实现的输出与实际二叉树的形状不太像：如果二叉树中有空节点，我们应该打印空格表示这个空位，除此之外，在每行开始应该打印空格使数据居中。
优化2.1.1的代码以达到效果是很麻烦的，因为我们不知道一个一般的二叉树的层数，那么居中输出问题就不好解决，同时节点中数据的位数也会影响输出的形状，不妨换一个思路。
为了输出形状更像的二叉树，看下面的例子。
有一个二叉树：
如果我们可以侧着把它输出在屏幕：
每一列表示树的一层，节点的右子女在右上方，左子女在右下方，这样居中和空位的问题就好解决了，因为各数据在不同行。
为了实现这个功能，我们使用递归的方法。
void BinaryTree::graph() const
{
if(!empty())GraphAux(root,0);
}
void BinaryTree::GraphAux(Node* subroot,int indent)const//indent为缩进的格数
{
if (subroot->right != NULL) GraphAux(subroot->right,indent + 4);
cout << setw(indent) << subroot->value << endl;
if (subroot->left != NULL) GraphAux(subroot->left,indent + 4);
}
graph()函数实现输出功能，为了透明化（不在使用时输入指针）,我们用GraphAux()实现功能，graph()封装。
Graph()按顺序实现：1.输出右子女 2.输出当前节点数据 3.输出左子女。
注意：通过设置缩进indent来表示各节点位于不同的列。
测试：
1.完全二叉树：
2.二叉搜索树：
2.2 其他各种遍历 2.2.1前序遍历void BinaryTree::preorder() const//前序遍历
{
PreAux(root);
}
void BinaryTree::PreAux(Node* subroot) const//辅助函数
{
if (subroot != NULL) {//如果subroot不为空，那么就要打印以subroot为根的这个树
cout << subroot->value << " ";//打印根数据
PreAux(subroot->left);//打印左子树
PreAux(subroot->right);//打印右子树
}
}
2.2.2中序遍历
与前序遍历相比仅改变了输出数据的顺序。
void BinaryTree::inorder() const//中序遍历
{
InAux(root);
}
void BinaryTree::InAux(Node* subroot) const
{
if (subroot != NULL) {
InAux(subroot->left);
cout << subroot->value << " ";
InAux(subroot->right);
}
}
2.2.3后序遍历
void BinaryTree::postorder() const
{
PostAux(root);
}
void BinaryTree::PostAux(Node* subroot) const
{
if (subroot != NULL) {
PostAux(subroot->left);
PostAux(subroot->right);
cout << subroot->value << " ";
}
}
2.2.4之字形遍历
之字形遍历按奇数层从左到右顺序输出，偶数层从右到左顺序输出（层数从1开始）。
我们使用双端队列deque实现功能（也可以用两个队列queue分别存放奇数层和偶数层节点，像上面的层序遍历一样操作），在奇数层从队头删除遍历过的节点N，从队尾加入节点N非空子女（先左后右），而在偶数层从队尾删除遍历过的节点，从队头加入非空子女（先右后左），这样就可以保证遍历顺序的正确。
void BinaryTree::z() const
{
if (!empty())
{
deque d;
d.push_back(root);
bool floor = true;//true为奇数层，false为偶数层
while (!d.empty())
{
int curnumber = d.size();//当前层元素个数
for (int i = 0; i < curnumber; i++)//遍历当前层
{
if (floor)//当前为奇数层
{
Node* f = d.front();
if (f->left != NULL) d.push_back(f->left);//从尾加入元素
if (f->right != NULL) d.push_back(f->right);
cout << f->value << " ";
d.pop_front();//从头弹出元素
}
else {
Node* b = d.back();
if (b->right != NULL) d.push_front(b->right);//从头加入元素
if (b->left != NULL) d.push_front(b->left);
cout << b->value << " ";
d.pop_back();//从尾弹出元素
}
}
cout << endl;
floor = !floor;//层数奇偶性改变
}
}
}
