b********e 发帖数: 693 | |
p******r 发帖数: 2999 | 2 用stack/list记录node
【在 b********e 的大作中提到】 : 要求每个level一行 : thanks
|
a*********9 发帖数: 523 | 3 用QUEUE入队
【在 b********e 的大作中提到】 : 要求每个level一行 : thanks
|
f*****o 发帖数: 2 | 4 可以中序遍历,每一层一个queue, 然后打印
空间比时间重要的话,可以中序搜索,每次搜多一层,每次打印一层 |
g**e 发帖数: 6127 | 5 从root开始,把所有子节点enqueue以后,再加一个分隔符enqueue
以后每遇到一个分隔符,就再加一个分隔符enqueue,直到queue为空就完了
【在 f*****o 的大作中提到】 : 可以中序遍历,每一层一个queue, 然后打印 : 空间比时间重要的话,可以中序搜索,每次搜多一层,每次打印一层
|
f*****o 发帖数: 2 | 6 嗯,貌似简单的广度优先搜索就行。
【在 g**e 的大作中提到】 : 从root开始,把所有子节点enqueue以后,再加一个分隔符enqueue : 以后每遇到一个分隔符,就再加一个分隔符enqueue,直到queue为空就完了
|
b********e 发帖数: 693 | 7 queue里面怎么加分隔符?
【在 g**e 的大作中提到】 : 从root开始,把所有子节点enqueue以后,再加一个分隔符enqueue : 以后每遇到一个分隔符,就再加一个分隔符enqueue,直到queue为空就完了
|
i***1 发帖数: 95 | 8 if we wants to print beautiful pics (which adds spaces to align nodes), then
I guess we need to do certain preprocessing. We have to know the depth even
it is a complete binary tree.
if we only wants to seperate them to different lines, then using BFS.
one way to avoid using "分隔符", is to use two arrays instead. (swap back
forth) |
f*********5 发帖数: 576 | 9 queue.push_back(NULL);
【在 b********e 的大作中提到】 : queue里面怎么加分隔符?
|
j**l 发帖数: 2911 | 10 你不判断分隔符是否在队尾是不行的,否则会死循环,一路追加分隔符到队尾。
【在 g**e 的大作中提到】 : 从root开始,把所有子节点enqueue以后,再加一个分隔符enqueue : 以后每遇到一个分隔符,就再加一个分隔符enqueue,直到queue为空就完了
|
|
|
i*****e 发帖数: 113 | 11 enqueue root
enqueue '\n'
while queue is not empty
if current node is '\n'
enqueue '\n'
else
enqueue all children of current node
example:
a
b1 b2
c1 c2 nil c3
nil nil nil d1
nil
a \n
a \n b1 b2 \n
a \n b1 b2 \n c1 c 2 c3 \n
a \n b1 b2 \n c1 c 2 c3 \n d1 \n |
j**l 发帖数: 2911 | 12 你不判断分隔符是否在队尾是不行的,否则会死循环,一路追加分隔符到队尾。
【在 i*****e 的大作中提到】 : enqueue root : enqueue '\n' : while queue is not empty : if current node is '\n' : enqueue '\n' : else : enqueue all children of current node : example: : a : b1 b2
|
i*****e 发帖数: 113 | 13 对,多谢提醒
应该在循环的时候加上计数,如果上一次没有child enqueue,则退出
【在 j**l 的大作中提到】 : 你不判断分隔符是否在队尾是不行的,否则会死循环,一路追加分隔符到队尾。
|
w******a 发帖数: 236 | 14 void printBinaryTree (Node * root) {
Node * myqueue[MAX_NODE_NUM] = { 0...MAX_NODE_NUM-1 = (Node *)0 };
int queue_pointer = 0;
int queue_size = 0;
while (root != 0) {
print ("%d\n", root->value);
if (root->lc != 0) {
myqueue[queue_size++] = root->lc;
}
if (root->rc != 0) {
myqueue[queue_size++] = root->rc;
}
root = myqueue[queue_pointer++];
}
} |
j**l 发帖数: 2911 | 15 这样就可以了:
enqueue root
enqueue '\n'
while queue is not empty
{
dequeue and set current node with the returned value
print current node
if current node is '\n' and queue is not empty
enqueue '\n'
else
enqueue all children of current node
}
【在 i*****e 的大作中提到】 : 对,多谢提醒 : 应该在循环的时候加上计数,如果上一次没有child enqueue,则退出
|
w******a 发帖数: 236 | 16 sorry,刚才没注意是要每一个level在一行输出,代码需要改改。
【在 w******a 的大作中提到】 : void printBinaryTree (Node * root) { : Node * myqueue[MAX_NODE_NUM] = { 0...MAX_NODE_NUM-1 = (Node *)0 }; : int queue_pointer = 0; : int queue_size = 0; : while (root != 0) { : print ("%d\n", root->value); : if (root->lc != 0) { : myqueue[queue_size++] = root->lc; : } : if (root->rc != 0) {
|