Java学习笔记（五）- 手写二叉树排序

学习的最好方式就是写出来

欢迎光临我的个人小窝：http://wsfss.top

今天我们就手撸一个二叉树排序吧

先来看看二叉树的相关知识

• 每个节点最多只有2个子节点
• 遍历元素口诀：前序遍历，根->左->右、中序遍历，左->根->右、后序遍历，左->右->根
• 排序机制：依次从根节点往下比较，小于当前节点值则走左子节点，大于当前节点值则走右子节点，然后用中序遍历

1、下面对一组数字进行排序：4、2、1、5、3、6，按排序机制添加元素，结果如下图

1.png

2、然后使用中序遍历

2.png

3、接下来通过代码实现

package com.fss.util.tree.binarytree.impl;

import com.fss.util.tree.binarytree.Tree;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class BinaryTreeSort implements Tree<Integer> {

    // 根节点
    private Node<Integer> root;

    public BinaryTreeSort() {
    }

    /**
     * 依次从根节点往下比较，小于当前节点值则走左子节点，大于当前节点值则走右子节点
     */
    @Override
    public boolean add(Integer i) {
        Node<Integer> node = new Node<>(i);
        // 根节点不存在
        if (root == null) {
            root = node;
            return true;
        }
        Node<Integer> newNode = new Node<>(i, null, null);
        Node<Integer> parent = parent(null, i);
        if (Integer.compare(i, parent.value) == -1) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }

        return true;
    }

    /**
     * 利用中序遍历来排序
     */
    @Override
    public void sort(List<Integer> list) {
        list.forEach(v -> {
            add(v);
        });
        List<Integer> sortList = new ArrayList<>();
        ldr(root, sortList);
        System.out.println("sortList: "+ sortList.stream().map(v -> String.valueOf(v)).collect(Collectors.joining(",")));
    }

    /**
     * 递归计算双亲位置
     * 当前节点的子节点不存在时，则当前节点为其双亲
     */
    private Node<Integer> parent(Node<Integer> node, Integer i) {
        Node<Integer> parent = node == null ? root : node;
        if (Integer.compare(i, parent.value) == -1) {
            return parent.left == null ? parent : parent(parent.left, i);
        } else {
            return parent.right == null ? parent : parent(parent.right, i);
        }
    }

    /**
     * 前序遍历，根->左->右
     */
    private void rld(Node<Integer> node, List<Integer> sortList) {
        if (node != null) {
            sortList.add(node.value);
            rld(node.left, sortList);
            rld(node.right, sortList);
        }
    }

    /**
     * 中序遍历，左->根->右
     */
    private void ldr(Node<Integer> node, List<Integer> sortList) {
        if (node != null) {
            ldr(node.left, sortList);
            sortList.add(node.value);
            ldr(node.right, sortList);
        }
    }

    /**
     * 后序遍历，左->右->根
     */
    private void lrd(Node<Integer> node, List<Integer> sortList) {
        if (node != null) {
            lrd(node.left, sortList);
            lrd(node.right, sortList);
            sortList.add(node.value);
        }
    }

    /**
     * 二叉树节点类
     */
    class Node<E> {

        // 节点内容
        private E value;

        // 左节点
        private Node<E> left;

        // 右节点
        private Node<E> right;

        public Node() {
        }

        public Node(E value) {
            this.value = value;
        }

        public Node(E value, Node<E> left, Node<E> right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

}

4、来个测试类

package test;

import com.fss.util.tree.binarytree.impl.BinaryTreeSort;

import java.util.Arrays;
import java.util.List;

public class BinaryTreeTest {

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(4,2,1,5,3,6);
        BinaryTreeSort binaryTreeSort = new BinaryTreeSort();
        binaryTreeSort.sort(list);
    }

}

5、打印结果

sortList: 1,2,3,4,5,6