数据结构之树-二叉树（Java版本） - JAVA

子路径循环走到“最左边”
// 当stack.peek()==null的时候退出while循环，表示到达了“最左边”
while ((p = (BinaryTreeNode) stack.peek()) != null)
stack.push(p.getLeftChild());
p = (BinaryTreeNode) stack.pop();// 弹出null元素
if (!stack.empty()) {
p = (BinaryTreeNode) stack.pop();
System.out.print(p.getElement().toString() + " ");
stack.push(p.getRightChild());
}
}
}

/**
* (10)先序遍历二叉树的非递归算法
*
* @param t
* 被遍历二叉树的根节点
*/
public static void PreOrder_Nonrecursive(BinaryTreeNode t) {
ArrayStack stack = new ArrayStack();// 辅助栈
BinaryTreeNode p;// 当前被考虑节点
stack.push(t);
while (!stack.empty()) {
while ((p = (BinaryTreeNode) stack.peek()) != null) {
// 先打印根节点，再将左孩子入栈
System.out.print(p.getElement().toString() + " ");
stack.push(p.getLeftChild());
}
p = (BinaryTreeNode) stack.pop();// 弹出null元素
if (!stack.empty()) {
p = (BinaryTreeNode) stack.pop();
stack.push(p.getRightChild());
}
}
}

/**
* (11)计算二叉树中叶子结点的数目
*
* @param t
* 指定二叉树
* @return 二叉树的叶子节点个数
*/
public static int LeafCount(BinaryTreeNode t) {
if (t == null)
return 0;
else if (t.getLeftChild() == null && t.getRightChild() == null)
return 1;
else
return LeafCount(t.getLeftChild()) + LeafCount(t.getRightChild());
}

/**
* (12)计算二叉树中以值为x的结点为根的子树深度
*
* @param t

* 指定的二叉树
* @param x
* 值
* @return 如果找到值为x的节点则返回该节点深度，否则返回-1
*/
public static void Get_sub_Depth(BinaryTreeNode t, Object x,int[] depth) {
if (t.getElement() == x) {
depth[0]=Get_Depth(t);
} else {
if (t.getLeftChild() != null)
Get_sub_Depth(t.getLeftChild(), x,depth);
if (t.getRightChild() != null)
Get_sub_Depth(t.getRightChild(), x,depth);
}
}

/**
* (13)辅助方法，用于确定指定二叉树结点的深度深度是从底层开始向上递增，底层深度为1
*
* @param t
* 指定二叉树节点
* @return 指定二叉树节点的深度
*/
public static int Get_Depth(BinaryTreeNode t) {
if (t == null)
return 0;
else {
int m = Get_Depth(t.getLeftChild());
int n = Get_Depth(t.getRightChild());
return (m > n m : n) + 1;
}
}

/*
* (13)后序遍历二叉树的非递归算法，使用栈为了区别两次进栈的不同处理方法，
* 在堆栈中增加一个mark域，mark=0 表示刚刚访问此结点，mark=1表示左
* 子树处理结束返回，mark=2表示右子树处理结束返回，每次根据栈顶元素的
* mark域决定执行什么工作。只有当左右子树都处理完毕后才能对该结点调用打
* 印操作，而且存储mark是在访问左右子树之前就执行。
*/
class PMType {
BinaryTreeNode ptr;
int mark;

public PMType(BinaryTreeNode ptr, int mark) {
this.ptr = ptr;
this.mark = mark;
}
}

public void PostOrder_Stack(BinaryTreeNode t) {
PMType a;
ArrayStack stack = new ArrayStack();
stack.push(new PMType(t, 0));
while (!stack.empty()) {
a = (PMType) stack.pop();
switch (a.mark) {
case

数据结构之树-二叉树（Java版本）(七)