博客

java实现一个排序树：

(1)每个节点：用一个类表示（父节点，左子节点，右子节点，自身，父节点对象，左右节点对象存储其地址）

(2)整体结构：用一个集合<Integer>表示

(3)初始化：空（约束条件：第一个添加的元素必须是根节点，无父节点，左右节点分别置为空，自身赋值）

(4)插入方法：使用查询指针进行移动，首先设置为根节点，如果大于该节点则将指针移动到根节点的右子树，否则创建右子树并赋值，左子树同理

Tree节点：

package TreeArrayList;

import lombok.Data;

import java.util.Objects;


public class Tree {
    private Integer self;
    private Integer father;
    private Integer leftSon;
    private Integer rightSon;
    private Tree fatherTree;//存储父节点地址
    private Tree leftSonTree;//存储左节点地址
    private Tree rightSonTree;//存储右节点地址

    //根节点：只有self
    //正常节点：有父节点，子节点
    public Tree(Integer self) {
        this.self = self;//创建根节点
//        this.father = null;
//        this.leftSon = null;
//        this.rightSon = null;
    }

    public Tree() {
    }

    public Tree(Integer self, Integer father, Tree fatherTree) {
        this.self = self;
        this.father = father;
        this.fatherTree = fatherTree;//创建一个新的有父节点的子节点
    }



    public Integer getSelf() {
        return self;
    }

    public void setSelf(Integer self) {
        this.self = self;
    }

    public Integer getFather() {
        return father;
    }

    public void setFather(Integer father) {
        this.father = father;
    }

    public Integer getLeftSon() {
        return leftSon;
    }

    public void setLeftSon(Integer leftSon) {
        this.leftSon = leftSon;
    }

    public Integer getRightSon() {
        return rightSon;
    }

    public void setRightSon(Integer rightSon) {
        this.rightSon = rightSon;
    }

    public Tree getFatherTree() {
        return fatherTree;
    }

    public void setFatherTree(Tree fatherTree) {
        this.fatherTree = fatherTree;
    }

    public Tree getLeftSonTree() {
        return leftSonTree;
    }

    public void setLeftSonTree(Tree leftSonTree) {
        this.leftSonTree = leftSonTree;
    }

    public Tree getRightSonTree() {
        return rightSonTree;
    }

    public void setRightSonTree(Tree rightSonTree) {
        this.rightSonTree = rightSonTree;
    }


}

TreeStore:

package TreeArrayList;

import lombok.Data;


import java.util.ArrayList;
import java.util.Iterator;

@Data
public class TreeStore {
    public static ArrayList<Tree> sortTree;//排序二叉树的存储集合

    public static Tree addTreePointer;//将移动指针设置为全局变量

    public TreeStore() {
        ArrayList<Tree> sortTree = new ArrayList<>();
        TreeStore.sortTree = sortTree;//初始化构造函数给一个空的存储集合
    }

    public void add(Integer add){
        if(null != sortTree){
            if(0 == sortTree.size()){
                Tree BaseTree = new Tree(add);//置为根节点,并将根节点加入static
                sortTree.add(BaseTree);
            }else {
                //引入对象指向根节点，先查找根节点
                Tree BaseTree = new Tree();
                Iterator<Tree> iterator = sortTree.iterator();
                while (iterator.hasNext()){
                    Tree next = iterator.next();
                    if(null == next.getFatherTree()){
                        BaseTree = next;
                    }
                }//找到根节点
//                sortTree.add(BaseTree);
                //设置一个插入指针，先指向根节点
//                Tree addTreePointer = new Tree();

                addTreePointer = BaseTree;

                while (true){
                    Boolean aBoolean = serachPointer(addTreePointer, add);
                    if(aBoolean){
                        break;
                    }
                }
            }
        }else {
            System.out.println("未创建新的二叉树！");
        }
    }

    public static Boolean serachPointer(Tree addTreePointer,Integer add){
        //根据插入指针来操作,如果要插入的数据小于插入指针的值
        if(add<addTreePointer.getSelf()){
            if(null == addTreePointer.getLeftSonTree()){
                //如果左边没有那么创建左子树，并将指针节点的左子树设置为该左节点，终结条件
                Tree leftTree = new Tree(add, addTreePointer.getFather(), addTreePointer.getFatherTree());
                addTreePointer.setLeftSonTree(leftTree);
                addTreePointer.setLeftSon(leftTree.getSelf());
                leftTree.setFather(addTreePointer.getSelf());
                leftTree.setFatherTree(addTreePointer);
                sortTree.add(leftTree);//插入新的元素

                return true;
            }else {
                //否则查询指针变为左子树
                TreeStore.addTreePointer = addTreePointer.getLeftSonTree();
                return false;
            }
        }else if(add > addTreePointer.getSelf()){
            if(null == addTreePointer.getRightSonTree()){
                //如果左边没有那么创建右子树，并将指针节点的左子树设置为该左节点
                Tree RightTree = new Tree(add, addTreePointer.getFather(), addTreePointer.getFatherTree());
                addTreePointer.setRightSonTree(RightTree);
                addTreePointer.setRightSon(RightTree.getSelf());
                RightTree.setFatherTree(addTreePointer);
                RightTree.setFather(addTreePointer.getSelf());
                sortTree.add(RightTree);
//                TreeStore.addTreePointer = addTreePointer.getRightSonTree();
                return true;
            }else {
                //否则查询指针变为右子树
                TreeStore.addTreePointer = addTreePointer.getRightSonTree();
                return false;
            }
        }else {
            System.out.println("插入的数据已经存在，不能插入！");
            return false;
        }

    }

    public static void ArrayListUpdate(Tree tree){
        if(null!=sortTree){
            if(0==sortTree.size()){

            }else {
                Tree BaseTree = new Tree();
                Iterator<Tree> iterator = sortTree.iterator();
                while (iterator.hasNext()){
                    Tree next = iterator.next();
                    if(null == next.getFatherTree()){
                        BaseTree = next;
                    }
                }
                //引入左移动指针和右移动指针
            }
        }
    }
}

测试方法;

TestMain:

package TreeArrayList;

import java.util.Iterator;

public class TestMain {
    public static void main(String[] args) {
        TreeStore treeStore = new TreeStore();
        treeStore.add(7);
        treeStore.add(4);
        treeStore.add(3);
        treeStore.add(6);
        treeStore.add(5);
        //如果用toString方法会出现错误，因为子节点的属性中有父节点对象，父节点对象的属性中也有子节点
        Iterator<Tree> iterator = TreeStore.sortTree.iterator();
        while (iterator.hasNext()){
            Tree next = iterator.next();
            System.out.println("该节点是："+next.getSelf()+"  "+"父节点是："+next.getFather()+"左右子节点分别是："+next.getLeftSon()+" "+next.getRightSon());
        }

    }
}