565      阿里云  技术社区[云栖]

二叉树的应用-先序遍历中序遍历还原二叉树

二叉树的一些应用 还是大实验要求的 还有已知先序遍历 中序遍历求后续遍历

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 100 //节点个数
#define Null 0
typedef int Elemtype;
class node
{
public:
    Elemtype data;
    node* rchild;
    node* lchild;
};
class tree
{
public:
    node *head;
    tree();//初始化
    node *input_1();//按照先序输入二叉树
    node *input_2();//已知先序遍历 层次遍历输入 建立二叉树
    node *input_3();//已知先序中序遍历 输入 建立二叉树
    node *input_3_build(Elemtype *first,Elemtype *mid,int len);//递归函数
    void output_dfsf(node *p);//先序遍历输出
    void output_dfsm(node *p);//中序遍历输出
    void output_dfsl(node *p);//后序遍历输出
    void output_bfs(node *p);//层次遍历输出
    tree huffman();//构建该二叉树的哈弗曼树
};
tree::tree()
{
    head=NULL;
}
node *tree::input_1()
{
    node *p;
    Elemtype x;
    cin>>x;
    if(x==Null)
        p=NULL;
    else
    {
        p=(node *)malloc(sizeof(node));
        p->data=x;
        p->lchild=input_1();
        p->rchild=input_1();
    }
    return p;
}

void tree::output_dfsf(node *p)
{
    if(!p)
        cout<<"* ";
    else
    {
        cout<<p->data<<" ";
        output_dfsf(p->lchild);
        output_dfsf(p->rchild);
    }
}
void tree::output_dfsm(node *p)
{
    if(!p)
        cout<<"* ";
    else
    {
        output_dfsm(p->lchild);
        cout<<p->data<<" ";
        output_dfsm(p->rchild);
    }
}
void tree::output_dfsl(node *p)
{
    if(!p)
        cout<<"* ";
    else
    {
        output_dfsl(p->lchild);
        output_dfsl(p->rchild);
        cout<<p->data<<" ";
    }
}
void tree::output_bfs(node *p)
{
    node* queue[MAX];
    int top=0,base=-1;
    queue[top]=p;
    while(top!=base)
    {
        base++;
        printf("%d ",queue[base]->data);
        if(queue[base]->lchild)
            queue[++top]=queue[base]->lchild;
        if(queue[base]->rchild)
            queue[++top]=queue[base]->rchild;
    }
    cout<<endl;
}

node *tree::input_2()
{
    int num;
    Elemtype data_dfs[MAX],data_bfs[MAX];
    do
    {
        cout<<"please input num of node(num>0)"<<endl;
        cin>>num;
    }
    while(num<=0);
    cout<<"input data of data_dfs"<<endl;
    for(int i=0; i<num; i++)
        cin>>data_dfs[i];
    cout<<"input data of data_bfs"<<endl;
    for(int i=0; i<num; i++)
        cin>>data_bfs[i];
}
node *tree::input_3_build(Elemtype *first,Elemtype *mid,int len)
{
    if(len<=0)
        return NULL;
    node *p=(node *)malloc(sizeof(node));
    p->data=*first;
    Elemtype *q;
    for(q=mid; q!=NULL; q++)
        if(*q==*first)
            break;
    int k=q-mid;
    p->lchild=input_3_build(first+1,mid,k);
    p->rchild=input_3_build(first+k+1,q+1,len-k-1);
    return p;
}
node *tree::input_3()
{
    int num;
    node *p;
    Elemtype data_first[MAX],data_mid[MAX];
    do
    {
        cout<<"please input num of node"<<endl;
        cin>>num;
    }
    while(num<=0);
    cout<<"input first"<<endl;
    for(int i=0; i<num; i++)
        cin>>data_first[i];
    cout<<"input mid"<<endl;
    for(int i=0; i<num; i++)
        cin>>data_mid[i];
    p=input_3_build(data_first,data_mid,num);
    return p;
}
int main()
{
    tree a;
    a.head=a.input_1();
    a.output_dfsf(a.head);
    cout<<endl;
    a.output_dfsm(a.head);
    cout<<endl;
    a.output_dfsl(a.head);
    cout<<endl;
    a.output_bfs(a.head);
    cout << "Hello world!" << endl;
    return 0;
}

最后更新：2017-04-04 07:03:12

  上一篇： Java中数据输入输出流——DataInputStream和DataOutputStream

  下一篇： Objective-C: delegate的那点事儿