二叉树的创建和路径长度

题目 二叉树中根结点到所有其他结点的路径及路径长度问题
[实验目的]
验证二叉树及其上的基本操作。
[实验内容及要求]
1、 定义二叉树类。
2、 实现如下功能:
① 根据老师输入的测试数据(整型)从无到有创建一棵二叉树Treel。
② 求根结点到二叉树中所有其他结点的路径及路径长度并打印输出。
3、 为便于观察程序的运行结果,设计的输出函数能在屏幕上以规范、直观的形
式输出计算结果。例如将路径输出成如下形式:1->2 -> 3 -> 4 -> 5
4、 为了增强程序的可读性,程序中要有适当的注释

函数部分:

typedef struct Binary_tree{
    struct Binary_tree * left;
    int data;
    struct Binary_tree * right;
}bt,*pbt;

int str2int(string str){
    int data_int=0;
    for(int i=0;i<str.length();i++)
    {
        data_int*=10;
        data_int+=(int(str[i])-48);//string 转 int
    }
    return data_int;
}

pbt create_Binary_tree(){
    pbt p;
    string data;
    cout<<"please inupt data(if you want to stop,input *):";
    cin>>data;
    if(data[0]=='*'){
        p=NULL;
        return p;
    }
    else{
        p=(pbt)malloc(sizeof(bt));
        p->data=str2int(data);
        p->left=create_Binary_tree();
        p->right=create_Binary_tree();
    }
    return p;
}

void Preorder_traversal(pbt p){
    if(p!=NULL){
        cout<<p->data<<' ';
        Preorder_traversal(p->left);
        Preorder_traversal(p->right);
    }
}

void output_length(pbt p,int count,vector<int>data){
    if(p!=NULL){
        if(count!=0)
        {
            for(int i=0;i<count-1;i++)
                cout<<data[i]<<" -> ";
            cout<<data[count-1];
        }
        if(count!=0)
            cout<<" -> ";
        cout<<p->data;
        cout<<"  length: "<<count<<endl;
        data.push_back(p->data);
        output_length(p->left, count+1, data);
        output_length(p->right, count+1, data);
    }
    return;
}

 

调用部分:

pbt head;
vector<int>data;
head=create_Binary_tree();
Preorder_traversal(head);
cout<<endl;
output_length(head, 0, data);

 

点赞

发表评论