c – 如何链接树中同一级别的所有节点

发布时间：2020-12-16 09:57:36 所属栏目：百科来源：网络整理

导读：我有一个二叉树： struct node { int n; // value of node struct node *left; // left subtree struct node *right; // right subtree struct node *level; // level pointer (node “to the right”)} 最初,level字段设置为NULL. 我需要编写一个函数来链接

我有一个二叉树：

struct node 
{
    int n; // value of node
    struct node *left; // left subtree
    struct node *right; // right subtree
    struct node *level; // level pointer (node “to the right”)
}

最初,level字段设置为NULL.

我需要编写一个函数来链接树中同一级别的所有节点(不仅是示例,而是任何给定的树).

void linkSameLevel(struct node *t);

如何知道我的函数的运行时间和内存使用量对于包含n个节点的深度为d的树？

在这里我有：

这就是我需要的：

解决方法

您可以为此目的使用两个队列并进行BFS遍历.
并保持两个指针currNode和prevNode.

>在Q1中推根.
>从Q1开始并初始化prevNode = null.
>从Q1开始,然后用它初始化currNode.在Q2中推送currNode的子节点.
>现在,如果prev！= null,则将prevNode与currNode链接.
>现在prevNode = currNode.
>从步骤3开始重复,直到Q1不为空.
>当Q1为空时.将Q2设置为Q1,将Q1设置为Q2(此新Q2将为空)并设置prevNode = null.转到第3步.

void linkSameLevel(node *root)
{
    if (root = null)
        return;
    queue<node *> Q1,Q2;
    Q1.push(root);
    node *currNode; node *prevNode;
    prevNode = null;
    do
    {
        while (!Q1.empty())
        {
            node *currNode = Q1.pop();
            Q2.push(currNode.left); Q2.push(currNode.right);
            if (prevNode != null)
                prevNode.level = currNode;
            prevNode = currNode;
        }
        swap(Q1,Q2);
    } while (!Q1.empty);
}

另外看看Level Order Traversal

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!