滿二叉樹是指在樹中每個節點的子節點數均為2,除了葉子節點外,每個節點都有兩個子節點。
以下是Java中滿二叉樹的定義:
public class FullBinaryTree { public Node root; class Node { int value; Node left; Node right; public Node(int value) { this.value = value; } } }
滿二叉樹有三種遍歷方式:前序遍歷、中序遍歷和后序遍歷。
以下為Java中滿二叉樹的遍歷實現:
public class FullBinaryTree { ... public void preorderTraversal(Node node) { if (node != null) { System.out.print(node.value + " "); preorderTraversal(node.left); preorderTraversal(node.right); } } public void inorderTraversal(Node node) { if (node != null) { inorderTraversal(node.left); System.out.print(node.value + " "); inorderTraversal(node.right); } } public void postorderTraversal(Node node) { if (node != null) { postorderTraversal(node.left); postorderTraversal(node.right); System.out.print(node.value + " "); } } }
前序遍歷的順序為根節點、左子樹、右子樹;中序遍歷的順序為左子樹、根節點、右子樹;后序遍歷的順序為左子樹、右子樹、根節點。