您好,登錄后才能下訂單哦!
小編給大家分享一下Java中二叉搜索樹遍歷操作的示例分析,希望大家閱讀完這篇文章之后都有所收獲,下面讓我們一起去探討吧!
前言:在上一節(jié)Java二叉搜索樹基礎(chǔ)中,我們對樹及其相關(guān)知識(shí)做了了解,對二叉搜索樹做了基本的實(shí)現(xiàn),下面我們繼續(xù)完善我們的二叉搜索樹。
對于二叉樹,有深度遍歷和廣度遍歷,深度遍歷有前序、中序以及后序三種遍歷方法,廣度遍歷即我們尋常所說的層次遍歷,如圖:
因?yàn)闃涞亩x本身就是遞歸定義,所以對于前序、中序以及后序這三種遍歷我們使用遞歸的方法實(shí)現(xiàn),而對于廣度優(yōu)先遍歷需要選擇其他數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn),本例中我們使用隊(duì)列來實(shí)現(xiàn)廣度優(yōu)先遍歷。
四種基本的遍歷思想為:
前序遍歷:根結(jié)點(diǎn) ---> 左子樹 ---> 右子樹
中序遍歷:左子樹---> 根結(jié)點(diǎn) ---> 右子樹
后序遍歷:左子樹 ---> 右子樹 ---> 根結(jié)點(diǎn)
層次遍歷:從上到下,從左到右。
比如,以下二叉樹的各種遍歷:
前序遍歷: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ù)上文提到的遍歷思路:根結(jié)點(diǎn) ---> 左子樹 ---> 右子樹,代碼實(shí)現(xiàn)如下:
//二分搜索樹的前序遍歷(前序遍歷:根結(jié)點(diǎ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ù)上文提到的遍歷思路:左子樹 ---> 根結(jié)點(diǎn) ---> 右子樹,代碼實(shí)現(xiàn)如下:
//二分搜索樹的中序遍歷(中序遍歷:左子樹---> 根結(jié)點(diǎ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ù)上文提到的遍歷思路:左子樹 ---> 右子樹 ---> 根結(jié)點(diǎn),代碼實(shí)現(xiàn)如下:
//二分搜索樹的后序遍歷(后序遍歷:左子樹 ---> 右子樹 ---> 根結(jié)點(diǎ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); }
對于層次遍歷,我們基于隊(duì)列來實(shí)現(xiàn),思路如下:
(1)先在隊(duì)列中增加根結(jié)點(diǎn)
(2)對于隨意其余任意節(jié)點(diǎn),在其出隊(duì)列的時(shí)候訪問(假設(shè)左孩子和右孩子有不為空的情況,入隊(duì)列)
代碼實(shí)現(xiàn)如下:
//層次遍歷--(基于隊(duì)列實(shí)現(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); } } }
看完了這篇文章,相信你對“Java中二叉搜索樹遍歷操作的示例分析”有了一定的了解,如果想了解更多相關(guān)知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道,感謝各位的閱讀!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。