1. 二叉树节点
package entity;
public class TreeNode {
//数据域
public int val;
//左孩子
public TreeNode left;
//右孩子
public TreeNode right;
//构造函数1
public TreeNode(int val) {
this.val = val;
}//构造函数2
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
2. 二叉树实现 【Java实现数据结构|Java层次创建二叉树，前序、中序、后序、层序遍历二叉树的非递归实现，获得二叉树的高度】代码中包含如下方法：
- 层次建立二叉树（-1代表null节点）
- 前序遍历递归实现
- 中序遍历递归实现
- 后续遍历递归实现
- 层序遍历实现
- 前序遍历非递归实现
- 中序遍历非递归实现
- 后序遍历非递归实现
- 二叉树的高度
- 输出叶子节点
package entity;
import java.util.*;
public class BinaryTree {
//层次建立二叉树
public TreeNode createBinaryTree(int[] nums) {
//队列
Queue queue = new LinkedList<>();
//创建根节点
TreeNode root = null;
//创建指针节点
TreeNode node = null;
//数组下标
int index = 0;
//边界判断一下
if (nums == null || nums.length == 0) {
return root;
} else {
root = new TreeNode(nums[index++]);
queue.offer(root);
}while (index != nums.length) {
node = queue.poll();
//拼上左节点
if (nums[index] != -1) {
node.left = new TreeNode(nums[index]);
queue.offer(node.left);
}
index++;
if (index != nums.length) {
if (nums[index] != -1) {
node.right = new TreeNode(nums[index]);
queue.offer(node.right);
}
index++;
}
}
return root;
}//前序遍历实现
public void preorderTraversal(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preorderTraversal(root.left);
preorderTraversal(root.right);
}//中序遍历
public void inorderTraversal(TreeNode root) {
if (root == null) {
return;
}
inorderTraversal(root.left);
System.out.print(root.val + " ");
inorderTraversal(root.right);
}//后序遍历
public void postorderTraversal(TreeNode root) {
if (root == null) {
return;
}
postorderTraversal(root.left);
postorderTraversal(root.right);
System.out.print(root.val + " ");
}//层序遍历
public List levelorderTraversal(TreeNode root) {
List list = new ArrayList<>();
if (root == null) return list;
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0;
i < size;
i++) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return list;
}//前序遍历非递归实现
public List preorderTraversal1(TreeNode root) {
//非递归实现的本质是栈
Deque stack = new LinkedList<>();
List list = new ArrayList<>();
while (!stack.isEmpty() || root != null) {
while (root != null) {
list.add(root.val);
stack.push(root);
root = root.left;
}
root = stack.poll();
root = root.right;
}
return list;
}//中序遍历非递归实现
public List inorderTraversal1(TreeNode root) {
//非递归实现的本质是栈
Deque stack = new LinkedList<>();
List list = new ArrayList<>();
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.poll();
list.add(root.val);
root = root.right;
}
return list;
}//后序遍历非递归实现
public List postorderTraversal1(TreeNode root) {
//非递归实现的本质是栈
Deque stack = new LinkedList<>();
List list = new ArrayList<>();
TreeNode prev = null;
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
//取出最左下节点
root = stack.poll();
if (root.right == prev || root.right == null) {
list.add(root.val);
prev = root;
//如果不置为null为被再压栈，比如一颗二叉树只有权值为1的根节点
root = null;
} else {
stack.push(root);
root = root.right;
}
}
return list;
}//返回树的高度
public int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
int lHeight = getHeight(root.left);
int rHeight = getHeight(root.right);
return lHeight > rHeight ? lHeight + 1 : rHeight + 1;
}//输出叶子节点
public List printLeaves(TreeNode root) {
List list = new ArrayList<>();
if (root == null) {
return list;
}
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0;
i < size;
i++) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) {
list.add(node.val);
}if (node.left != null) {
queue.offer(node.left);
}if (node.right != null) {
queue.offer(node.right);
}
}
}
return list;
}
}
3. 二叉树测试代码
package test;
import entity.BinaryTree;
import entity.TreeNode;
public class BinaryTreeTest {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
int[] nums = {1, 2, 3, -1, 2, 5, -1};
TreeNode root = binaryTree.createBinaryTree(nums);
binaryTree.preorderTraversal(root);
System.out.println();
binaryTree.inorderTraversal(root);
System.out.println();
binaryTree.postorderTraversal(root);
System.out.println();
BinaryTree binaryTree1 = new BinaryTree();
int[] nums1 = {1, 2, 3, -1, 2, 5, -1, 2, 2, 3, 4, 5, 6, -1, -1, -1, -1, -1, -1, 2};
TreeNode root1 = binaryTree.createBinaryTree(nums1);
System.out.println(binaryTree.preorderTraversal1(root1));
System.out.println(binaryTree.inorderTraversal1(root1));
System.out.println(binaryTree.postorderTraversal1(root1));
System.out.println(binaryTree.getHeight(root1));
System.out.println(binaryTree.levelorderTraversal(root1).toString());
System.out.println(binaryTree.printLeaves(root1).toString());
}
}
