假如現在有一棵樹，如圖：

樹的遍歷主要分為前序遍歷、中序遍歷和后序遍歷。上面圖的樹遍歷結果如下：

前序遍歷：532468

中序遍歷：234568

后序遍歷：243865

?

可以簡單理解（不嚴謹）：以根節點為參考點，前序遍歷是根節點首先輸出，然后左子樹輸出，最后右子樹輸出；中序遍歷是左子樹先輸出，根節點在中間輸出，右子樹最后輸出；后續遍歷是左子樹，右子樹，最后根節點最后輸出。

這里以中序遍歷分析一下：

1、首先遍歷根節點，有左子樹，所以遍歷左子樹3

2、3有左子樹，所以遍歷左子樹2

3、2遍歷左子樹為null，所以返回2，然后輸出2

4、接著遍歷2的右子樹，為null,返回2后，在返回3，接著輸出3

5、然后遍歷右子樹4，4的左子樹為null，返回4，接著輸出4，然后接著遍歷4的右子樹，為null，然后返回3，再返回5，輸出5.

6、返回5后，再遍歷5的右子樹，遍歷和上面類似。最終輸出：234568

代碼如下：

import java.util.Stack;public class BST<E extends Comparable<E>> {private class Node {public E e;public Node left, right;public Node(E e) {this.e = e;left = null;right = null;}}private Node root;private int size;public BST(){root = null;size = 0;}public int size(){return size;}public boolean isEmpty(){return size == 0;}// 向二分搜索樹中添加新的元素epublic void add(E e){root = add(root, e);}// 向以node為根的二分搜索樹中插入元素e，遞歸算法// 返回插入新節點后二分搜索樹的根private Node add(Node node, E e){if(node == null){size ++;return new Node(e);}if(e.compareTo(node.e) < 0)node.left = add(node.left, e);else if(e.compareTo(node.e) > 0)node.right = add(node.right, e);return node;}// 看二分搜索樹中是否包含元素epublic boolean contains(E e){return contains(root, e);}// 看以node為根的二分搜索樹中是否包含元素e, 遞歸算法private boolean contains(Node node, E e){if(node == null)return false;if(e.compareTo(node.e) == 0)return true;else if(e.compareTo(node.e) < 0)return contains(node.left, e);else // e.compareTo(node.e) > 0return contains(node.right, e);}// 二分搜索樹的前序遍歷public void preOrder(){System.out.print("前序遍歷：");preOrder(root);}// 前序遍歷以node為根的二分搜索樹, 遞歸算法private void preOrder(Node node){if(node == null)return;System.out.print(node.e + " ");preOrder(node.left);preOrder(node.right);}// 二分搜索樹的中序遍歷public void inOrder(){System.out.print("中序遍歷：");inOrder(root);}// 中序遍歷以node為根的二分搜索樹, 遞歸算法private void inOrder(Node node){if(node == null)return;inOrder(node.left);System.out.print(node.e + " ");inOrder(node.right);}// 二分搜索樹的后序遍歷public void postOrder(){System.out.print("后序遍歷：");postOrder(root);}// 后序遍歷以node為根的二分搜索樹, 遞歸算法private void postOrder(Node node){if(node == null)return;postOrder(node.left);postOrder(node.right);System.out.print(node.e + " ");}@Overridepublic String toString(){StringBuilder res = new StringBuilder();generateString(root, 0, res);return res.toString();}// 生成以node為根節點，深度為depth的描述二叉樹的字符串private void generateString(Node node, int depth, StringBuilder res){if(node == null){res.append(generateDepthString(depth) + "null\n");return;}res.append(generateDepthString(depth) + node.e + "\n");generateString(node.left, depth + 1, res);generateString(node.right, depth + 1, res);}private String generateDepthString(int depth){StringBuilder res = new StringBuilder();for(int i = 0 ; i < depth ; i ++)res.append("--");return res.toString();} } BST<Integer> bst = new BST<>();int[] nums = {5, 3, 6, 8, 4, 2};for(int num: nums)bst.add(num);bst.preOrder();System.out.println();bst.inOrder();System.out.println();bst.postOrder();System.out.println();/*output：前序遍歷：5 3 2 4 6 8 中序遍歷：2 3 4 5 6 8 后序遍歷：2 4 3 8 6 5 */

用遞歸，進行深度遍歷。

轉載于:https://www.cnblogs.com/luoa/p/10839731.html

總結

以上是生活随笔為你收集整理的树的遍历和代码实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。