1> 内部类
a) 二叉树节点内部类：BiTNode.class
b) 队列内部类：Queue.class
2> 二叉树一些操作
a) 根据补齐叶子节点后的先序遍历结果构造二叉树：creatBiTree(Queue
b) 前序遍历（递归）二叉树：preOrderTraverse(BiTNode t)
c) 中序遍历（递归）二叉树：inOrderTraverse(BiTNode t)
d) 后序遍历（递归）二叉树：postOrderTraverse(BiTNode t)
e) 中序遍历（栈）二叉树：inTraverse(BiTNode t)
f) 层次遍历二叉树：traverse(BiTNode t)
g) 复制二叉树：copy(BiTNode t)
h) 获取二叉树节点总数：getNodesCount(BiNode t)
i) 获取二叉树叶子节点数：getLeafNodesCount(BiTNode t)
j) 获取二叉树的深度：getDepth(BiTNode t)
2）代码实现public class BiTree {
// 测试方法
public static void main(String[] args) {
// 输入控制
Scanner in = new Scanner(System.in);
System.out.print("请输入先序序列，叶子节点以【#】补齐：");
char[] nodes = in.nextLine().toCharArray();
// 二叉树节点信息保存在队列中
Queue q = new Queue<>(100);
for (char c: nodes){
q.enter(c);
}
// 构造二叉树
BiTNode t = creatBiTree(q);
// 递归遍历二叉树
System.out.print("先序遍历结果：");
preOrderTraverse(t);
System.out.println("");// 换行
System.out.print("中序遍历结果：");
inOrderTraverse(t);
System.out.println("");// 换行
System.out.print("后序遍历结果：");
postOrderTraverse(t);
System.out.println("");// 换行
// 非递归中序遍历
System.out.print("非递归中序遍历结果：");
inTraverse(t);
System.out.println("");// 换行
// 层次遍历（逐层自左往右遍历每个节点）
System.out.print("层次遍历结果：");
traverse(t);
System.out.println("");// 换行
// 复制二叉树并前序输出
BiTNode newT = copy(t);
System.out.print("复制得到的二叉树先序遍历结果：");
preOrderTraverse(newT);
System.out.println("");// 换行
// 计算二叉树所有的节点数
int nodesCount = getNodesCount(t);
System.out.println("所有的节点数是：" + nodesCount);
// 计算二叉树叶子节点数
int leafNodesCount = getLeafNodesCount(t);
System.out.println("叶子节点数是：" + leafNodesCount);
// 计算二叉树的深度
int depth = getDepth(t);
System.out.println("二叉树的深度是：" + depth);
}
private static BiTNode creatBiTree(Queue q){
BiTNode t = null;
char c = q.out();
if (c == '#'){
return null;
}else {
t = new BiTNode(c);
t.lChild = creatBiTree(q);
t.rChild = creatBiTree(q);
return t;
}
}
private static void preOrderTraverse(BiTNode t){
if (t == null){
return;
}else {
System.out.print(t.data + " ");
preOrderTraverse(t.lChild);
preOrderTraverse(t.rChild);
}
}
private static void inOrderTraverse(BiTNode t){
if (t == null){
return;
}else {
inOrderTraverse(t.lChild);
System.out.print(t.data + " ");
inOrderTraverse(t.rChild);
}
}
private static void postOrderTraverse(BiTNode t){
if (t == null){
return;
}else{
postOrderTraverse(t.lChild);
postOrderTraverse(t.rChild);
System.out.print(t.data + " ");
}
}
private static void inTraverse(BiTNode t) {
BiTNode p = t;
Stack stack = new Stack<>();
while (p!=null || !stack.empty()){
if (p != null){
stack.push(p);
p = p.lChild;
}else {
BiTNode q = stack.pop();
System.out.print(q.data + " ");
p = q.rChild;
}
}
}
private static void traverse(BiTNode t) {
Queue q = new Queue<>(100);
q.enter(t);
while (!q.isEmpty()){
BiTNode temp = q.out();
System.out.print(temp.data + " ");
if (temp.lChild != null){
q.enter(temp.lChild);
}
if (temp.rChild != null){
q.enter(temp.rChild);
}
}
}
private static BiTNode copy(BiTNode t) {
BiTNode newT = null;
if (t == null){
return null;
}else {
newT = new BiTNode(t.data);
newT.lChild = copy(t.lChild);
newT.rChild = copy(t.rChild);
return newT;
}
}
private static int getNodesCount(BiTNode t) {
if (t == null){
return 0;
}else {
return getNodesCount(t.lChild)+getNodesCount(t.rChild)+1;
}
}
private static int getLeafNodesCount(BiTNode t) {
if (t == null){
return 0;
}else if (t.lChild==null && t.rChild==null){
return 1;
}else {
return getLeafNodesCount(t.lChild)+getLeafNodesCount(t.rChild);
}
}
private static int getDepth(BiTNode t) {
if (t == null){
return 0;
}else {
int lDepth = getDepth(t.lChild);
int rDepth = getDepth(t.rChild);
if (lDepth > rDepth){
return lDepth+1;
}else {
return rDepth+1;
}
}
}
// 节点类
static class BiTNode{
char data;
BiTNode lChild;
BiTNode rChild;
public BiTNode(char data) {
this.data = data;
}
}
// 队列
static class Queue{
int maxSize;
Object[] arr;
int rear;
int front;
public Queue(int maxSize) {
this.maxSize = maxSize;
arr = new Object[maxSize];
rear = 0;
front = 0;
}
boolean isEmpty(){
return rear==front;
}
boolean isFull(){
return (rear+1)%maxSize==front;
}
void enter(E e){
if (isFull()){
throw new RuntimeException("队列已满！");
}
arr[rear] = e;
rear = (rear+1)%maxSize;
}
E out(){
if (isEmpty()){
throw new RuntimeException("队列为空！");
}
E e = (E) arr[front];
front = (front+1)%maxSize;
return e;
}
}
}
三、测试
