stack.push(new PMType(a.ptr, 1));
if (a.ptr.getLeftChild() != null)
stack.push(new PMType(a.ptr.getLeftChild(), 0));
break;
case 1:
stack.push(new PMType(a.ptr, 2));
if (a.ptr.getRightChild() != null)
stack.push(new PMType(a.ptr.getRightChild(), 0));
break;
case 2:
System.out.print(a.ptr.getElement().toString() + " ");
}
}
}
/**
* (14)求树节点的子孙总数 为了能用一个统一的计算公式计算子孙数目，
* 当t为空指针的时候，访问设置为-1而不是0
*/
public int DescNum(BinaryTreeNode t) {
if (t == null)
return -1;
else
return (DescNum(t.getLeftChild()) + DescNum(t.getRightChild()) + 2);
}
/**
* (15)判断二叉树是否为完全二叉树 思想：不管当前结点是否有左右孩子，都入列，这样当树是完全二叉树
* 时候，遍历时候得到的是一个连续的不包含空指针的序列，反之则有空指针。 另外可能出现一种情况：队列的最后是连续的空指针，此时也是完全二叉树，
* 这种情况在算法中的表现是每一次循环都只执行到if (btn == null)flag = true;
* 如果之后没有出现非空指针则队列将空，return true，如果之后出现非空指针 算法将执行语句else if (flag) return
* false;
*/
public boolean IsFullBinaryTree(BinaryTreeNode t) {
ArrayQueue queue = new ArrayQueue();
BinaryTreeNode btn;
boolean flag = false;
queue.put(t);
while (!queue.isEmpty()) {
btn = (BinaryTreeNode) queue.get();
if (btn == null)
flag = true;
else if (flag)
return false;
else {
queue.put(btn.getLeftChild());
queue.put(btn.getRightChild());
}
}
return true;
}
/**
* (16)求二叉树中结点p,q的最近共同祖先
*/
boolean found = false;
public BinaryTreeNode Find_Near_Ancient(BinaryTreeNode t, BinaryTreeNode p,
BinaryTreeNode q) {
int i;
BinaryTreeNode[] pathp = new BinaryTreeNode[100];
BinaryTreeNode[] pathq = new BinaryTreeNode[100];
// 将根t到两个结点p，q的路径存放在数组当中
FindPath(t, p, pathp, 0);
found = false;
FindPath(t, q, pathq, 0);
for (i = 0; pathq[i] == pathp[i] && pathp[i] != null; i++);
//当pathq[i]!=pathp[i]或者pathq[i]==pathp[i]&&pathp[i]==null时退出
return pathp[--i];
}
public void FindPath(BinaryTreeNode t, BinaryTreeNode p,
BinaryTreeNode[] path, int i) {
if (t == p) {
found = true;
return;
}
path[i] = t;
if (t.getLeftChild() != null)
FindPath(t.getLeftChild(), p, path, i + 1);
if (t.getRightChild() != null && !found)
FindPath(t.getRightChild(), p, path, i + 1);
if (!found)
path[i] = null;// 回溯
}
/**
* (17)非递归复制二叉树
*/
public BinaryTreeNode Bitree_Copy_Nonrecursive(BinaryTreeNode t,
BinaryTreeNode u) {
BinaryTreeNode q;
BinaryTreeNode p;
ArrayStack stack1 = new ArrayStack();
ArrayStack stack2 = new ArrayStack();
stack1.push(t);
u.setElement(t.getElement());
q = u;
stack2.push(u);
while (!stack1.empty()) {
while ((p = (BinaryTreeNode) stack1.peek()) != null) {
q.setLeftChild(new BinaryTreeNode());
q = q.getLeftChild(