q:计算下二叉树的节点:
a:可以用递归,
q:递归堆栈利用高,时间复杂度高,不要用递归
a:emmmmmm… 请看下文
package com.gjw.datastruts_Alg.binarytree;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
@Data
@NoArgsConstructor
@AllArgsConstructor
public class BiTree {
private BiTree lChild, rChild;
private int data;
public BiTree(int data) {
this.data = 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 + " ");
}
private static BiTree init() {
BiTree biTree = new BiTree();
biTree.setData(1);
BiTree two = 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(two);
biTree.setRChild(three);
two.setLChild(four);
two.setRChild(five);
three.setLChild(six);
three.setRChild(seven);
return biTree;
}
}