美文网首页
二叉树的基础+剑指offer32题

二叉树的基础+剑指offer32题

作者: 继续向前冲 | 来源:发表于2018-08-07 20:37 被阅读36次

    二叉树的简单创建 遍历等
    题目:不分行从上到下打印二叉树
    从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印,则一次打印出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;
    }
    

    相关文章

      网友评论

          本文标题:二叉树的基础+剑指offer32题

          本文链接:https://www.haomeiwen.com/subject/ztqzvftx.html