本文實例講述了Java二叉搜索樹遍歷操作。分享給大家供大家參考，具體如下：

前言：在上一節(jié)Java二叉搜索樹基礎中，我們對樹及其相關知識做了了解，對二叉搜索樹做了基本的實現(xiàn)，下面我們繼續(xù)完善我們的二叉搜索樹。

對于二叉樹，有深度遍歷和廣度遍歷，深度遍歷有前序、中序以及后序三種遍歷方法，廣度遍歷即我們尋常所說的層次遍歷，如圖：

因為樹的定義本身就是遞歸定義，所以對于前序、中序以及后序這三種遍歷我們使用遞歸的方法實現(xiàn)，而對于廣度優(yōu)先遍歷需要選擇其他數(shù)據(jù)結構實現(xiàn)，本例中我們使用隊列來實現(xiàn)廣度優(yōu)先遍歷。

四種基本的遍歷思想為：

前序遍歷：根結點 ---> 左子樹 ---> 右子樹中序遍歷：左子樹---> 根結點 ---> 右子樹后序遍歷：左子樹 ---> 右子樹 ---> 根結點層次遍歷：從上到下，從左到右。

比如，以下二叉樹的各種遍歷：

前序遍歷:5-3-2-4-6-8中序遍歷:2-3-4-5-6-8后序遍歷:2-4-3-8-6-5層次遍歷：5-3-6-2-4-8

依據(jù)上文提到的遍歷思路：根結點 ---> 左子樹 ---> 右子樹，代碼實現(xiàn)如下：

//二分搜索樹的前序遍歷(前序遍歷：根結點 ---> 左子樹 ---> 右子樹) public void preOrder() { preOrder(root); } //前序遍歷以node為根的二分搜索樹,遞歸算法 private void preOrder(Node node) { if (node == null) { return; } System.out.println(node.e); preOrder(node.left); preOrder(node.right); }二、中序遍歷

依據(jù)上文提到的遍歷思路：左子樹 ---> 根結點 ---> 右子樹，代碼實現(xiàn)如下：

//二分搜索樹的中序遍歷(中序遍歷：左子樹---> 根結點 ---> 右子樹) public void inOrder() { inOrder(root); } //中序遍歷以node為根的二分搜索樹,遞歸算法 private void inOrder(Node node) { if (node == null) { return; } inOrder(node.left); System.out.println(node.e); inOrder(node.right); }三、后序遍歷

依據(jù)上文提到的遍歷思路：左子樹 ---> 右子樹 ---> 根結點,代碼實現(xiàn)如下：

//二分搜索樹的后序遍歷(后序遍歷：左子樹 ---> 右子樹 ---> 根結點) public void postOrder() { postOrder(root); } //后序遍歷以node為根的二分搜索樹,遞歸算法 private void postOrder(Node node) { if (node == null) { return; } postOrder(node.left); postOrder(node.right); System.out.println(node.e); }四、層次遍歷

對于層次遍歷，我們基于隊列來實現(xiàn)，思路如下：（1）先在隊列中增加根結點（2）對于隨意其余任意節(jié)點，在其出隊列的時候訪問（假設左孩子和右孩子有不為空的情況，入隊列）代碼實現(xiàn)如下：

//層次遍歷--(基于隊列實現(xiàn)) public void levelOrder() { Queue<Node> q = new LinkedList<>(); q.add(root); while (!q.isEmpty()) { Node cur = q.remove(); System.out.println(cur.e); if (cur.left != null) {q.add(cur.left); } if (cur.right!=null){q.add(cur.right); } } }

源代碼地址 https://github.com/FelixBin/dataStructure/blob/master/src/BST/BST.java

更多關于java算法相關內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結構與算法教程》、《Java操作DOM節(jié)點技巧總結》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對大家java程序設計有所幫助。