一、生成二叉树
生成目标
新建一个类：
public class BinaryNode {
public int value = 0;
public BinaryNode left;
public BinaryNode right;
public BinaryNode(int value) {
this.value = value;
}
}
生成二叉树方法：
public class BinaryTreeUtils {
public static void createBinaryTree(BinaryNode root, int[] array) {
root.value = array.length > 0 ? array[0] : -1;
for (int i = 1; i < array.length; i++) {
insertBinaryTreeNode(root, array[i]);
}
}
private static void insertBinaryTreeNode(BinaryNode root, int value) {
if (root.value >= value) {
if (root.left == null) {
root.left = new BinaryNode(value);
return;
} else {
insertBinaryTreeNode(root.left, value);
}
} else {
if (root.right == null) {
root.right = new BinaryNode(value);
return;
} else {
insertBinaryTreeNode(root.right, value);
}
}
}
}
生成二叉树：
public static void main(String[] args) {
int [] array = {8,3,5,20,15,2,29,1,4,6,13,16,21,30};
BinaryNode root = new BinaryNode(0);
BinaryTreeUtils.createBinaryTree(root,array);
}
二、广度优先遍历
广度优先遍历，也可以称为层次优先遍历，从上到下，先把每一层遍历完之后再遍历一下一层。如上图，我们先遍历第一层：8，再遍历第二层： 2、20，接着第三层：2、5、15、29以此类推.....
我们可以在遍历开始时把根节点放在队列里，然后在循环里面取出节点，访问其值，并且把左右节点放入队列，以此类推。
//广度优先遍历
public static void printBinaryTreeWidthFirst(BinaryNode root)
{
Queue queue = new LinkedList();
if (root != null)
{
queue.add(root);
}
while (!queue.isEmpty()){
root = (BinaryNode) queue.poll();
System.out.print(root.value + " ");
if (root.left != null)
{
queue.offer(root.left);
}
if (root.right != null)
{
queue.offer(root.right);
}
}
}
三、深度优先遍历
顾名思义，就是沿着一个方向一直向下遍历，比较简单
//深度优先遍历
public static void printBinaryTreeDepthFirst(BinaryNode root)
{
Stack stack = new Stack();
stack.push(root);
while (!stack.isEmpty())
{
root = (BinaryNode) stack.pop();
System.out.print(root.value + " ");
if (root.right != null)
{
stack.push(root.right);
}
if (root.left != null)
{
stack.push(root.left);
}
}
}
四、深度计算
//计算深度
public static int calculateDepthBinaryTree(BinaryNode root)
{
if (root == null)
{
return 0;
}
int left = calculateDepthBinaryTree(root.left);
int right = calculateDepthBinaryTree(root.right);
return Math.max(left,right) + 1;
}
测试代码：
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] array = {8,3,5,20,15,2,29,1,4,6,13,16,21,30};
BinaryNode root = new BinaryNode(0);
BinaryTreeUtils.createBinaryTree(root,array);
System.out.println("广度优先遍历：");
BinaryTreeUtils.printBinaryTreeWidthFirst(root);
System.out.println("");
System.out.println("深度优先遍历：");
BinaryTreeUtils.printBinaryTreeDepthFirst(root);
System.out.println("");
System.out.println("深度：" + BinaryTreeUtils.calculateDepthBinaryTree(root));
;
}
结果：
结果
