二叉树的基础+剑指offer32题

二叉树的简单创建 遍历等
题目：不分行从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印，则一次打印出8,6,10,5,7,9,11

//
//  NewTree.hpp
//  二叉树的基本
//
//  Created by 张传奇 on 2018/8/7.
//  Copyright © 2018年 张传奇. All rights reserved.
//

#ifndef NewTree_hpp
#define NewTree_hpp

#include <stdio.h>
#include <iostream>
using namespace std;

class NewNode {
public:
    char data;
    NewNode * lchild, * rchild;
};

class NewTree {
private:
    NewNode * root;
    int height;
    void pre_Order(NewNode * t);
    void in_Order(NewNode * t);
    void post_Order(NewNode * t);
    NewNode * create(string &s,int &pos);
public:
    NewTree(){root = nullptr;height = 0;};
    ///按照前序遍历序列创建二叉树
    void createBiTree(string s);
    ///前序遍历二叉树
    void preOrder();
    ///中序遍历二叉树
    void inOrder();
    ///后序遍历二叉树(递归方法)
    void postOrder();
    ///后序遍历二叉树(使用栈的非递归方法)
    void postOrder1();
    ///层序遍历二叉树
    void levelOrder();
    ///求树的高度
    int getHeight();
    void get_Height(NewNode *t,int h);
    
};



#endif /* NewTree_hpp */

//
//  NewTree.cpp
//  二叉树的基本
//
//  Created by 张传奇 on 2018/8/7.
//  Copyright © 2018年 张传奇. All rights reserved.
//

#include "NewTree.hpp"
#include <iostream>
#include "stack"
#include "queue"

using namespace std;

NewNode * NewTree::create(string &s, int &pos) {
    ++ pos;
    NewNode * t;
    if ((unsigned) pos >= s.size()) {
        return nullptr;
    }else
    {
        if (s[pos] == '#') {
            t = nullptr;
        }
        else
        {
            t = new NewNode;
            t->data = s[pos];
            t->lchild = create(s, pos);
            t->rchild = create(s, pos);
        }
        return t;
    }
}

void NewTree::createBiTree(std::string s) {
    int pos = -1;
    root = create(s, pos);
}

void NewTree::preOrder() {
    pre_Order(root);
    cout<<endl;
}
void NewTree::pre_Order(NewNode *t){
    if (t != nullptr) {
        cout<<t->data<<" ";
        pre_Order(t->lchild);
        pre_Order(t->rchild);
    }
}
void NewTree::inOrder() {
    in_Order(root);
       cout<<endl;
}
void NewTree::in_Order(NewNode *t) {
    if (t != nullptr) {
        in_Order(t->lchild);
        cout<<t->data<<" ";
        in_Order(t->rchild);
    }
 
}

void NewTree::postOrder() {
    
    post_Order(root);
    cout<<endl;
}

void NewTree::post_Order(NewNode *t) {
    if (t != nullptr) {
        post_Order(t->lchild);
        post_Order(t->rchild);
        cout<<t->data<<" ";
    }
}


void NewTree::postOrder1() {
    
    NewNode *p,*r;
    r = nullptr;
    p = root;
    
    stack<NewNode *> my_stack;
    while (p != nullptr || !my_stack.empty()) {
        if (p) {
            //把左子树 便利完了
            my_stack.push(p);
            p = p->lchild;
        
        }
        else
        {
            //栈顶元素
            p = my_stack.top();
            
            if (p->rchild != nullptr && p->rchild != r) {
                //先便利右子树，再便利右子树的左子树
                p = p->rchild;
                my_stack.push(p);
                p = p->lchild;
            }
            else
            {
//                左面便利完了，右面也便利完了，该根节点了
                p = my_stack.top();
                my_stack.pop();
                cout<<p->data<<" ";
                                ///更新最近遍历的节点
                r = p;
                        ///将遍历后的节点设为NULL，进行下一个节点的遍历
                p = nullptr;
            }
            
        }
    }
    
    cout<<endl;
    
}

void NewTree::levelOrder() {
    if (root == nullptr) {
        return;
    }
    
    queue<NewNode *> my_queue;
    my_queue.push(root);
    while (!my_queue.empty()) {
        NewNode * t;
        t = my_queue.front();
        my_queue.pop();
        cout<<t->data<<" ";
        if (t->lchild != nullptr) {
            my_queue.push(t->lchild);
        }
        if (t->rchild != nullptr) {
            my_queue.push(t->rchild);
        }
    }
    cout<<endl;
}

int NewTree::getHeight() {
    get_Height(root,0);
    return height;
}

void NewTree::get_Height(NewNode *t, int h) {
    if (t != nullptr) {
        ++ h;
        if (h> height) {
            height = h;
            get_Height(t->lchild, h);
            get_Height(t->rchild, h);
        }
    }
}

/**
 前序遍历 非递归版本
 */
void BiTree::preOrder1() {
    stack<BigNode *>my_stack;
    my_stack.push(root);
    BigNode * p;
    
    while (!my_stack.empty()) {
        
        p = my_stack.top();
        my_stack.pop();
        
        if (p != nullptr) {
            cout<<p->data<<" ";
            if (p->rchild != nullptr) {
                my_stack.push(p->rchild);
            }
            if (p->lchild != nullptr) {
                my_stack.push(p->lchild);
            }
        }
    }
    
    cout<<endl;
}

/**
 中序遍历非递归版本
 */
void BiTree::inOrder1() {
    stack<BigNode *> my_stack;
    BigNode * p = root;
    
    do {
        while (p != nullptr) {
            my_stack.push(p);
            p = p->lchild;
        }
        p = my_stack.top();
        my_stack.pop();
        
        cout<<p->data<<" ";
        
        if (p->rchild != nullptr) {
            p = p->rchild;
        }else
        {
            p = nullptr;
        }
        
    } while (p != nullptr || !my_stack.empty());
    cout<<endl;
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";
    
    NewTree a;
    string s;
    s="ABD##E#F##C##";

    a.createBiTree(s);
    cout<<"前序遍历："<<endl;
    a.preOrder();

    cout<<"中序遍历："<<endl;
    a.inOrder();
//
    cout<<"后序遍历1："<<endl;
    a.postOrder();
    cout<<"后序遍历2："<<endl;
    a.postOrder1();
    cout<<"层序遍历："<<endl;
    a.levelOrder();
    cout<<"树高："<<endl;
    cout<<a.getHeight()<<endl;
    return 0;
}