二叉树顺序存储和遍历(2)

/** * 先序遍历1，非递归实现，借助栈来实现<p> * @param index 根节点从 1 开始 */ public void preOrderOne(int index){ ArrayStack<Integer> stack = new ArrayStack<Integer>(n); while (isExist(index) || !stack.isEmpty()) { // (1) 首先访问根节点，一直往左下方走，直到一个左孩子不存在的结点。 while (isExist(index)) { System.out.print(data[index - 1] + " "); stack.push(index); // 根节点入栈，把每个结点都看作一个根节点，检查其左右孩子是否存在 index = 2 * index; } // 此时，栈内是从根节点左孩子开始的左孩子，最后一个���点是不存在左孩子的结点 // (2) 拿栈顶元素，看其右孩子是否存在，把当前结点置为其右孩子，继续循环判断(1) if (!stack.isEmpty()) { int tmp = stack.pop(); // 弹出的左子树结点 index = 2 * tmp + 1; // 看它的右孩子是否存在 } } }

1.4 中序遍历 1.4.1 递归实现

/** * 中序遍历，递归实现Recursion * @param index 根节点从 1 开始 */ public void inOrderRecur(int index){ if(isExist(index)){ inOrderRecur(2*index); // 递归遍历左子树 System.out.print(data[index-1]+" "); // 访问根节点 inOrderRecur(2*index + 1); // 递归遍历右子树 } }

1.4.2 非递归实现

/** * 中序遍历，非递归实现，更改访问时机即可 * @param index */ public void inOrder(int index){ ArrayStack<Integer> stack = new ArrayStack<Integer>(n); while(isExist(index) || !stack.isEmpty()){ while(isExist(index)){ stack.push(index); // 根节点入栈 index = 2 * index; // 是否存在左孩子 } if(!stack.isEmpty()){ int tmp = stack.pop(); // 弹出左孩子 System.out.print(data[tmp-1]+" "); // 访问结点 index = 2 * tmp + 1; // 看左孩子的右孩子是否存在 } } }

1.5 后序遍历 1.5.1 递归实现

/** * 后序遍历，递归实现Recursion * @param index 根节点从 1 开始 */ public void postOrderRecur(int index){ if(isExist(index)){ postOrderRecur(2*index); // 递归遍历左子树 postOrderRecur(2*index + 1); // 递归遍历右子树 System.out.print(data[index-1]+" "); // 访问根节点 } }

1.5.2 非递归实现

/** * 后序遍历，非递归实现<p> * 与前中序相比实现比较麻烦，先访问左子树再访问右子树 */ public void postOrder(int index){ ArrayStack<Integer> stack = new ArrayStack<Integer>(n); int visited = 0; // 标记前一个已被访问的结点 while(isExist(index) || !stack.isEmpty()){ while(isExist(index)){ stack.push(index); // 根节点入栈 index = 2 * index; }// 先把 index 的左孩子全部找到 int top = stack.peek(); // 查看栈顶元素，没有弹出，访问完右孩子之后在弹出访问根节点 // 如果当前结点不存在右孩子或者右孩子已经访问过，则访问当前结点 if(!isExist(2*top+1) || (2*top+1) == visited){ int tmp = stack.pop(); System.out.print(data[tmp-1]+" "); visited = tmp; } else { // 否则访问右孩子 index = 2 * top + 1; } } }

2 测试