@Data
@NoArgsConstructor
@AllArgsConstructor
public class BiTree {
private BiTree lChild, rChild;
private int data;
//先序周遊
public static void PreOrder(BiTree tree) {
BiTree[] stack = new BiTree[MAX];
int top = -1;
stack[++top] = tree;
while (top != -1) {
BiTree p = stack[top--];
while (p != null) {
print(p);
if (p.rChild != null) {
stack[++top] = p.rChild;
}
p = p.lChild;
}
}
}
//中序周遊
public static void InOrder(BiTree tree) {
BiTree[] stack = new BiTree[MAX];
int top = -1;
BiTree p = tree;
while (p != null || top != -1) {
if (p != null) {
stack[++top] = p;
p = p.lChild;
} else {
p = stack[top--];
print(p);
p = p.rChild;
}
}
}
static class SNode {
int flag = 0; //用來記錄該節點是否輸出 0表示未輸出 1表示已經輸出
BiTree p;
public SNode(BiTree p) {
this.p = p;
}
}
//後序周遊
public static void PostOrder(BiTree tree) {
SNode[] stack = new SNode[MAX];
int top = -1;
BiTree p = tree;
while (p != null || top != -1) {
while (p != null) {
SNode node = new SNode(p);
stack[++top] = node;
p = p.lChild;
}
SNode node = stack[top--];
if (node.flag == 0) {
node.flag = 1;
stack[++top] = node;
p = node.p.rChild;
} else {
print(node.p);
}
}
}
//層級周遊
public static void LevelOrder(BiTree tree) {
BiTree[] queue = new BiTree[MAX];
int front = 0, rear = 0;
queue[rear++] = tree;
while (front < rear) {
BiTree p = queue[front++];
print(p);
if (p.lChild != null)
queue[rear++] = p.lChild;
if (p.rChild != null)
queue[rear++] = p.rChild;
}
}
//統計葉子節點(遞歸)
public static int leafCount(BiTree tree) {
int count = 0;
if (tree == null) {
return count;
} else if (tree.lChild == null && tree.rChild == null) {
count = 1;
} else {
count = leafCount(tree.lChild) + leafCount(tree.rChild);
}
return count;
}
//統計非葉子節點(遞歸)
public static int noLeafCount(BiTree tree) {
int count = 0;
if (tree == null) {
return count;
} else if (tree.lChild != null || tree.rChild != null) {
count = 1;
if (tree.lChild != null)
count += noLeafCount(tree.lChild);
if (tree.rChild != null)
count += noLeafCount(tree.rChild);
}
return count;
}
//統計各種節點(非遞歸)
public static int LeafCount(BiTree tree) {
if (tree == null)
return 0;
int count = 0;
int top = -1;
BiTree[] stack = new BiTree[MAX];
stack[++top] = tree;
while (top != -1) {
BiTree p = stack[top--];
//if(p.lChild!=null || p.rChild!=null)//統計非葉子節點
//if(p.lChild!=null && p.rChild!=null)//統計有兩個孩子的節點
//if ((p.lChild != null && p.rChild == null) || (p.lChild == null && p.rChild != null)) //統計隻有一個孩子的節點
if (p.lChild == null && p.rChild == null)//統計葉子節點
count++;
if (p.lChild != null)
stack[++top] = p.lChild;
if (p.rChild != null)
stack[++top] = p.rChild;
}
return count;
}
//統計二叉樹的高度
public static int TreeHigh(BiTree tree) {
int leftHigh, rightHigh, maxHigh;
if (tree == null) {
return 0;
} else {
leftHigh = TreeHigh(tree.lChild);
rightHigh = TreeHigh(tree.rChild);
maxHigh = leftHigh > rightHigh ? leftHigh : rightHigh;
return maxHigh + 1;
}
}
public static int treeHigh(BiTree tree) {
BiTree[] queue = new BiTree[MAX];
int front = 0, rear = 0;
queue[rear++] = tree;
int level = 1, high = 0;
while (front < rear) {
BiTree p = queue[front++];
if (p.lChild != null)
queue[rear++] = p.lChild;
if (p.rChild != null)
queue[rear++] = p.rChild;
if (front == level) {
high++;
level = rear;
}
}
return high;
}
//統計二叉樹的寬度
//判斷二叉樹的是否是完全二叉樹
private static int MAX = 10;
public static void main(String[] args) {
BiTree biTree = init();
PreOrder(biTree);
System.out.println();
InOrder(biTree);
System.out.println();
PostOrder(biTree);
System.out.println();
LevelOrder(biTree);
System.out.println();
System.out.println("葉子節點個數: " + leafCount(biTree));
System.out.println("非葉子節點個數: " + noLeafCount(biTree));
System.out.println("葉子節點個數: " + LeafCount(biTree));
System.out.println("遞歸樹的高度: " + TreeHigh(biTree));
System.out.println("非遞歸樹的高度: " + treeHigh(biTree));
}
private static void print(BiTree p) {
System.out.print(p.data + " ");
}
public BiTree(int data) {
this.data = data;
}
private static BiTree init() {
BiTree biTree = new BiTree();
biTree.setData(1);
BiTree tow = new BiTree(2);
BiTree three = new BiTree(3);
BiTree four = new BiTree(4);
BiTree five = new BiTree(5);
BiTree six = new BiTree(6);
BiTree seven = new BiTree(7);
biTree.setLChild(tow);
biTree.setRChild(three);
tow.setLChild(four);
tow.setRChild(five);
three.setLChild(six);
three.setRChild(seven);
return biTree;
}
}