C语言-树的遍历

发布于 / 数据结构与算法 / Comments Off on C语言-树的遍历

0x00、树的静态写法

    之前刷PAT的过程中已经接触过树的静态写法了,不过之前接触过的都是二叉树,这里是树。

使用数组当做内存,下标当做地址,即可存放静态树。比如这样:

struct node{
    ElementType data;    //数据域
    int child[MAX];    //孩子域
}Node[MAX];

这里MAX是最大节点个数,因为C语言中数组大小是固定的,所以必须定义这个MAX。当然也可以使用vector存放孩子节点的地址,使得孩子的量可变:

struct node{
    ElementType data;
    vector<int> child;
}Node[MAX];

这样,我们就定义了一个二叉树的节点类型。

0x01、树的先根遍历

和二叉树的先序遍历一样,二叉树是固定的有两个孩子,而树是不固定的。所以我们要将孩子域的数组遍历一遍,遍历数组每一个孩子。

先根遍历,顾名思义,要先遍历根部。这里我们仍然使用递归进行遍历:

Void PreOrder(int root){
    printf("%d ", Node[root].data);    //访问数据域数据
    for(int i = 0; i < Node[root].child[i])
        PreOrder(Node[root].child[i]);
}

我们明显的发现,上面的代码并没有递归边界,这是因为数组遍历完成后,递归就退出了,所以我们不需要递归边界。

0x02、树的层序遍历

    和二叉树一样,树也存在着层序遍历。我们可以使用队列来实现:

Void LayerOrder(int root){
    queue<int> Q;
    Q.push(root);
    while(!Q.empty()){
        int front = Q.front();
        Q.pop();
        for(int i = 0; i < Node[front].child.size(); i++)
            Q.push(Node[front].child[i]);
    }
}

如果我们需要获取层次信息,我们可以在结构体中定义layer:

struct node{
    int layer;
    ElementType data;
    vector<int> child;
}

在遍历中只需要加上判断层号的代码即可

转载原创文章请注明,转载自: 斐斐のBlog » C语言-树的遍历
评论已关闭