本质上是二叉树的层次遍历，遍历层次的过程当中把next指针加上去。
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
和问题"Populating Next Right Pointers in Each Node"类似。
如果给定的树是任意的二叉树，你先前的方法还能工作吗？
笔记：
例如给定的是羡慕的二叉树，
1
/ 2 3
/ \ 4 5 7当调用完你的函数后，这个树应该看起来想这样子： 1 -> NULL
/ 2 -> 3 -> NULL
/ \ 4-> 5 -> 7 -> NULL
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
For
example,
Given the following binary
tree,
1
/ 2 3
/ \ 4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ 2 -> 3 -> NULL
/ \ 4-> 5 -> 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 95 |
#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 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(7); ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3); ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5); ConnectTreeNodes(pNodeA3, NULL, pNodeA6); 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 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); } } |
【遍历二叉树】12往二叉树中添加层次链表的信息【Populating Next Right Pointers in Each Node II】,布布扣,bubuko.com
【遍历二叉树】12往二叉树中添加层次链表的信息【Populating Next Right Pointers in Each Node II】
原文：http://www.cnblogs.com/codemylife/p/3652351.html