if (t.getRightChild() != null)
q.put(t.getRightChild());
// get next node to visit
t = (BinaryTreeNode) q.get();
}
}
/** output elements in preorder */
public void preOrderOutput() {
preOrder(theOutput);
}
/** output elements in inorder */
public void inOrderOutput() {
inOrder(theOutput);
}
/** output elements in postorder */
public void postOrderOutput() {
postOrder(theOutput);
}
/** output elements in level order */
public void levelOrderOutput() {
levelOrder(theOutput);
}
/** count number of nodes in tree */
public int size() {
count = 0;
preOrder(theAdd1);
return count;
}
/**
* 返回二叉树的高度
*
* @return 二叉树的高度
*/
public int height() {
return theHeight(getRoot());
}
/**
* 返回以指定结点为根的二叉树的高度
*
* @param t
* 二叉树的根节点
* @return 二叉树的高度
*/
static int theHeight(BinaryTreeNode t) {
if (t == null)
return 0;
int hl = theHeight(t.getLeftChild());
int hr = theHeight(t.getRightChild());
if (hl > hr)
return ++hl;
else
return ++hr;
}
}
[java]
/**
* 二叉树问题集锦
* @author Sking
*/
package 树.二叉树.二叉树问题总结;
import 栈.ArrayStack;
import 树.二叉树.链接二叉树.LinkedBinaryTree;
import 队列.ArrayQueue;
public class BinaryTreeQuestion {
/**
* (1) 输出完全括弧化的中序遍历形式
*
* @param t
* 被遍历的二叉树根节点
*/
public static void infix(BinaryTreeNode t) {
if (t != null) {
System.out.print("(");
infix(t.getLeftChild());
System.out.print(t.getElement().toString());
infix(t.getRightChild());
System.out.print(")");
}
}
/**
* (2)确定链接二叉树的高度
*
* @param t
* 指定的二叉树根节点
* @return 二叉树的高度
*/
public static int height(BinaryTreeNode t) {
if (t != null) {
int hLeft = height(t.getLeftChild());
int hRight = height(t.getRightChild());
return Math.max(hLeft, hRight) + 1;
} else
return 0;
}
/**
* (3)确定链接二叉树节点数最多的层，根为第一层
*
* @param t
* 指定二叉树的根节点
* @return 连接二叉树节点最多的层
*/
public static int maxLevel(BinaryTreeNode t) {
if (t == null)
return 0;
int maxLevel = 0;// 当前结点个数对多的层
int maxNodes = 0;// 当前单层最大节点个数
// endOfLevel表示层结束标记
BinaryTreeNode endOfLevel = new BinaryTreeNode();
ArrayQueue q = new ArrayQueue();
q.put(t);
q.put(endOfLevel);// 加入第一层的结束标记
int currentLevel = 1;// currentLevel表示当前层
int numOfNodes = 0;// 当前层的节点个数
while (true) {
BinaryTreeNode p = (BinaryTreeNode) q.get();
if (p == endOfLevel) {// 当前层统计结束
if (numOfNodes > maxNodes) {
maxNodes = numOfNodes;
maxLevel = currentLevel;
} else if (numOfNodes == 0)
return maxLevel;// 底层统计结束
currentLevel++;
numOfNodes = 0;
// 每当统计完一层时，都要为下一层加入标记endOfLevel
// (此时下一层的结点已经全部在队列当中，层序遍历的结果）