当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 树的四种递归遍历（C++读文件）

树的四种递归遍历（C++读文件）

2018年09月13日  | 移动技术网IT编程  | 我要评论

数码宝贝第3部国语,小魔星闯江湖,经典儿歌歌词

从“tree.in”文件里读取字符串，构造树，若遇到’0’，则认为是空树，然后对该树进行四种遍历

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define elemtype char

typedef struct treenode {
    struct treenode * lchild;
    struct treenode * rchild;
    elemtype data;
}treenode,* tree;

void createtree(tree & t, string str) {
    static int n = 0;
    if (str.length() <= n)
        return;
    elemtype ch = str[n++];
    if (ch == '0')
        t = null;
    else {
        t = (treenode*)malloc(sizeof(treenode));
        t->data = ch;
        createtree(t->lchild, str);
        createtree(t->rchild, str);
    }
}

//递归前中后序
void preorder(tree & t) {
    if (t) {
        std::cout << t->data<<" ";
        preorder(t->lchild);
        preorder(t->rchild);
    }
}
void inorder(tree & t) {
    if (t) {
        inorder(t->lchild);
        std::cout << t->data<<" ";
        inorder(t->rchild);
    }
}
void postorder(tree & t) {
    if (t) {
        postorder(t->lchild);
        postorder(t->rchild);
        std::cout << t->data<<" ";
    }
}
void levelorder(tree & t) {
    queue q;
    if (t) {
        q.push(t);
        while (!q.empty()) {
            tree temp = q.front();
            cout << temp->data << " ";
            q.pop();
            if (temp->lchild)
                q.push(temp->lchild);
            if (temp->rchild)
                q.push(temp->rchild);
        }
    }
}
int main() {
    ifstream ifs;
    ifs.open("tree.in");
    string str;
    ifs >> str;
    cout << str << endl;
    tree t;
    createtree(t, str);
    preorder(t);
    cout << endl;
    createtree(t, str);
    inorder(t);
    cout << endl;
    createtree(t, str);
    postorder(t);
    cout << endl;
    createtree(t, str);
    levelorder(t);
    cout << endl;
    ifs.close();
    system("pause");
    return exit_success;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网