文章目录
为什么要引入树？
二叉树 1、概念 1）二叉树 2）满二叉树、完全二叉树
满二叉树：所有叶子节点都在最后一层，并且总节点数为2n-1(n为层数)
完全二叉树：叶子节点在最后一层和倒数第二层，并且最后一层的叶子节点在左边连续，倒数第二层叶子节点在右边连续
前序遍历：先输出父节点、再输出左子树、右子树
中序遍历：先遍历左子树、再遍历父节点、再遍历右子树
后序遍历：先遍历左子树、再遍历右子树、再遍历父节点
tips：遍历的顺序根据父节点的顺序而定
2、前中后序遍历 代码实现
public class BinaryTreeDemo {
public static void main(String[] args) {
// 创建节点
EmpNode node1 = new EmpNode(1,"heroc");
EmpNode node2 = new EmpNode(2,"lucy");
EmpNode node3 = new EmpNode(3,"smith");
EmpNode node4 = new EmpNode(4,"tom");
EmpNode node5 = new EmpNode(5,"jack");
// 创建树
node1.setLeft(node2);
node2.setLeft(node3);
node1.setRight(node4);
node4.setLeft(node5);
// 确定根节点，遍历树
BinaryTree rootNode = new BinaryTree(node1);
// System.out.println("前序：");
// rootNode.perOrder();
// System.out.println("中序：");
// rootNode.centerOrder();
// System.out.println("后序：");
// rootNode.afterOrder();
// 前序遍历查询
EmpNode empNode = rootNode.perOrderFind(5);
if (empNode!=null){
System.out.println(empNode.toString());
}
// 中序遍历查询
empNode = rootNode.perOrderFind(2);
if (empNode!=null){
System.out.println(empNode.toString());
}
// 后序遍历查询
empNode = rootNode.afterOrderFind(4);
if (empNode!=null){
System.out.println(empNode.toString());
}
}
}
// 创建节点
class EmpNode{
private int id;
private String name;
private EmpNode left;
private EmpNode right;
public EmpNode(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public EmpNode getLeft() {
return left;
}
public void setLeft(EmpNode left) {
this.left = left;
}
public EmpNode getRight() {
return right;
}
public void setRight(EmpNode right) {
this.right = right;
}
@Override
public String toString() {
return "EmpNode{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
// 前序遍历
public void perOrder(){
System.out.println(this.toString());
if (this.left!=null){
this.left.perOrder();
}
if (this.right!=null){
this.right.perOrder();
}
}
// 中序遍历
public void centerOrder(){
if (this.left!=null){
this.left.centerOrder();
}
System.out.println(this.toString());
if (this.right!=null){
this.right.centerOrder();
}
}
// 后续遍历
public void afterOrder(){
if (this.left!=null){
this.left.afterOrder();
}
if (this.right!=null){
this.right.afterOrder();
}
System.out.println(this.toString());
}
// 前序遍历查询
public EmpNode perOrderFind(int id){
if (this.id == id){
return this;
}
EmpNode empNode = null;
if (this.left!=null){
empNode = this.left.perOrderFind(id);
}
if (empNode!=null){
return empNode;
}
if (this.right!=null){
empNode = this.right.perOrderFind(id);
}
if (empNode!=null){
return empNode;
}
return null;
}
// 中序遍历查询
public EmpNode centerOrderFind(int id){
EmpNode empNode = null;
// 向左查找
if (this.left!=null){
empNode = this.left.centerOrderFind(id);
}
if (empNode!=null){ // 如果empNode不等null，说明找到了，就返回结果
return empNode;
}
// 当前节点
if (this.id == id){
return this;
}
// 向右查找
if (this.right != null){
empNode = this.right.centerOrderFind(id);
}
if (empNode!=null){
return empNode;
}
// 都没找到返回null
return empNode;
}
// 后序遍历查询
public EmpNode afterOrderFind(int id){
EmpNode empNode = null;
// 向左查找
if (this.left!=null){
empNode = this.left.centerOrderFind(id);
}
if (empNode!=null){ // 如果empNode不等null，说明找到了，就返回结果
return empNode;
}
// 向右查找
if (this.right != null){
empNode = this.right.centerOrderFind(id);
}
if (empNode!=null){
return empNode;
}
// 当前节点
if (this.id == id){
return this;
}
return empNode;
}
}
// 创建根节点
class BinaryTree{
private EmpNode root;
public BinaryTree(EmpNode root) {
this.root = root;
}
public void perOrder(){
if (root!=null){
root.perOrder();
}else {
System.out.println("树为空");
}
}
public void centerOrder(){
if (root!=null){
root.centerOrder();
}else {
System.out.println("树为空");
}
}
public void afterOrder(){
if (root!=null){
root.afterOrder();
}else {
System.out.println("树为空");
}
}
public EmpNode perOrderFind(int id){
if (root!=null){
return root.perOrderFind(id);
}else {
System.out.println("树为空");
return null;
}
}
public EmpNode centerOrderFind(int id){
if (root!=null){
return root.centerOrderFind(id);
}else {
System.out.println("树为空");
return null;
}
}
public EmpNode afterOrderFind(int id){
if (root!=null){
return root.afterOrderFind(id);
}else {
System.out.println("树为空");
return null;
}
}
}
3、顺序存储二叉树
顺序存储二叉树java二叉树遍历算法，是将二叉树顺序存储到数组中，并在遍历数组的时候依旧按照前序遍历、中序遍历、后序遍历。
顺序存储二叉树的特点：
从0开始计算【】叶子节点的操作分析与操作策略（上）
，为了与数组索引保持一致。
代码实现
<p><pre>public class ArrayBinaryTreeDemo {
public static void main(String[] args) {
int arr[] = {1,2,3,4,5,6,7}; // 这是一个二叉树从根节点依次顺序存储的数组
ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
System.out.println("前序遍历：");
arrayBinaryTree.perOrder();
System.out.println("\n中序遍历：");
arrayBinaryTree.infixOrder();
System.out.println("\n后序遍历：");
arrayBinaryTree.suffixOrder();
}}
class ArrayBinaryTree{
int arr[];
public ArrayBinaryTree(int[] arr) {
this.arr = arr;
}
// 前序遍历顺序存储的二叉树数组
public void perOrder(){
perOrder(0);
}
public void perOrder(int index){
System.out.print(arr[index]+" ");
if ((2*index+1)