投资网站建设优化排名推广关键词

原文地址：Level Order Tree Traversal

树的水平遍历就是广度优先遍历树。

上树的水平遍历顺序是：1 2 3 4 5。

方法1 （用函数打印指定的层）

算法：这个方法里面有两个基本的函数。一个是打印已知层的所有节点（printGivenLevel），另一个是打印树的水平顺序遍历（printLevelorder）。printLevelorder用printGivenLevel逐个从根部打印所有层的节点。

/*Function to print level order traversal of tree*/
printLevelorder(tree)
for d = 1 to height(tree)printGivenLevel(tree, d);/*Function to print all nodes at a given level*/
printGivenLevel(tree, level)
if tree is NULL then return;
if level is 1, thenprint(tree->data);
else if level greater than 1, thenprintGivenLevel(tree->left, level-1);printGivenLevel(tree->right, level-1);

实现：

// Recursive Java program for level order traversal of Binary Tree/* Class containing left and right child of current node and key value*/
class Node
{int data;Node left, right;public Node(int item){data = item;left = right = null;}
}class BinaryTree
{// Root of the Binary TreeNode root;public BinaryTree(){root = null;}/* function to print level order traversal of tree*/void printLevelOrder(){int h = height(root);int i;for (i=1; i<=h; i++)printGivenLevel(root, i);}/* Compute the "height" of a tree -- the number ofnodes along the longest path from the root nodedown to the farthest leaf node.*/int height(Node root){if (root == null)return 0;else{/* compute  height of each subtree */int lheight = height(root.left);int rheight = height(root.right);/* use the larger one */if (lheight > rheight)return(lheight+1);else return(rheight+1); }}/* Print nodes at the given level */void printGivenLevel (Node root ,int level){if (root == null)return;if (level == 1)System.out.print(root.data + " ");else if (level > 1){printGivenLevel(root.left, level-1);printGivenLevel(root.right, level-1);}}/* Driver program to test above functions */public static void main(String args[]){BinaryTree tree = new BinaryTree();tree.root= new Node(1);tree.root.left= new Node(2);tree.root.right= new Node(3);tree.root.left.left= new Node(4);tree.root.left.right= new Node(5);System.out.println("Level order traversal of binary tree is ");tree.printLevelOrder();}
}

输出：

Level order traversal of binary tree is - 
1 2 3 4 5 

最坏情况下的时间复杂度是：O(n^2) ，对于一个偏树（skewed tree），printGivenLevel()花费的时间是O(n)，n在这里是偏树的节点数目。所以printLevelOrder()的时间复杂度是O(n) + O(n-1) + O(n-2) + .. + O(1)，也就是O(n^2)

方法2：（用队列）

算法：

对于每一个节点，首先遍历这个节点，然后将这个节点的孩子节点推到一个FIFO的队列。

printLevelorder(tree)
1) Create an empty queue q
2) temp_node = root /*start from root*/
3) Loop while temp_node is not NULLa) print temp_node->data.b) Enqueue temp_node’s children (first left then right children) to qc) Dequeue a node from q and assign it’s value to temp_node

实现：

这里对上述算法做了一个简单的实现。队列是用数组实现的，它的最大尺寸是500。我们也可以用链表实现一个队列。

// Iterative Queue based Java program to do level order traversal
// of Binary Tree/* importing the inbuilt java classes required for the program */
import java.util.Queue;
import java.util.LinkedList;/* Class to represent Tree node */
class Node {int data;Node left, right;public Node(int item) {data = item;left = null;right = null;}
}/* Class to print Level Order Traversal */
class BinaryTree {Node root;/* Given a binary tree. Print its nodes in level orderusing array for implementing queue  */void printLevelOrder() {Queue<Node> queue = new LinkedList<Node>();queue.add(root);while (!queue.isEmpty()) {/* poll() removes the present head.For more information on poll() visit http://www.tutorialspoint.com/java/util/linkedlist_poll.htm */Node tempNode = queue.poll();System.out.print(tempNode.data + " ");/*Enqueue left child */if (tempNode.left != null) {queue.add(tempNode.left);}/*Enqueue right child */if (tempNode.right != null) {queue.add(tempNode.right);}}}public static void main(String args[]) {/* creating a binary tree and entering the nodes */BinaryTree tree_level = new BinaryTree();tree_level.root = new Node(1);tree_level.root.left = new Node(2);tree_level.root.right = new Node(3);tree_level.root.left.left = new Node(4);tree_level.root.left.right = new Node(5);System.out.println("Level order traversal of binary tree is - ");tree_level.printLevelOrder();}
}

输出：

Level order traversal of binary tree is - 
1 2 3 4 5 

时间复杂度：O(n)，n在这里是二叉树的节点数。