本文共 4051 字，大约阅读时间需要 13 分钟。

问题分析

设计二叉树类，能够对二叉树进行先序、中序、后序和层序遍历，遍历的操作为输出结点的值。主函数输入一棵二叉树，按先序、中序、后序、层序的遍历顺序输出结点的值。

代码

        
问题描述
    
设计二叉树类，能够对二叉树进行先序、中序、后序和层序遍历，遍历的操作为输出结点的值。主函数输入一棵二叉树，按先序、中序、后序、层序的遍历顺序输出结点的值。二叉树的结点数不超过20。
        
   
            输入数据只有一组，二叉树的结点均为一个数字，数据为0代表当前结点为空。输入结点的值按照二叉树的先序遍历顺序，例如输入：
    
                 1 2 4 0 0 5 0 0 3 0 6 0 0        
    
        0表示空，输入的数字之间由空格分隔。上述输入对应的二叉树如下图所示：    
   
    
输出描述
    
输出先序、中序、后序和层序遍历二叉树得到的序列，各占一行，同一行的数字之间由空格分隔。
    
   
            输入样例：
    
                 1 2 4 0 0 5 0 0 3 0 6 0 0        
    
        输出样例：
    
                 1 2 4 5 3 6            4 2 5 1 3 6            4 5 2 6 3 1            1 2 3 4 5 6        
    
    
   
    
代码
    
        #include 
    
             using namespace std;        struct BiNode {            int data;            BiNode *lchild, *rchild;        };        class BiTree {            public:                BiTree() {                    root = Creat();                }                ~BiTree() {                    Release(root);                }                void PreOrder() {                    PreOrder(root);                }                void InOrder() {                    InOrder(root);                }                void PostOrder() {                    PostOrder(root);                }                void LevelOrder() {                    LevelOrder(root);                }            private:                BiNode *Creat();                void Release(BiNode *bt);                void PreOrder(BiNode *bt) {                    if (bt != NULL) {                        cout << bt->data << " ";                        PreOrder(bt->lchild);                        PreOrder(bt->rchild);                    }                }                void InOrder(BiNode *bt) {                    if (bt != NULL) {                        InOrder(bt->lchild);                        cout << bt->data << " ";                        InOrder(bt->rchild);                    }                }                void PostOrder(BiNode *bt) {                    if (bt != NULL) {                        PostOrder(bt->lchild);                        PostOrder(bt->rchild);                        cout << bt->data << " ";                    }                }                void LevelOrder(BiNode *bt) {                    if (bt == NULL) {                        return;                    }                    queue
     
       q;                    q.push(bt->data);                    while (!q.empty()) {                        int current = q.front();                        q.pop();                        if (current == 0) {                            continue;                        }                        cout << current << " ";                        int left = current * 2 - 1;                        if (left >= 1 && left <= 20) {                            q.push(left);                        }                        int right = current * 2;                        if (right >= 1 && right <= 20) {                            q.push(right);                        }                    }                }                BiNode *root;        };        BiNode *BiTree::Creat() {            BiNode *bt;            int ch;            cin >> ch;            if (ch == 0) {                bt = NULL;            } else {                bt = new BiNode;                bt->data = ch;                bt->lchild = Creat();                bt->rchild = Creat();            }            return bt;        }        void BiTree::Release(BiNode *bt) {            if (bt == NULL) {                return;            } else {                Release(bt->lchild);                Release(bt->rchild);                delete bt;            }        }        int main() {            BiTree B;            B.PreOrder();            cout << endl;            B.InOrder();            cout << endl;            B.PostOrder();            cout << endl;            B.LevelOrder();            return 0;        }    
     
    

输出结果

先序遍历输出：

1 2 4 5 3 6

中序遍历输出：

4 2 5 1 3 6

后序遍历输出：

4 5 2 6 3 1

层序遍历输出：

1 2 3 4 5 6