泥浆比重,木吉他自学教程,刘海珊
二叉树用例
代码解析：
我要评论public class binarytree {
static class treenode {
integer val;
treenode left;
treenode right;
public treenode(integer val) {
this.val = val;
}
}
public static treenode init(integer[] arr, int index) {
treenode node = null;
if (index < arr.length) {
node = new treenode(arr[index]);
node.left = init(arr, 2 * index + 1);
node.right = init(arr, 2 * index + 2);
}
return node;
}
private static list<integer> list = new arraylist<>(10);
public static void main(string[] args) {
integer[] arr = new integer[]{1, 3, 4, 5, 6, 7, 8};
system.out.println("递归实现前序遍历： "+ rootleftrightrecursive(init(arr,0)));
list.clear();
system.out.println("非递归实现前序遍历： "+ rootleftrightnonrecursive(init(arr,0)));
list.clear();
system.out.println();
system.out.println("递归实现中序遍历： "+ leftrootrightrecursive(init(arr,0)));
list.clear();
system.out.println("非递归实现中序遍历： "+ leftrootrightnonrecursive(init(arr,0)));
list.clear();
system.out.println();
system.out.println("递归实现后序遍历： "+ leftrightrootrecursive(init(arr,0)));
list.clear();
system.out.println("非递归实现后序遍历： "+ leftrightrootnonrecursive(init(arr,0)));
list.clear();
system.out.println();
system.out.println("层次遍历： "+ levelorder(init(arr,0)));
system.out.println();
system.out.println("树的深度为： "+ depth(init(arr,0)));
}
/**
* 递归实现前序遍历
* 中-左-右
* @param node treenode
* @return list
*/
public static list rootleftrightrecursive(treenode node) {
if (null != node){
list.add(node.val);
rootleftrightrecursive(node.left);
rootleftrightrecursive(node.right);
}
return list;
}
/**
* 非递归实现前序遍历
* 中-左-右
* @param node treenode
* @return list
*/
public static list rootleftrightnonrecursive(treenode node) {
stack<treenode> stack = new stack<>();
treenode cur = node;
while (null != cur || !stack.isempty()) {
if (null != cur) {
list.add(cur.val);
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
cur = cur.right;
}
}
return list;
}
/**
* 递归实现中序遍历
* 左-中-右
* @param node treenode
* @return list
*/
public static list leftrootrightrecursive(treenode node) {
if (null!=node){
leftrootrightrecursive(node.left);
list.add(node.val);
leftrootrightrecursive(node.right);
}
return list;
}
/**
* 非递归实现中序遍历
* 左-中-右
* @param node treenode
* @return list
*/
public static list leftrootrightnonrecursive(treenode node) {
list<integer> list = new arraylist<>(10);
stack<treenode> stack = new stack<>();
treenode cur = node;
while (null != cur || !stack.isempty()) {
if (null != cur) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
}
/**
* 递归实现后序遍历
* 左-右-中
* @param node treenode
* @return list
*/
public static list leftrightrootrecursive(treenode node){
if (null!=node){
leftrightrootrecursive(node.left);
leftrightrootrecursive(node.right);
list.add(node.val);
}
return list;
}
/**
* 非递归实现后序遍历
* 左-右-中
* @param node treenode
* @return list
*/
public static list leftrightrootnonrecursive(treenode node){
if (null == node){
return list;
}
stack<treenode> stack = new stack<>();
stack.push(node);
treenode cur;
while (!stack.isempty()){
cur = stack.pop();
if (cur.left!=null){
stack.push(cur.left);
}
if (cur.right!=null){
stack.push(cur.right);
}
// 逆序添加
list.add(0,cur.val);
}
return list;
}
/**
* 层序遍历队列实现（广度优先算法bfs）
* @param root treenode
* @return list
*/
public static list<list<integer>> levelorder(treenode root){
list<list<integer>> list = new arraylist<>();
if(root == null){
return list;
}
queue<treenode> queue = new linkedlist<>();
queue.add(root);
while(!queue.isempty()){
int count = queue.size();
list<integer> tmplist = new arraylist<>();
while(count > 0){
treenode node = queue.poll();
tmplist.add(node.val);
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
count--;
}
list.add(tmplist);
}
return list;
}
/**
* 递归实现获取树的深度
* @param node treenode
* @return int
*/
public static int depth(treenode node){
if (node == null){
return 0;
}
int left = depth(node.left);
int right = depth(node.right);
return left > right ? left + 1 : right + 1;
}
}
结果为：
递归实现前序遍历： [1, 3, 5, 6, 4, 7, 8] 非递归实现前序遍历： [1, 3, 5, 6, 4, 7, 8] 递归实现中序遍历： [5, 3, 6, 1, 7, 4, 8] 非递归实现中序遍历： [5, 3, 6, 1, 7, 4, 8] 递归实现后序遍历： [5, 6, 3, 7, 8, 4, 1] 非递归实现后序遍历： [5, 6, 3, 7, 8, 4, 1] 层次遍历： [[1], [3, 4], [5, 6, 7, 8]] 树的深度为： 3
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
apollo与springboot集成实现动态刷新配置的教程详解
网友评论