知識布局-數據結構-二叉查找樹-遍歷

前言

二叉樹的遍歷有三種方式：

1.前序遍歷

2.中序遍歷

3.後序遍歷

上述這三種遍歷方式都是相對於根節點來說。前序遍歷是先遍歷根節點，然後遍歷左子節點，最後遍歷右子節點；中序遍歷是先遍歷左子節點，然後遍歷根節點，最後遍歷右子節點；後序遍歷是先遍歷左子節點，然後遍歷右子節點，最後遍歷根節點。

比如如下的二叉查找樹的遍歷情況：

前序遍歷：

7-4-2-6-10-9

中序遍歷：

2-4-6-7-9-10

後序遍歷：

2-6-4-9-10-7

目錄

1.前序遍歷

2.中序遍歷

3.後序遍歷

4.總結

1.前序遍歷

/** * 前序遍歷 * 前序遍歷是先遍歷根節點，然後是左子節點，然後是右子節點 * * @param node 遍歷的節點 */public void preOrderTraverse(TreeNode node) { if (node == null) { return; } System.out.print(node.getData() + " "); preOrderTraverse(node.getLeftNode()); preOrderTraverse(node.getRightNode());}

2.中序遍歷

/** * 中序遍歷 * 中序遍歷是先訪問左子節點，然後是根節點，最後是右子節點 * * @param node 遍歷的節點 */public void midOrderTraverse(TreeNode node) { if (node == null) { return; } midOrderTraverse(node.getLeftNode()); System.out.print(node.getData() + " "); midOrderTraverse(node.getRightNode());}

3.後序遍歷

/** * 後序遍歷 * 後序遍歷是最後遍歷根節點。先訪問左子節點，然後是右子節點，最後是根節點 * * @param node 遍歷的節點 */public void lastOrderTraverse(TreeNode node) { if (node == null) { return; } lastOrderTraverse(node.getLeftNode()); lastOrderTraverse(node.getRightNode()); System.out.print(node.getData() + " ");}

4.總結

數據結構是一個高效的工具。他能改善

1.存儲的代價

2.查詢的代價

3.自己摸索的代價

所以，掌握好不同的數據結構能夠讓一個程序猿寫出更好的代碼。這點是毋庸置疑的。