construct BTree from breadth-order input

Posted on |

first there should be a queue or stack to store the next layer elements, as the tree go deeper, there are many branches, which requires a contianer to track what’s the elements in next layer. stack always pop out the top element(FILO), which actually set the input elements in a reversed order as tree elements; queue can pop out the first element(FIFO), which can set the input elements in the same order in tree elements. so here pick std::queue.

the input array can used std::vector, each time pop_front(), which basically read the array in order. and each pop_front element constructs a new TreeNode. if the layer container is empty(), then it’s the root layer; else it’s a branch layer. growing the tree in each branch layer, need update the next layer container.

for each new inserting element, either insert to left or right of node A in parent layer or insert to the A’s sibling node B. then pop out the node which already has both kids.

when traversling to the last node in parent layer, and if both the kids are filled-in, then there is a turning point, need to swap next_parent layer as parent layer.

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
void insert_kids(std::queue<TreeNode*>& parents, std::queue<TreeNode*>& next_parents, TreeNode* p)
{
	if(parents.empty())
		return ;
	TreeNode* father = parents.front();
	if(!father->left)
	{
		father->left = p;
		if(p)
			next_parents.push(p);
	}else if(!father->right)
	{
		father->right = p;
		if(p)
			next_parents.push(p);
	}else
	{
		parents.pop(); 
		if(parents.empty())  // turning point, if returned then p will be lost 
		{
			parents.swap(next_parents);  
		}		
		insert_kids(parents, next_parents, p); 	}	
}
TreeNode* breadth_construct(list<int>& arr)
{
	TreeNode *p, *root ; 
	int x ; 
	std::queue<TreeNode*> parents, next_parents; 
	
	while(!arr.empty())
	{
		x = arr.front();	
		arr.pop_front();
		
		p = (TreeNode*) new TreeNode(x); 
			
		if(parents.empty())
		{
			parents.push(p);
			root = p ; 
			continue; 
		}else if( !parents.empty())  //at this step, parents still has 1 element, but after insert_kids, parents is empty. then 
		{
			insert_kids(parents, next_parents, p); 
			continue;
		}
	}
	return root; 
}

how to deal with NULL during struct constructure? if both (int x) and (TreeNode* p) constructor are defined, which will lead to ambisious when new TreeNode(NULL).

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
struct TreeNode {
	int value ;
	struct TreeNode *left ;
	struct TreeNode *right;
	//TODO: how to implement copy assignment in structure ?
	TreeNode(TreeNode* p)
	{
		if(p == NULL)
		{
			value = 0;
			left = NULL;
			right = NULL;
		}else
		{
			value = p->value;
			left = p->left;
			right = p->right; 
		}
	}
	TreeNode(int x):
		value(x), 
		left(NULL),	
		right(NULL)
		{
		}
};