二叉树的构造方法不一，这里根据存储结点次序的数字关系来构造父节点和孩子结点的关系（parentIndex*2+1==leftChildIndex，parentIndex*2+2==leftRightIndex），关于二叉树非递归遍历的详细介绍请看 二叉树的建立与遍历，下面程序还实现了查找叶子节点、查找某一元素是否存在的功能。
import java.util.LinkedList; import java.util.List; import java.util.Scanner; import java.util.Stack; public class TestBinaryTree { private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; private static List<Node> nodeList = null; private static class Node { int value; Node leftChild; Node rightChild; public Node(int value) { this.value = value; leftChild = null; rightChild = null; } } /* * 将给定的数组元素作为节点赋值到链表nodeList， 然后按照 array.length/2-1 个父节点与其孩子节点在链表的下标关系， * 构造二叉树。注意最后一个父节点可能没有右孩子节点，需特殊处理。 */ public Node createBinTree() { nodeList = new LinkedList<Node>(); for (int i = 0; i < array.length; i++) { nodeList.add(new Node(array[i])); } for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) { nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex * 2 + 1); nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex * 2 + 2); } int lastParentIndex = array.length / 2 - 1; nodeList.get(lastParentIndex).leftChild = nodeList.get(lastParentIndex * 2 + 1); if (array.length % 2 == 1) { nodeList.get(lastParentIndex).rightChild = nodeList.get(lastParentIndex * 2 + 2); } return nodeList.get(0); } /* * 0 对二叉树进行先根、中根和后根顺序深度地遍历并输出（非递归）, 这里借助栈来保存遍历过程中的节点 */ public void preOderTraverse(Node root) { if (root == null) return; Stack<Node> nodeStack = new Stack<>(); Node temp = root; nodeStack.push(temp); while (!nodeStack.isEmpty()) { temp = nodeStack.pop(); if (temp != null) { System.out.print(temp.value + " "); nodeStack.push(temp.rightChild); nodeStack.push(temp.leftChild); } } } public void inOderTraverse(Node root) { if (root == null) return; Stack<Node> nodeStack = new Stack<>(); Node temp = root; while ((temp != null) || (!nodeStack.empty())) { while (temp != null) { nodeStack.push(temp); temp = temp.leftChild; } temp = nodeStack.pop(); System.out.print(temp.value + " "); temp = temp.rightChild; } } private void aftOderTraverse(Node root) { if (root == null) return; Stack<Node> nodeStack = new Stack<>(); Node temp = root; while ((temp != null) || (!nodeStack.empty())) { while (temp != null) { nodeStack.push(temp); temp = temp.leftChild != null ? temp.leftChild : temp.rightChild; } temp = nodeStack.pop(); System.out.print(temp.value + " "); if ((!nodeStack.empty()) && (temp == nodeStack.peek().leftChild)) { temp = nodeStack.peek().rightChild; } else { temp = null; } } } /* * 统计二叉树的叶子节点个数并输出叶子节点的数据， 思路是递归地访问所有结点，判定其是否是叶子节点（有无孩子节点） */ public int findLeafNode(Node root) { int count; if (root == null) count = 0; else if ((root.leftChild == null) && (root.rightChild == null)) { count = 1; System.out.print(root.value + " "); } else count = findLeafNode(root.leftChild) + findLeafNode(root.rightChild); return count; } /* * 查找某元素在二叉树中是否存在，是则输出1，否则输出0， 思路是按某种遍历顺序访问所有结点，查找是否存在给定元素 */ public int findNode(Node root, int key) { int flag = 0; if (root == null) return flag; Stack<Node> nodeStack = new Stack<>(); Node temp = root; nodeStack.push(temp); while (!nodeStack.isEmpty()) { temp = nodeStack.pop(); if (temp != null) { // System.out.print(temp.value + " "); if(temp.value==key) { flag=1; break; } nodeStack.push(temp.rightChild); nodeStack.push(temp.leftChild); } } return flag; } public static void main(String[] args) { TestBinaryTree test = new TestBinaryTree(); Node root = test.createBinTree(); System.out.println("先根遍历："); test.preOderTraverse(root); System.out.println("\n中根遍历："); test.inOderTraverse(root); System.out.println("\n后根遍历："); test.aftOderTraverse(root); System.out.println("\n叶子节点："); int count = test.findLeafNode(root); System.out.println(" , 共有" + count + "个"); System.out.println("输入你要查找的元素："); Scanner input=new Scanner(System.in); int key=input.nextInt(); input.close(); System.out.println("结果："+test.findNode(root, key)); } }二叉树样例：
运行截图：
