首页 > 其他 > 详细

【二叉树的递归】06填充每个节点中的下一个正确的指针【Populating Next Right Pointers in Each Node】

时间：2014-04-08 19:06:25      阅读：687      评论：0      收藏：0      [点我收藏+]

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

 给定一个二叉树

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

填入每个节点的next指针，如果没有右边的节点，那么这个next指针设置为NULL。

初始时候所有歌next指针都设置成NULL。

Note:

  • 空间复杂度必须是常量级别的。
  • 你可以假设这是个完全二叉树 (ie, 所有的叶子节点都在同一层，并且所有的父节点都有两个孩子节点).

例如，

给定下面的这个完全二叉树，

         1
       /        2    3
     / \  /     4  5  6  7

当调用完你的函数后，这个树应该是下面这样子的：

         1 -> NULL
       /        2 -> 3 -> NULL
     / \  /     4->5->6->7 -> NULL

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

 Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

  • You may only use constant extra space.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /        2    3
     / \  /     4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /        2 -> 3 -> NULL
     / \  /     4->5->6->7 -> NULL

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
test.cpp:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
  
#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>
#include "BinaryTreeWithNext.h"

using namespace std;
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
void connect(TreeLinkNode *root)
{
    if(root == NULL)
    {
        return ;
    }
    vector<TreeLinkNode *> vec;
    vec.push_back(root);
    int count = 1;
    while(!vec.empty())
    {
        if(count > 1)
        {
            vec[0]->next = vec[1];
        }
        else
        {
            vec[0]->next = NULL;
        }
        if(vec[0]->left != NULL)
        {
            vec.push_back(vec[0]->left);
        }
        if(vec[0]->right != NULL)
        {
            vec.push_back(vec[0]->right);
        }
        vec.erase(vec.begin());
        count--;

        if(count == 0)
        {
            count = vec.size();
        }
    }
}



// 树中结点含有分叉，
//                  1
//              /       \
//             2         3
//           /   \      /  \
//          4     5    6    7
int main()
{
    TreeLinkNode *pNodeA1 = CreateBinaryTreeNode(1);
    TreeLinkNode *pNodeA2 = CreateBinaryTreeNode(2);
    TreeLinkNode *pNodeA3 = CreateBinaryTreeNode(3);
    TreeLinkNode *pNodeA4 = CreateBinaryTreeNode(4);
    TreeLinkNode *pNodeA5 = CreateBinaryTreeNode(5);
    TreeLinkNode *pNodeA6 = CreateBinaryTreeNode(6);
    TreeLinkNode *pNodeA7 = CreateBinaryTreeNode(7);

    ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3);
    ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5);
    ConnectTreeNodes(pNodeA3, pNodeA6, pNodeA7);

    connect(pNodeA1);

    TreeLinkNode *trav = pNodeA1;
    TreeLinkNode *tmp;
    while (trav != NULL)
    {
        tmp = trav;
        while(tmp)
        {
            cout << tmp->val << " ";
            tmp = tmp->next;
        }
        cout << endl;
        trav = trav->left;
    }
    cout << endl;

    DestroyTree(pNodeA1);
    return 0;
}
结果输出：
1

2 3

4 5 6 7

BinaryTreeWithNext.h：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  
#ifndef _BINARY_TREE_WITH_NEXT_H_
#define _BINARY_TREE_WITH_NEXT_H_

struct TreeLinkNode
{
    int val;
    TreeLinkNode *left;
    TreeLinkNode *right;
    TreeLinkNode *next;
    TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};


TreeLinkNode *CreateBinaryTreeNode(int value);
void ConnectTreeNodes(TreeLinkNode *pParent,
                      TreeLinkNode *pLeft, TreeLinkNode *pRight);
void PrintTreeNode(TreeLinkNode *pNode);
void PrintTree(TreeLinkNode *pRoot);
void DestroyTree(TreeLinkNode *pRoot);


#endif /*_BINARY_TREE_WITH_NEXT_H_*/
BinaryTreeWithNext.cpp：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
  
#include <iostream>
#include <cstdio>
#include "BinaryTreeWithNext.h"

using namespace std;

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
//创建结点
TreeLinkNode *CreateBinaryTreeNode(int value)
{
    TreeLinkNode *pNode = new TreeLinkNode(value);

    return pNode;
}

//连接结点
void ConnectTreeNodes(TreeLinkNode *pParent, TreeLinkNode *pLeft, TreeLinkNode *pRight)
{
    if(pParent != NULL)
    {
        pParent->left = pLeft;
        pParent->right = pRight;
    }
}

//打印节点内容以及左右子结点内容
void PrintTreeNode(TreeLinkNode *pNode)
{
    if(pNode != NULL)
    {
        printf("value of this node is: %d\n", pNode->val);

        if(pNode->left != NULL)
            printf("value of its left child is: %d.\n", pNode->left->val);
        else
            printf("left child is null.\n");

        if(pNode->right != NULL)
            printf("value of its right child is: %d.\n", pNode->right->val);
        else
            printf("right child is null.\n");
    }
    else
    {
        printf("this node is null.\n");
    }

    printf("\n");
}

//前序遍历递归方法打印结点内容
void PrintTree(TreeLinkNode *pRoot)
{
    PrintTreeNode(pRoot);

    if(pRoot != NULL)
    {
        if(pRoot->left != NULL)
            PrintTree(pRoot->left);

        if(pRoot->right != NULL)
            PrintTree(pRoot->right);
    }
}

void DestroyTree(TreeLinkNode *pRoot)
{
    if(pRoot != NULL)
    {
        TreeLinkNode *pLeft = pRoot->left;
        TreeLinkNode *pRight = pRoot->right;

        delete pRoot;
        pRoot = NULL;

        DestroyTree(pLeft);
        DestroyTree(pRight);
    }
}





 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

【二叉树的递归】06填充每个节点中的下一个正确的指针【Populating Next Right Pointers in Each Node】,布布扣,bubuko.com

【二叉树的递归】06填充每个节点中的下一个正确的指针【Populating Next Right Pointers in Each Node】

原文：http://www.cnblogs.com/codemylife/p/3652398.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！