} else {// 当前层未统计完毕
numOfNodes++;
if (p.getLeftChild() != null)
q.put(p.getLeftChild());
if (p.getRightChild() != null)
q.put(p.getRightChild());
}
}
}
/*
* (4)使用前序遍历制作二叉树的副本
*/
public static BinaryTreeNode preOrderClone(BinaryTreeNode t) {
if (t != null) {
BinaryTreeNode ct = new BinaryTreeNode(t.getElement());
ct.setLeftChild(preOrderClone(t.getLeftChild()));
ct.setRightChild(preOrderClone(t.getRightChild()));
return ct;
} else
return null;
}
/*
* (5)使用后序遍历制作二叉树的副本
*/
public static BinaryTreeNode postOrderClone(BinaryTreeNode t) {
if (t != null) {
BinaryTreeNode cLeft = postOrderClone(t.getLeftChild());
BinaryTreeNode cRight = postOrderClone(t.getRightChild());
return new BinaryTreeNode(t.getElement(), cLeft, cRight);
} else
return null;
}
/**
* (6)判断结点u是否为结点v的子孙
*
* @param u
* 节点u
* @param v
* 节点v
* @return 如果u是节点v的子孙，则返回true，否则返回false
*/
public static boolean Is_Descendant(BinaryTreeNode u, BinaryTreeNode v) {
if (u == v)
return true;
else {
if (v.getLeftChild() != null)
if (Is_Descendant(u, v.getLeftChild()))
return true;
if (v.getRightChild() != null)
if (Is_Descendant(u, v.getRightChild()))
return true;
}
return false;
/**
* (7)判断两棵二叉树是否相似
*
* @param b1
* 第一课二叉树的根节点
* @param b2
* 第二课二叉树的根节点
* @return 如果两棵二叉树相似则返回true，否则false
*/
public boolean Bitree_sim(BinaryTreeNode b1, BinaryTreeNode b2) {
if (b1 == null && b2 == null)
return true;
else if (b1 != null && b2 != null
&& Bitree_sim(b1.getLeftChild(), b2.getLeftChild())
&& Bitree_sim(b1.getRightChild(), b2.getRightChild()))
return true;
else
return false;
}
/**
* (8)中序遍历二叉树的非递归算法
*
* @param t
* 被遍历的二叉树根节点
*/
public static void InOrderTraverse(BinaryTreeNode t) {
ArrayStack stack = new ArrayStack();// 辅助栈
BinaryTreeNode p = t;// 当前考虑子树的根节点
// 当p==null并且stack.empty()为true时退出while循环
while (p != null || !stack.empty()) {
// 沿着左孩子路径循环走到“最左边”
if (p != null) {// 当前子树不为空
stack.push(p);// 当前结点入栈
p = p.getLeftChild();// 获取当前结点的左孩子
} else {// p==null,当前子树为空
p = (BinaryTreeNode) stack.pop();// 出栈
System.out.print(p.getElement().toString() + " ");
p = p.getRightChild();// 获取当前结点的右孩子
}
}
}
/**
* (9)中序遍历二叉树的非递归算法2
*
* @param t
* 被遍历的二叉树根节点
*/
public static void InOrderTraverse2(BinaryTreeNode t) {
ArrayStack stack = new ArrayStack();
BinaryTreeNode p;// 当前考虑节点
stack.push(t);
while (!stack.empty()) {
// 沿着左孩