直接上代码：
package org.meter.demo.sort;
import lombok.extern.log4j.Log4j2;
import java.util.ArrayDeque;
/**
* 广度优先和深度优先算法模拟
* 广度优先采用队列
* 深度优先采用栈
*/
@Log4j2
public class DeepWidthSearch {
static class TreeNode {
int value;
TreeNodeleft;
TreeNoderight;
public TreeNode(int value) {
this.value = value;
}
}
TreeNoderoot;
public DeepWidthSearch(int[] array) {
root =makeBinaryTreeByArray(array, 1);
}
/**
* 采用递归的方式创建一颗二叉树
* 传入的是二叉树的数组表示法
* 构造后是二叉树的二叉链表表示法
*/
public static TreeNodemakeBinaryTreeByArray(int[] array, int index) {
if (index < array.length) {
int value = array[index];
if (value !=0) {
TreeNode t =new TreeNode(value);
array[index] =0;
t.left =makeBinaryTreeByArray(array, index *2);
t.right =makeBinaryTreeByArray(array, index *2 +1);
return t;
}
}
return null;
}
/**
* 深度优先遍历，相当于先根遍历
* 采用非递归实现
* 需要辅助数据结构：栈
*/
public void depthDegreeSrarch() {
if (root ==null) {
logger.info("empty tree");
return;
}
ArrayDeque stack =new ArrayDeque();
stack.push(root);
while (stack.isEmpty() ==false) {
TreeNode node = stack.pop();
logger.info("深度优先遍历："+node.value +" ");
if (node.right !=null) {
stack.push(node.right);
}
if (node.left !=null) {
stack.push(node.left);
}
}
logger.info("-------------------------------------------------------------");
}
/**
* 广度优先遍历
* 采用非递归实现
* 需要辅助数据结构：队列
*/
public void widthDegreeSearch() {
if (root ==null) {
logger.info("empty tree");
return;
}
ArrayDeque queue =new ArrayDeque();
queue.add(root);
while (queue.isEmpty() ==false) {
TreeNode node = queue.remove();
logger.info("广度优先："+node.value +" ");
if (node.left !=null) {
queue.add(node.left);
}
if (node.right !=null) {
queue.add(node.right);
}
}
logger.info("------------------------------------------------");
}
public static void main(String[] args) {
int[] arr = {0, 13, 65, 5, 97, 25, 0, 37, 22, 0, 4, 28, 0, 0, 32, 0};
DeepWidthSearch tree =new DeepWidthSearch(arr);
tree.depthDegreeSrarch();
tree.widthDegreeSearch();
}
}
测试数据以及测试结果：
测试数据
测试结果
网友评论