algorithm - 逐层读取二叉树。最快的方法是什么？

Question

假设有这样的二叉树。

我想逐层阅读（从左到右），所以输出看起来像：

2 4 5 3 1 3 9

谢谢。

Answer 1

它的打印BFS，你应该使用辅助数据结构队列：在这里学习

listed below is pseudocode for a simple queue based level order traversal,

levelorder(root) 
  q = empty queue
  q.enqueue(root)
  while not q.empty do
    node := q.dequeue()
    visit(node)
    if node.left ≠ null
      q.enqueue(node.left)
    if node.right ≠ null
      q.enqueue(node.right)

Answer 2

 This is one way of doing it.
void tree::BFS()
{
queue<node *>p;
node *leaf=root;

node *newline=new node; //this node helps to print a tree level by level
newline->val=0;
newline->left=NULL;
newline->right=NULL;
newline->parent=NULL;

p.push(leaf);
p.push(newline);

while(!p.empty())
{
    leaf=p.front();
    if(leaf==newline)
    {
        printf("\n");
        p.pop();
        if(!p.empty())
        p.push(newline);
    }
    else
    {
        cout<<leaf->val<<" ";
        if(leaf->left!=NULL)
        {
            p.push(leaf->left);
        }
        if(leaf->right!=NULL)
        {
            p.push(leaf->right);
        }
        p.pop();
    }
}
delete newline;

}

This implementation is using queue.There are other implementations also in which you 
do not need queue.

The below mwntioned code do not need any queue.

1) Using the parent pointer, get the level of the given node. Also, get the root of the  
tree.

int level = 1;
struct node *temp = node;

/* Find the level of the given node and root of the tree */
while(temp->parent != NULL)
{
 temp = temp->parent;
 level++;
}
/* temp is now root of the tree and level is level of the node */
2) Once we have level of the given node and root of the tree, traverse the tree from   
   root to the calculated level + 1. We are traversing one extra level for the case   
   when given node is the rightmost node of its level. While traversing if you visit 
   the given node, mark visited flag as 1. Print the node just after the visited flag.

#include <stdio.h>
#include <stdlib.h>

/* Note the structure of root. It has data and pointers to left childe, right child and
parent node */
struct node
{
int data;
struct node *left;
struct node *right;
struct node *parent;
};

/* Prints the level order successor of node
root  --> root of the tree
level --> level of node */
void _print(struct node* root, struct node *node, int level)
{
static int visited = 0;
if(root == NULL)
 return;
if(level == 1)
{
 /* If the given node is visited then print the current root */
 if(visited == 1)
 {
    printf("Level Order Successor is %d ", root->data);
    visited = 0;
    return;
 }
 /* If the current root is same as given node then change the visited flag
    so that current node is printed */
 if(root == node)
    visited = 1;
}
else if (level > 1)
{
  _print(root->left, node, level-1);
  _print(root->right, node, level-1);
}
}

void printLevelOrderSuccessor(struct node *node)
{
int level = 1;
struct node *temp = node;

/* Find the level of the given node and root of the tree */
while(temp->parent != NULL)
{
 temp = temp->parent;
 level++;
}
_print(temp, node, level);
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */ 
struct node* newNode(int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
return(node);
}  

/* Driver program to test above functions*/
int main()
{
  struct node *root  = newNode(1);
  root->parent      = NULL;
  root->left         = newNode(2);
  root->right        = newNode(3);
  root->left->parent = root;
  root->right->parent = root;  

root->left->left  = newNode(4);
root->right->right = newNode(5); 

root->left->left->parent   = root->left;
root->right->right->parent  = root->right;

// printf("\n Level order successor of %d is: ", root->right->data);
 printLevelOrderSuccessor(root->left->left);

return 0;
}

Time Complexity: O(n) for both the algos.
Space Complexity: O(n) if we consider the size of recursion stack, otherwise O(1).