二叉树数据结构
二叉树数据结构
由于在LeetCode上刷题时遇到二叉树的问题都会非常头疼，因为二叉树的数据结构在本机没有实现。因此此类编程题目无法在本机进行运行，更无法改错啦！为了解决这个麻烦，于是自己简单实现了一个二叉树的数据结构，构造参数通过Object数组进行初始化。toString()中集成了层序遍历、前序遍历、中序遍历和后序遍历。
前序遍历
采用递归法进行前序遍历
private List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
preorder(root,list);
return list;
}
private void preorder(TreeNode root,List<Integer> list) {
if(root != null){
list.add(root.val);
preorder(root.left,list);
preorder(root.right,list);
}
} 中序遍历
采用迭代法+栈进行中序遍历
private List<Integer> inorderTraversal(TreeNode root) {
List<Integer>list = new ArrayList<>();
if(root==null)return list;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (!stack.isEmpty()|| cur != null){
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
} 后序遍历
采用迭代法+自定义数据结构Command进行后续遍历
private List<Integer> postorderTraversal(TreeNode root) {
List<Integer>list = new ArrayList<>();
if(root==null)return list;
Stack<Command> stack = new Stack<>();
stack.push(new Command("go",root));
while (!stack.isEmpty()){
Command cur = stack.pop();
if(cur.message.equals("print")){
list.add(cur.node.val);
}else{
stack.push(new Command("print",cur.node));
if(cur.node.right!=null)stack.push(new Command("go",cur.node.right));
if(cur.node.left!=null)stack.push(new Command("go",cur.node.left));
}
}
return list;
}
/**
* @Author CourageHe
* @Description 后续遍历的辅助数据结构，可通过Pair代替
* @Date 2020/6/9 0:33
**/
private class Command {
String message;
TreeNode node;
Command(String message, TreeNode node) { this.message = message;this.node = node;}
} 层序遍历
采用迭代法+队列 进行层序遍历
private List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
Queue<Pair<TreeNode,Integer>> queue = new ArrayDeque<>();
queue.add(new Pair<>(root,0));
while (!queue.isEmpty()){
TreeNode node = queue.peek().getKey();
int level = queue.peek().getValue();
queue.poll();
//如果节点为空，则跳过
if(node == null) continue;
//如果该层没有列表 则新建
if(level == list.size())
list.add(new ArrayList<>());
list.get(level).add(node.val);
queue.add(new Pair<>(node.left,level+1));
queue.add(new Pair<>(node.right,level+1));
}
return list;
} 完整代码
import javafx.util.Pair;
import java.util.*;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
private Queue<TreeNode> queue = new ArrayDeque<>();
public TreeNode(int x) {
val = x;
}
//根据n个元素的数组arr创建一个链表
//使用arr为参数，创建另外一个listnode的构造函数
public TreeNode(Object[] arr) {
this.val = (int)arr[0];
TreeNode cur = this;
for (int i = 1; i < arr.length; i+=2) {
if(arr[i] != null ){
cur.left = new TreeNode((int)arr[i]);
queue.add(cur.left);
}
if(arr[i+1] != null ){
cur.right = new TreeNode((int)arr[i+1]);
queue.add(cur.right);
}
cur = queue.poll();
}
}
@Override
public String toString() {
StringBuilder s = new StringBuilder();
s.append("层序遍历："+levelOrder(this)+"\n");
s.append("前序遍历："+preorderTraversal(this)+"\n");
s.append("中序遍历："+inorderTraversal(this)+"\n");
s.append("后序遍历："+postorderTraversal(this)+"\n");
return s.toString();
}
/**
* @Author CourageHe
* @Description 树的层序遍历
* @Date 2020/6/9 0:09
* @Param [root]
* @return java.util.List<java.util.List<java.lang.Integer>>
**/
private List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
Queue<Pair<TreeNode,Integer>> queue = new ArrayDeque<>();
queue.add(new Pair<>(root,0));
while (!queue.isEmpty()){
TreeNode node = queue.peek().getKey();
int level = queue.peek().getValue();
queue.poll();
//如果节点为空，则跳过
if(node == null) continue;
//如果该层没有列表 则新建
if(level == list.size())
list.add(new ArrayList<>());
list.get(level).add(node.val);
queue.add(new Pair<>(node.left,level+1));
queue.add(new Pair<>(node.right,level+1));
}
return list;
}
/**
* @Author CourageHe
* @Description 树的前序遍历
* @Date 2020/6/9 0:14
* @Param [root]
* @return java.util.List<java.lang.Integer>
**/
private List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
preorder(root,list);
return list;
}
private void preorder(TreeNode root,List<Integer> list) {
if(root != null){
list.add(root.val);
preorder(root.left,list);
preorder(root.right,list);
}
}
/**
* @Author CourageHe
* @Description 中序遍历
* @Date 2020/6/9 0:29
* @Param [root]
* @return java.util.List<java.lang.Integer>
**/
private List<Integer> inorderTraversal(TreeNode root) {
List<Integer>list = new ArrayList<>();
if(root==null)return list;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (!stack.isEmpty()|| cur != null){
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
}
/**
* @Author CourageHe
* @Description 树的后序遍历
* @Date 2020/6/9 0:31
* @Param [root]
* @return java.util.List<java.lang.Integer>
**/
private List<Integer> postorderTraversal(TreeNode root) {
List<Integer>list = new ArrayList<>();
if(root==null)return list;
Stack<Command> stack = new Stack<>();
stack.push(new Command("go",root));
while (!stack.isEmpty()){
Command cur = stack.pop();
if(cur.message.equals("print")){
list.add(cur.node.val);
}else{
stack.push(new Command("print",cur.node));
if(cur.node.right!=null)stack.push(new Command("go",cur.node.right));
if(cur.node.left!=null)stack.push(new Command("go",cur.node.left));
}
}
return list;
}
/**
* @Author CourageHe
* @Description 后续遍历的辅助数据结构，可通过Pair代替
* @Date 2020/6/9 0:33
**/
private class Command {
String message;
TreeNode node;
Command(String message, TreeNode node) {
this.message = message;this.node = node;
}
}
public static void main(String[] args) {
Object []arr = {3,9,20,null,null,15,7};
TreeNode root = new TreeNode(arr);
System.out.println(root);
}
}
