如何使用级序遍历序列构造二叉树 [英] How to construct a binary tree using a level order traversal sequence
问题描述
如何使用水平序遍历序列，例如从序列构造的二进制树{1,2,3，＃，＃4，＃，＃，5}，我们可以构建这样一个二叉树：
1
/ \
2 3
/
4
\
五
其中＃表示低于在不存在节点的路径终止。
最后，我实现了范忠的算法，用C ++
结构树节点
{
树节点*离开;
树节点*权利;
INT VAL;
树节点（INT X）：左（NULL），右（NULL），缬氨酸（X）{}
};
树节点* build_tree（字符节点[]，INT N）
{
树节点*根=新树节点（节点[0] - '0'）;
队列＆LT;树节点*＆GT; q;
布尔is_left = TRUE;
树节点* CUR = NULL;
q.push（根）;
的for（int i = 1;我n种;我++）{
树节点*节点= NULL;
如果（节点[I]！='＃'）{
节点=新树节点（节点[I] - '0'）;
q.push（节点）;
}
如果（is_left）{
CUR = q.front（）;
q.pop（）;
当前＆GT;左=节点;
is_left = FALSE;
} 其他 {
当前＆GT;右=节点;
is_left = TRUE;
}
}
返回根;
}
假设使用数组 INT []数据 0的索引，我们有一个简单的函数来获得儿童：
-
左子
INT getLeftChild（INT指数）{ 如果（指数* 2 + 1＆GT; = data.length） 返回-1; // -1表示出界 返回数据[（指数* 2）+ 1]; } -
右键孩子
INT getRightChild（INT指数）{ 如果（指数* 2 +2; = data.length） 返回-1; // -1表示出界 返回数据[（指数* 2）+ 2]; }
编辑： 好了，通过维持一个队列，我们可以建立该二叉树。
我们使用队列来维持的尚未处理的节点。
使用一个变量计数来跟踪当前节点添加孩子的数目
首先，创建根节点，将其指定为当前节点。 因此，从指数1日起（索引0是根），作为计数为0，我们作为这个节点作为当前节点的左子。 增加计数。如果此节点不是'＃'，将其添加到队列中。
移动到下一个索引，计数为1，所以我们作为当前节点的这个作为右子，重置计数为0，并更新当前节点（通过分配当前节点作为队列中的第一个元件）。如果此节点不是'＃'，将其添加到队列中。
诠释计数= 0;
队列Q =新的队列（）;
q.add（新节点（数据[0]）;
节点CUR = NULL;
的for（int i = 1; I＆LT; data.length;我++）{
节点node =新节点（数据[I]）;
如果（计数== 0）{
CUR = q.dequeue（）;
}
如果（计数== 0）{
算上++;
cur.leftChild =节点;
}其他 {
计数= 0;
cur.rightChild =节点;
}
如果（数据[I]！='＃'）{
q.enqueue（节点）;
}
}
类节点{
int数据;
节点leftChild，rightChild;
}
How to construct a binary tree using a level order traversal sequence, for example from sequence {1,2,3,#,#,4,#,#,5}, we can construct a binary tree like this:
1
/ \
2 3
/
4
\
5
where '#' signifies a path terminator where no node exists below.
Finally I implement Pham Trung's algorithm by c++
struct TreeNode
{
TreeNode *left;
TreeNode *right;
int val;
TreeNode(int x): left(NULL), right(NULL), val(x) {}
};
TreeNode *build_tree(char nodes[], int n)
{
TreeNode *root = new TreeNode(nodes[0] - '0');
queue<TreeNode*> q;
bool is_left = true;
TreeNode *cur = NULL;
q.push(root);
for (int i = 1; i < n; i++) {
TreeNode *node = NULL;
if (nodes[i] != '#') {
node = new TreeNode(nodes[i] - '0');
q.push(node);
}
if (is_left) {
cur = q.front();
q.pop();
cur->left = node;
is_left = false;
} else {
cur->right = node;
is_left = true;
}
}
return root;
}
Assume using array int[]data with 0-based index, we have a simple function to get children:
Left child
int getLeftChild(int index){ if(index*2 + 1 >= data.length) return -1;// -1 Means out of bound return data[(index*2) + 1]; }Right child
int getRightChild(int index){ if(index*2 + 2 >= data.length) return -1;// -1 Means out of bound return data[(index*2) + 2]; }
Edit: Ok, so by maintaining a queue , we can build this binary tree.
We use a queue to maintain those nodes that are not yet processed.
Using a variable count to keep track of the number of children added for the current node.
First, create root node, assign it as current node. So starting from index 1 (index 0 is the root), as count is 0, we as this node as left child of the current node. Increase count. If this node is not '#', add it to the queue.
Moving to the next index, the count is 1, so we as this as right child of current node, reset count to 0 and update current node (by assign current node as the first element in the queue). If this node is not '#', add it to the queue.
int count = 0;
Queue q = new Queue();
q.add(new Node(data[0]);
Node cur = null;
for(int i = 1; i < data.length; i++){
Node node = new Node(data[i]);
if(count == 0){
cur = q.dequeue();
}
if(count==0){
count++;
cur.leftChild = node;
}else {
count = 0;
cur.rightChild = node;
}
if(data[i] != '#'){
q.enqueue(node);
}
}
class Node{
int data;
Node leftChild, rightChild;
}
这篇关于如何使用级序遍历序列构造二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
