The reason we traverse a binary tree is to examine each of its nodes. Many different binary tree algorithms involve traversals. For example if we wish to count the number of nodes in a tree we must visit each node. If we wish to find the largest value in each node, we must examine the value contained in each node.

There are two fundamentally different kinds of binary trees traversals--those that are depth-first and those that are breadth-first. When you watch the animation, notice that the path followed by each of these traversals is along the branches of the tree. Each node of the tree is visited three times during each of the depth-first traversals, once on its way down the tree, a second time coming up from the left child, and a third time coming up from the right child. When you watch the animation of these traversals, notice that a checkmark is placed beneath each node each time the node is visited.

There are three different types of depth-first traversals, preorder, inorder, and postorder. The preorder traversal extracts the value the first time it visits the node--when there is one checkmark beneath the node. During the animation, the value of the node is copied to the list at the bottom of the screen when the value is extracted. During the inorder traversal, the value is extracted during the second visit to the node--when there are two checkmarks beneath the node. During the postorder traversal, the value is extracted during the third visit--when there are three checkmarks beneath the node.

There is only one kind of breadth-first traversal--the level order traversal. When you watch the animation, notice that unlike the depth-first traversals, this traversal does not follow the branches of the tree. To implement a level-order traversal, we need a first-in first-out queue--not a stack.

All binary tree traversals, regardless of the order that they visit the nodes, are linear with respect to the number of number of nodes in the tree.

  翻译：

查看mercari原页面

收藏该商品

立即下单