學(xué)習(xí)的最好方式就是寫出來

歡迎光臨我的個人小窩：http://wsfss.top

今天我們就手?jǐn)]一個二叉樹排序吧

先來看看二叉樹的相關(guān)知識

• 每個節(jié)點最多只有2個子節(jié)點
• 遍歷元素口訣：前序遍歷视卢，根->左->右虑绵、中序遍歷碌更，左->根->右禀苦、后序遍歷，左->右->根
• 排序機制：依次從根節(jié)點往下比較搀玖，小于當(dāng)前節(jié)點值則走左子節(jié)點绪励，大于當(dāng)前節(jié)點值則走右子節(jié)點铐炫，然后用中序遍歷

1挖函、下面對一組數(shù)字進(jìn)行排序：4状植、2、1怨喘、5、3振定、6必怜，按排序機制添加元素，結(jié)果如下圖

1.png

2后频、然后使用中序遍歷

2.png

3梳庆、接下來通過代碼實現(xiàn)

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> {

    // 根節(jié)點
    private Node<Integer> root;

    public BinaryTreeSort() {
    }

    /**
     * 依次從根節(jié)點往下比較，小于當(dāng)前節(jié)點值則走左子節(jié)點卑惜，大于當(dāng)前節(jié)點值則走右子節(jié)點
     */
    @Override
    public boolean add(Integer i) {
        Node<Integer> node = new Node<>(i);
        // 根節(jié)點不存在
        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(",")));
    }

    /**
     * 遞歸計算雙親位置
     * 當(dāng)前節(jié)點的子節(jié)點不存在時膏执，則當(dāng)前節(jié)點為其雙親
     */
    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);
        }
    }

    /**
     * 二叉樹節(jié)點類
     */
    class Node<E> {

        // 節(jié)點內(nèi)容
        private E value;

        // 左節(jié)點
        private Node<E> left;

        // 右節(jié)點
        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毫痕、打印結(jié)果

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