二叉樹是一種常用的數據結構,具有很多應用。在Java中,我們可以使用遍歷和構造來操作二叉樹。
首先,讓我們來看一下遍歷二叉樹的方法。按照遍歷順序的不同,二叉樹遍歷可以分為三種方式:
前序遍歷(父節點-左子樹-右子樹): public void preOrder(TreeNode node) { if (node == null) { return; } System.out.print(node.val + " "); preOrder(node.left); preOrder(node.right); } 中序遍歷(左子樹-父節點-右子樹): public void inOrder(TreeNode node) { if (node == null) { return; } inOrder(node.left); System.out.print(node.val + " "); inOrder(node.right); } 后序遍歷(左子樹-右子樹-父節點): public void postOrder(TreeNode node) { if (node == null) { return; } postOrder(node.left); postOrder(node.right); System.out.print(node.val + " "); }
其中,TreeNode表示二叉樹節點的類,包含值(val)、左子節點(left)和右子節點(right)。在上述代碼中,我們使用了遞歸的方式,對每個節點進行遍歷。
接下來,我們來看一下如何構造二叉樹。這里介紹一種常見的構造方法——遞歸。
public TreeNode buildTree(int[] preorder, int[] inorder) { return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1); } private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) { if (preStart >preEnd) { return null; } int rootVal = preorder[preStart]; int index = inStart; while (index<= inEnd && inorder[index] != rootVal) { index++; } int leftSize = index - inStart; TreeNode root = new TreeNode(rootVal); root.left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1); root.right = build(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd); return root; }
這里我們通過前序遍歷序列和中序遍歷序列來構造二叉樹。首先,我們將前序遍歷序列的第一個值作為當前節點值(rootVal)。在中序遍歷序列中,我們找到該值的位置(index),并根據它將中序遍歷序列分成左子樹和右子樹。
接下來,我們遞歸地構造左子樹和右子樹,并將它們分別作為當前節點的左子節點和右子節點。
綜上,遍歷和構造是我們操作二叉樹的重要工具,在Java中也有很好的實現方法。