BUAA_数据结构_5TH_1. 树叶节点遍历（树-基础题）

题目描述：

从标准输入中输入一组整数，在输入过程中按照左子结点值小于根结点值、右子结点值大于等于根结点值的方式构造一棵二叉查找树，然后从左至右输出所有树中叶结点的值及高度（根结点的高度为1）。例如，若按照以下顺序输入一组整数：50、38、30、64、58、40、10、73、70、50、60、100、35，则生成下面的二叉查找树：

从左到右的叶子结点包括：10、35、40、50、60、70、100，叶结点40的高度为3，其它叶结点的高度都为4。

输入形式

先从标准输入读取整数的个数，然后从下一行开始输入各个整数，整数之间以一个空格分隔。

输出形式

按照从左到右的顺序分行输出叶结点的值及高度，值和高度之间以一个空格分隔。

样例输入

13
50 38 30 64 58 40 10 73 70 50 60 100 35

样例输出

10 4
35 4
40 3
50 4
60 4
70 4
100 4

思路1

使用数组作为存储结构

参考代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define maxn 1000
typedef struct node
{
    int data;
    int high;//deep
    int leaf_or_not;
} Tree;
Tree tree[maxn+10];
int deep=0;

void build(int pos,int temp);
void LDR(int pos);

int main()
{
    for(int i=0;i<maxn+9;i++){
        tree[i].data=-1;
        tree[i].high=0;
        tree[i].leaf_or_not=1;
    }//初始化
    int n,temp;
    scanf("%d",&n);
    for (int i=0;i<n;i++){
        scanf("%d",&temp);
        deep=0;//每次重置deep为0
        build(1,temp);
    }
    LDR(1);
    return 0;
}

void build(int pos,int temp)
{
    deep++;
    if(tree[pos].data==-1){//如果这个结点之前没存数据，就存在这里
        tree[pos].data=temp;
        tree[pos].high=deep;
    }
    else if(temp<tree[pos].data){//分左右
        tree[pos].leaf_or_not=0;//说明有孩子，标记一下子
        build(2*pos,temp);//去左边找 2*pos为pos的左孩子
    }
    else if(temp>=tree[pos].data){
        tree[pos].leaf_or_not=0;
        build(2*pos+1,temp);//去右边找 2*pos+1为pos的右孩子
    }
}

void LDR(int pos)
{
    if(tree[pos].data!=-1){
        LDR(2*pos);
        if(tree[2*pos].data==-1&&tree[2*pos+1].data==-1){
            printf("%d %d\n",tree[pos].data,tree[pos].high);
        }
        LDR(2*pos+1);
    }
}

思路2

使用链表作为存储结构

参考代码

#include<stdio.h>
#include<stdlib.h>
#include<stdlib.h>
typedef struct tree{
    int data;
    int deep;
    struct tree *lc,*rc;
}tree,*tree_ptr;
tree_ptr root;
int height;

tree_ptr create_node(int data_temp,int deep_temp);
tree_ptr add(tree_ptr now,int temp);
void print(tree_ptr temp);
int is_leaf(tree_ptr temp);

int main()
{
    int n;
    scanf("%d",&n);
    int temp;
    scanf("%d",&temp);
    root=create_node(temp,1);
    for(int i=1;i<n;i++){
        scanf("%d",&temp);
        height=0;
        add(root,temp);
    }
    print(root);
    return 0;
}

tree_ptr create_node(int data_temp,int deep_temp)
{
    tree_ptr temp=(tree_ptr)malloc(sizeof(tree));
    temp->lc=NULL;
    temp->rc=NULL;
    temp->data=data_temp;
    temp->deep=deep_temp;
    return temp;
}

tree_ptr add(tree_ptr now,int temp)
{
    height++;
    if(now==NULL){
        now=create_node(temp,height);
    }
    else if(temp<now->data){
        now->lc=add(now->lc,temp);
    }
    else if(temp>=now->data){
        now->rc=add(now->rc,temp);
    }
    return now;
}

void print(tree_ptr temp)
{
    if(temp->lc){
        print(temp->lc);
    }
    if(is_leaf(temp))
        printf("%d %d\n",temp->data,temp->deep);
    if(temp->rc){
        print(temp->rc);
    }
}

int is_leaf(tree_ptr temp)
{
    if(temp->lc==NULL&&temp->rc==NULL){
        return 1;
    }
    else{
        return 0;
    }
}

有问题或bug 欢迎私戳/评论