数据结构实验六：二叉树源码

1、 输入一个完全二叉树的层次遍历字符串，创建这个二叉树，输出这个二叉树的前序遍历字符串、中序遍历字符串、后序遍历字符串、结点数目、二叉树高度(上述每一个结果独立一行显示)。

2、 输入二叉树前序序列和中序序列(各元素各不相同)，创建这个二叉树，输出该二叉树的后序序列、层次遍历。

#include<iostream>
#include<queue>
using namespace std;
int allCount,counter=0;
class BtreeNode{
public:
    char data;

    BtreeNode *leftChild,*rightChild;
    int size;
    BtreeNode(){leftChild=rightChild=nullptr;size=0;}
    BtreeNode(char& theData,BtreeNode* left=nullptr,BtreeNode*right=nullptr){
        data=theData;
        leftChild=left;
        rightChild=right;
        size=1;
    }
};
int height(BtreeNode *node){
    if(node == nullptr) return 0;
    int hl=height(node->leftChild);
    int hr=height(node->rightChild);
    if(hl>hr) {
        return++hl;
    }
    else {
        return ++hr;
    }
}

void preOrder(BtreeNode* node){//前序遍历输出
    if(node != nullptr){
        if(counter != allCount - 1) cout << node->data << ",";
        else cout << node->data << endl;
        counter++;
        preOrder(node->leftChild);
        preOrder(node->rightChild);
    }
}
void inOrder(BtreeNode* node){//中序遍历输出
    if(node != nullptr){
        inOrder(node->leftChild);
        if(counter != allCount - 1) cout << node->data << ",";
        else cout << node->data << endl;
        counter++;
        inOrder(node->rightChild);
    }
}
void postOrder(BtreeNode* node){//后序遍历输出
    if(node != nullptr){
        postOrder(node->leftChild);
        postOrder(node->rightChild);
        if(counter != allCount - 1) cout << node->data << ",";
        else cout << node->data << endl;
        counter++;
    }
}
void levelOrder(BtreeNode* node){//层序遍历输出
    queue<BtreeNode*> queue;
    while(node != nullptr){
        if(counter != allCount - 1) cout << node->data << ",";
        else cout << node->data << endl;
        counter++;
        if(node->leftChild != nullptr){
            queue.push(node->leftChild);
        }
        if(node->rightChild != nullptr){
            queue.push(node->rightChild);
        }
        if(queue.empty()){
            break;
        }
        node=queue.front();
        queue.pop();

    }
}
//按层次遍历顺序创建二叉树
void set(BtreeNode *current, int i, string s){
    if((2*i+1)<=s.length()){//如果当前节点既有左子节点，又有右子节点
        current->leftChild=new BtreeNode(s[2 * i - 1]);
        set(current->leftChild, 2 * i, s);
        current->rightChild=new BtreeNode(s[2 * i]);
        set(current->rightChild, 2 * i + 1, s);
        current->size+=(current->leftChild->size + current->rightChild->size);
        return;
    }
    else if(2*i==s.length()){//如果当前节点只有左子节点
        current->leftChild=new BtreeNode(s[2 * i - 1]);
        current->size+=current->leftChild->size;
        return;
    }
    else if(2*i>s.length()) return;//如果当前节点没有子节点
}
BtreeNode* rebuild(char preOrder[],char inOrder[],int pStart,int pEnd,int iStart,int iEnd){
    BtreeNode* tree=new BtreeNode(preOrder[pStart]);
    if(pStart==pEnd&&iStart==iEnd){
        return tree;
    }
    int root=0;
    //找中序遍历中的根节点
    for(root=iStart;root<=iEnd;root++){
        if(preOrder[pStart]==inOrder[root]) {
            break;
        }
    }//<=根节点在末尾 没有右子树的情况

    //划分左右子树
    int leftLength=root-iStart;//左子树
    int rightLength=iEnd-root;//右子树
    //遍历左子树
    if(leftLength>0){
        tree->leftChild=rebuild(preOrder,inOrder,pStart+1,pStart+leftLength,iStart,root-1);

    }
    //遍历右子树
    if(rightLength>0){
        tree->rightChild=rebuild(preOrder,inOrder,pStart+leftLength+1,pEnd,root+1,iEnd);

    }
    return tree;
}
int main(){
    cout<<"Input1"<<endl;
    string s1,s2,s3,ss;
    cin>>s1;
    cout<<"Output1"<<endl;
    BtreeNode *r1=new BtreeNode(s1[0]);
    set(r1,1,s1);
    allCount=s1.length();
    //为实现输出最后一个节点元素时换行，利用全局变量count，每输出一个元素+1，输出结束后清零，以便下一次输出
    preOrder(r1);counter=0;
    inOrder(r1);counter=0;
    postOrder(r1);counter=0;
    cout<<r1->size<<endl;
    cout<<height(r1)<<endl;
    cout<<"Input2"<<endl;
    cin>>s2>>s3;
    //用字符串读入二叉树前序序列和中序序列，并转化成字符数组对二叉树进行重建
    char char1[s2.length()]; s2.copy(char1, s2.length(), 0);
    char char2[s3.length()]; s3.copy(char2, s3.length(), 0);
    cout<<"Output2"<<endl;
    BtreeNode *r2=rebuild(char1, char2, 0, s2.length() - 1, 0, s3.length() - 1);
    allCount=s2.length();
    postOrder(r2);counter=0;
    levelOrder(r2);
    cout<<"End"<<endl;
    return 0;
}