论坛 › 数据结构与算法 › 求大神帮忙解决

kykio 发表于 2018-5-2 20:49:30

求大神帮忙解决

这个程序太困难了，求大神帮忙解决！
以下问题要求统一在一个大程序里解决。
按先序遍历的扩展序列建立二叉树的存储结构
二叉树先序、中序、后序遍历的递归算法
二叉树中序遍历的非递归算法
二叉树层次遍历的非递归算法
求二叉树的深度(后序遍历)
建立树的存储结构
求树的深度

溯影 发表于 2018-5-5 10:05:38

二叉树的那个帖子我想回复你但是不知道为什么我的帖子没有办法发出去。。。。。
层次遍历要用到队列，非递归中序遍历要用到栈
我用宏定义引用了上面的顺序队列和顺序栈的模板
主程序：
#include <iostream>
#include <assert.h>
#include <cstdbool>
using namespace std;

//宏定义，嵌入队列文件模板
#ifndef SQQUEUE_H
#define SQQUEUE_H
#include "C:\Users\pc\Desktop\ConsoleApplication1\ConsoleApplication1\SqQueue.cpp"
#endif

//宏定义，嵌入顺序栈文件模板
#ifndef SQSTACK_H
#define SQSTACK_H
#include "C:\Users\pc\Desktop\ConsoleApplication1\ConsoleApplication1\SqStack.cpp"
#endif


template <typename elemtype>
class BiTree{
public:
        class Node{
        public:
                Node *left;                //指向左结点
                Node *right;        //指向右结点
                elemtype data;        //数据域

                Node(){                        //构造函数
                        left = NULL;
                        right = NULL;
                }
        };

        typedef Node* NodePointer;

protected:
        NodePointer root;        //根节点

public:
        BiTree(){                        //二叉树构造函数
                root = NULL;
        }

        void createBiTree();
        void createBiTree_aux(NodePointer &p);                        //创建二叉树辅助函数
        void preOrderTraverse();                                                //前序递归遍历二叉树
        void preOrderTraverse_aux(NodePointer p);                //前序递归遍历二叉树辅助函数

        void inOrderTraverse();                                                        //中序递归遍历二叉树
        void inOrderTraverse_aux(NodePointer p);                //中序递归遍历二叉树辅助函数

        void postOrderTraverse();                                                //后序递归遍历二叉树
        void postOrderTraverse_aux(NodePointer p);                //后序递归遍历二叉树辅助函数

        int depth();                                                                        //求二叉树深度
        int depth_aux(NodePointer p);                                        //求二叉树深度的辅助函数


        void layOrderTraverse();                                                //按层次顺序遍历二叉树

        void noRecursionInOrderTraverse();                                //非递归中序遍历二叉树

};

//创建二叉树
template <typename elemtype>
void BiTree<elemtype>::createBiTree(){
        createBiTree_aux(root);
}

//创建二叉树辅助函数
template <typename elemtype>
void BiTree<elemtype>::createBiTree_aux(NodePointer &p){
        elemtype value;
        cout << "请输入数据域的值，输入0时代表叶子的生成:";
        cin >> value;
        if (value == 0){
                p = NULL;
        }
        else{
                p = new Node;
                assert(p != 0);
                p->data = value;                        //先序创建二叉树
                createBiTree_aux(p->left);                //左子树递归
                createBiTree_aux(p->right);                //右子树递归
        }
}

//先序遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::preOrderTraverse(){
        preOrderTraverse_aux(root);
}
//先序遍历二叉树的辅助函数
template <typename elemtype>
void BiTree<elemtype>::preOrderTraverse_aux(NodePointer p){
        if (p){
                cout << p->data << "\t";
                preOrderTraverse_aux(p->left);
                preOrderTraverse_aux(p->right);
        }
}


//中序遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::inOrderTraverse(){
        inOrderTraverse_aux(root);
}

//中序递归遍历二叉树辅助函数
template <typename elemtype>
void BiTree<elemtype>::inOrderTraverse_aux(NodePointer p){
        if (p){
                inOrderTraverse_aux(p->left);
                cout << p->data << "\t";
                inOrderTraverse_aux(p->right);
        }
}


//后续递归遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::postOrderTraverse(){
        postOrderTraverse_aux(root);
}

//后序递归遍历二叉树辅助函数
template <typename elemtype>
void BiTree<elemtype>::postOrderTraverse_aux(NodePointer p){
        if (p){
                postOrderTraverse_aux(p->left);
                postOrderTraverse_aux(p->right);
                cout << p->data << "\t";
        }
}


//求二叉树的深度
template <typename elemtype>
int BiTree<elemtype>::depth(){
        return depth_aux(root);
}

//求二叉树深度的辅助函数
template <typename elemtype>
int BiTree<elemtype>::depth_aux(NodePointer p){
        int lDep;                        //左子树深度
        int rDep;                        //右子树深度
        if (!p){                        //如果是空树，返回深度为0
                return 0;
        }
        else{                                //后序递归求二叉树深度
                lDep = depth_aux(p->left);
                rDep = depth_aux(p->right);

                return (lDep > rDep ? lDep : rDep) + 1;
        }
}

//按层次顺序遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::layOrderTraverse(){
        NodePointer p;                                                //预指向当前那遍历结点的指针
        SqQueue<NodePointer> Q;                                //顺序队列的类模板，预存放待遍历结点的指针队列
        if (root){
                Q.enQueue(root);                                //根指针进入队列
        }

        //逐一遍历队列每个指针所指向的结点
        while (!Q.isEmpty()){
                Q.deQueue(p);                                        //出队列指针p
                cout << p->data << "\t";                //输出数据域
                if (p->left){
                        Q.enQueue(p->left);                        //左孩子进队列
                }
                if (p->right){
                        Q.enQueue(p->right);                //右孩子进队列
                }
        }
}

//非递归中序遍历二叉树
template <typename elemtype>
void BiTree<elemtype>::noRecursionInOrderTraverse(){
        NodePointer p = root;
        SqStack<NodePointer> S;                                //预存放左子树上所有待遍历的结点
        while (p || !S.isEmpty()){
                if (p){
                        S.push(p);                                        //结点进栈
                        p = p->left;
                }
                else{
                        S.pop(p);                                        //如果当前结点为空，左子树走完，弹栈
                        cout << p->data << "\t";
                        p = p->right;
                }
        }
}


int main(void){
        BiTree<int> bt1;
        bt1.createBiTree();
        cout << "先序遍历二叉树：" << endl;
        bt1.preOrderTraverse();
        cout << endl;

        cout << "二叉树的深度:" << bt1.depth() << endl;
        cout << "层次遍历二叉树:";
        bt1.layOrderTraverse();
        cout << endl;
        cout << "非递归中序遍历二叉树:" << endl;
        bt1.noRecursionInOrderTraverse();


        return 0;
}








顺序队列：
#include <iostream>
#include <cstdlib>
#include <cstdbool>
#include <assert.h>
using namespace std;

template <typename elemtype>
class SqQueue{
public:
        //循环队列置空
        void clear();

        //出队列
        bool deQueue(elemtype &e);

        //进队列
        bool enQueue(elemtype e);

        //读取循环队列队头元素
        bool getFront(elemtype &e);

        //求循环队列的元素的个数
        int getLength();

        //判断队列是否为空
        bool isEmpty();

        //判断队列是否已满
        bool isFull();

        //重载赋值运算符
        SqQueue operator=(SqQueue right);

        //构造函数
        SqQueue(int size = 10);

        //析构函数
        virtual ~SqQueue();

        //拷贝构造函数
        SqQueue(SqQueue &other);

        //重载输出运算符
        template <typename out_put>
        friend ostream& operator <<(ostream& out, SqQueue<out_put> other);

protected:
        int rear;//队尾指针
        int front;//对头指针
        int queueSize;//循环队列最大存储空间
        elemtype *base;//队列动态存储空间的首地址
};


template <typename elemtype>
void SqQueue<elemtype>::clear(){
        front = rear;
}

//出队列
template <typename elemtype>
bool SqQueue<elemtype>::deQueue(elemtype &e){
        if (isEmpty()){
                return false;
        }
        e = base;
        front = (front + 1) % queueSize;//这里要取模，形成循环队列
        return true;
}

//进队列
template <typename elemtype>
bool SqQueue<elemtype>::enQueue(elemtype e){
        if (isFull()){
                return false;
        }
        base = e;
        rear = (rear + 1) % queueSize;
        return true;
}

//读取队头元素
template <typename elemtype>
bool SqQueue<elemtype>::getFront(elemtype &e){
        if (isEmpty()){
                return false;
        }
        e = base;
        return true;
}

//求队列中元素的个数
template <typename elemtype>
int SqQueue<elemtype>::getLength(){
        return (rear - front + queueSize) % queueSize;
}

//判断是否为空
template <typename elemtype>
bool SqQueue<elemtype>::isEmpty(){
        return front == rear ? true : false;
}

//判断队列是否已满
template <typename elemtype>
bool SqQueue<elemtype>::isFull(){
        return (rear + 1) % queueSize == front ? true : false;
}

//重载赋值运算符
template <typename elemtype>
SqQueue<elemtype> SqQueue<elemtype>::operator=(SqQueue<elemtype> right){
        if (this != &right){
                if (queueSize != right.queueSize){
                        delete[] base;
                        base = new elemtype;
                        assert(base != 0);
                        queueSize = right.queueSize;
                }

                front = right.front;
                rear = right.rear;

                for (int i = front; i%queueSize != rear;){
                        base = right.base;
                        i = (i + 1) % queueSize;
                }
        }
        return *this;
}

template <typename elemtype>
SqQueue<elemtype>::SqQueue(int size = 10){
        base = new elemtype;
        assert(base != 0);
        front = rear = 0;
        queueSize = size;
}

template <typename elemtype>
SqQueue<elemtype>:: ~SqQueue(){
        delete[]base;
}

//拷贝初始化构造函数
template <typename elemtype>
SqQueue<elemtype>::SqQueue(SqQueue &other){
        base = new elemtype;
        assert(base != 0);
        queueSize = other.queueSize;

        front = other.front;
        rear = other.rear;

        for (int i = front; i%queueSize != rear;){
                base = other.base;
                i = (i + 1) % queueSize;
        }
}

//重载输出运算符
template <typename out_put>
ostream& operator<<(ostream& out, SqQueue<out_put> other){
        for (int i = other.front; i%other.queueSize != other.rear;){
                out << other.base << "\t";
                i = (i + 1) % other.queueSize;
        }
        return out;
}



顺序栈：
#include <iostream>
#include <assert.h>
#include <cstdlib>
#include <cstdbool>
#define STACK_MAX_SIZE 100
#define STACKINCREAMENT 10
using namespace std;

template <typename elemtype>
class SqStack{
public:
        //顺序栈置空
        void clear();

        //求顺序栈中元素的个数
        int getLength();

        //返回档期那已经分派的存储空间的大小
        int getStackSize();

        //读取栈顶元素
        bool getTop(elemtype &e);

        //判断顺序栈是否为空
        bool isEmpty();

        //重载赋值运算符
        SqStack operator=(SqStack right);

        //弹出栈顶元素
        bool pop(elemtype &e);

        //在栈顶压入元素e
        void push(elemtype e);

        //构造函数
        SqStack();

        //析构函数
        virtual ~SqStack();

        //拷贝构造函数
        SqStack(SqStack &other);

        //重载输出运算符
        template <typename out_put>
        friend ostream& operator <<(ostream& out, SqStack<out_put> other);

protected:
        elemtype *base;//栈底指针，就是顺序栈动态存储空间的首地址
        elemtype *top;//栈顶指针
        int stackSize;//顺序栈当前已经分配的存储空间的大小
};


template <typename elemtype>
void SqStack<elemtype>::clear(){
        top = base;
        cout << "顺序栈已经清空" << endl;
}

template <typename elemtype>
int SqStack<elemtype>::getLength(){
        return top - base;
}

template <typename elemtype>
int SqStack<elemtype>::getStackSize(){
        return stackSize;
}

//读取栈顶的元素
template <typename elemtype>
bool SqStack<elemtype>::getTop(elemtype &e){
        if (isEmpty()){
                return false
        }
        else{
                e = *(top - 1);
        }
        return true;
}

template <typename elemtype>
bool SqStack<elemtype>::isEmpty(){
        return top == base ? true : false;
}

//重载赋值运算符
template <typename elemtype>
SqStack<elemtype> SqStack<elemtype>::operator =(SqStack<elemtype> right){
        int length = right.getLength();

        if (this != &right){
                if (stackSize < right.stackSize){
                        delete[] base;//回收左边的顺序栈的存取空间
                        base = new elemtype;
                        assert(base != 0);
                        stackSize = right.stackSize;//进行属性的一些重新的赋值
                }

                for (int i = 0; i < length; i++){
                        *(base + i) = *(right.base + i);
                }
                top = base + length();
        }
        return *this;//返回对象
}

//弹出栈顶元素到e
template <typename elemtype>
bool SqStack<elemtype>::pop(elemtype &e){
        if (isEmpty()){
                return false;
        }
        else{
                e = *--top;
        }
        return true;
}

//在栈顶压入元素e
template <typename elemtype>
void SqStack<elemtype>::push(elemtype e){
        int length = top - base;//顺序栈中元素的个数
        elemtype *newBase;//预指向新顺序栈的栈底指针
        //判断当前顺序栈是否已满，如果满了，则需要另外申请存储空间
        if (top - base >= stackSize){
                newBase = new elemtype;
                assert(newBase != 0);

                for (int j = 0; j < length; j++){
                        *(newBase + j) = *(base + j);
                }

                delete[] base;//回收当前已经满了的栈空间
                base = newBase;
                top = base + length;
        }

        //如果当前顺序栈没有满，就不用重新申请空间了，就直接以下两个语句就行了
        *top = e;
        top++;
}


template <typename elemtype>
SqStack<elemtype>::SqStack(){
        base = new elemtype;//申请空间
        assert(base != 0);
        stackSize = STACK_MAX_SIZE;//属性的赋值
        top = base;//栈的初始为空
}

//你懂的
template <typename elemtype>
SqStack<elemtype>::~SqStack(){
        if (base){
                delete[]base;
        }
        stackSize = 0;
        top = base = NULL;
}

template <typename elemtype>
SqStack<elemtype>::SqStack(SqStack &other){
        int length = other.top - other.base;
        base = new elemtype;

        assert(base != 0);

        stackSize = other.stackSize;
        for (int i = 0; i < length; i++){
                *(base + i) = *(other.base + i);
        }
        top = base + length;
}

template <typename out_put>
ostream& operator<<(ostream& out, SqStack<out_put> other){
        int length = other.top - other.base;
        for (int i = 0; i < length; i++){
                out << *(other.base + i) << "\t";
        }

        return out;
}

/*
int main(void){
        SqStack<int> s1;
        for (int i = 1; i <= 10; i++){
                s1.push(i);
        }
        cout << "顺序栈为:";
        cout << s1 << endl;//应用的重载的输出运算符
        cout << "####################################" << endl;
        int e;
        while (s1.pop(e)){
                cout << "弹出栈顶元素为:" << e << endl;
        }

        return 0;
}
*/

kykio 发表于 2018-5-8 19:57:10

溯影 发表于 2018-5-5 10:05
二叉树的那个帖子我想回复你但是不知道为什么我的帖子没有办法发出去。。。。。
层次遍历要用到队列，非递 ...

不知道为什么，一直没有提醒我有回复，所以看晚了，抱歉！

刘亮 发表于 2018-5-10 08:37:33

没怎么看懂，这是C++写的吧！我还没学呢

段坤11 发表于 2018-5-15 23:50:15

没怎么看懂，这是C++写的吧！我还没学呢

multitate 发表于 2018-7-12 00:14:53

学习一下{:5_106:}

独吟月上 发表于 2018-7-16 23:49:14

这个真的强

whdd 发表于 2018-9-16 12:16:12

{:9_218:}

钱闻韬 发表于 2018-9-16 17:29:01

666

whdd 发表于 2018-9-28 15:13:42

{:9_227:}

whdd 发表于 2018-10-1 23:59:05

{:7_139:}

小小小菜菜菜 发表于 2018-12-20 13:46:29

查看完整版本: 求大神帮忙解决