D-oj|二叉树的基本操作 题目编号:462

**

设计二叉树类，能够对二叉树进行先序、中序、后序和层序遍历，遍历的操作为输出结点的值，设计主函数，输入一棵二叉树，按先序、中序、后序、层序的遍历顺序输出结点的值。二叉树的结点数不超过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

层序：

思路：
层序中head用来输出指针数组的头部，调用节点个数作为指针数组遍历的上限，将二叉树中所有的左右子树的指针依次加入数组中，然后每次输出数组中的第一个指针的data，相当于模拟队列。

void BiTree::cx(BiNode *bt,BiNode*a[],int i,int c) {
    if(head==c)return;
    else{
    cout<<bt->data<<" ";
    if(bt->lchild!=NULL)a[i++]=bt->lchild;
    if(bt->rchild!=NULL)a[i++]=bt->rchild;
    bt=a[head++];
    cx(bt,a,i,c);
    }}

完整代码

#include <iostream>
using namespace std;
struct BiNode{
    int data;
    BiNode *lchild;
    BiNode *rchild;
};
class BiTree{
public:
    BiTree(){root=Creat();head=0;}
    ~BiTree(){Release(root);}
    int Getnum(){return Getnum(root);};
    void qx(){ qx(root);}
    void zx(){ zx(root);}
    void hx(){ hx(root);}
    void cx(BiNode*b[],int c){
        cx(root, b,0,c);}
private:
    int head;
    BiNode *root;
    BiNode *Creat();
    void Release(BiNode *bt);
    int Getnum(BiNode*bt);
    void qx(BiNode*bt);
    void zx(BiNode*bt);
    void hx(BiNode*bt);
    void cx(BiNode*bt,BiNode*a[],int i,int c);
};
void BiTree::qx(BiNode *bt) {
    if(bt==NULL)return;
    else{
        cout<<bt->data<<" ";
        qx(bt->lchild);
        qx(bt->rchild);
    }
}
void BiTree::zx(BiNode*bt) {
    if(bt==NULL)return;
    else{
        zx(bt->lchild);
        cout<<bt->data<<" ";
        zx(bt->rchild);
    }
}
void BiTree::hx(BiNode *bt) {
    if(bt==NULL)return;
    else{
        hx(bt->lchild);
        hx(bt->rchild);
        cout<<bt->data<<" ";
    }
}
void BiTree::cx(BiNode *bt,BiNode*a[],int i,int c) {
    if(head==c)return;
    else{
    cout<<bt->data<<" ";
    if(bt->lchild!=NULL)a[i++]=bt->lchild;
    if(bt->rchild!=NULL)a[i++]=bt->rchild;
    bt=a[head++];
    cx(bt,a,i,c);
    }}
int BiTree::Getnum(BiNode*bt){
    if(bt==NULL)return 0;
    int lNum;
    int rNum;
    lNum=Getnum(bt->lchild);
    rNum= Getnum(bt->rchild);
    return 1+lNum+rNum;
}
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){
        Release(bt->lchild);
        Release(bt->rchild);
        delete bt;
    }
}
int main()
{
    BiTree A;
    int c=A.Getnum();
    BiNode*b[c];
    A.qx();
   // cout<<endl;
    A.zx();
    //cout<<endl;
    A.hx();
    //cout<<endl;
    A.cx(b,c);
}