本文共 4911 字,大约阅读时间需要 16 分钟。
原文地址:
树的水平遍历就是广度优先遍历树。
上树的水平遍历顺序是: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, then print(tree->data);else if level greater than 1, then printGivenLevel(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 Tree Node 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 of nodes along the longest path from the root node down 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 q2) temp_node = root /*start from root*/3) Loop while temp_node is not NULL a) print temp_node->data. b) Enqueue temp_node’s children (first left then right children) to q c) 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 order using array for implementing queue */ void printLevelOrder() { Queuequeue = new LinkedList (); 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在这里是二叉树的节点数。