返回顶部

收藏

数据结构-二叉查找树添加 删除 遍历

更多
package com.structures.tree;

import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.Stack;

/*
 * Binary Search Tree 
 */
public class Searchtree {
    public Integer data;
    public Searchtree left;
    public Searchtree right;

    public void setData(Integer data) {
        this.data = data;
    }

    public Searchtree(Integer number) {
        this.data = number;
    }

    public void setLeft(Searchtree left) {
        this.left = left;
    }

    public void setRight(Searchtree right) {
        this.right = right;
    }

    // add
    public void add(int number) {
        if (number <= this.data)
            add(number, this, this.left, 0);
        else
            add(number, this, this.right, 1);
    }

    private void add(int number, Searchtree father, Searchtree child, int tag) {
        if (child == null) {
            child = new Searchtree(number);
            if (tag == 0)
                father.setLeft(child);
            else
                father.setRight(child);
        } else {
            // attention: here must be child
            if (number <= child.data)// add to left
                add(number, child, child.left, 0);
            else
                // add to right
                add(number, child, child.right, 1);

        }
    }

    // find
    public Searchtree find(int number) {
        if (number < data) {
            return find(number, this);
        } else if (number > data) {
            return find(number, this);
        } else {
            return find(number, this);
        }
    }

    private Searchtree find(int number, Searchtree tree) {
        if (tree == null)
            throw new NoSuchElementException(
                    "no such element in the binary search tree");
        if (number < tree.data) {
            return find(number, tree.left.left);
        } else if (number > tree.data) {
            return find(number, tree.right);
        } else
            return tree;
    }

    // findPrevious
    private ArrayList<Searchtree> trees = new ArrayList<Searchtree>();

    private Searchtree findPrevious(int number, Searchtree tree) {
        if (tree == null)
            throw new NoSuchElementException(
                    "no such element in the binary search tree");
        trees.add(tree);
        if (number < tree.data) {
            return findPrevious(number, tree.left);
        } else if (number > tree.data) {
            return findPrevious(number, tree.right);
        } else {
            Searchtree pre = trees.get(trees.size() - 2);
            trees = null;
            return pre;
        }
    }

    // min
    public Searchtree findMin(Searchtree tree) {
        if (tree == null)
            throw new NoSuchElementException(
                    "no such element in the binary search tree");
        else if (tree.left == null)
            return tree;
        else
            return findMin(tree.left);

    }

    // max
    public Searchtree findMax(Searchtree tree) {
        if (tree == null)
            throw new NoSuchElementException(
                    "no such element in the binary search tree");
        else if (tree.right == null)
            return tree;
        else
            return findMax(tree.right);
    }

    public Searchtree remove(int number) {
        return remove(number, this);
    }
    /*remove
     *  是最困难的,请大家参考一下,递归有点晕。大家阅读书理解吧。
     *  参考代码:《数据结构与算法分析》-C语言描述 英文版
     *  第102-103页 
     * ISBN: 9787115139849 
     * detail:http://book.douban.com/subject/1444648/
     */
    public Searchtree remove(int number, Searchtree tree) {
        Searchtree delete = null;
        if (tree == null)
            throw new IndexOutOfBoundsException("tree size is 0");
        else if (number < tree.data) {
            // go left
            tree.left = remove(number, tree.left);
        } else if (number > tree.data) {
            // go right
            tree.right = remove(number, tree.right);
            // found element to be remove
        } else if (tree.left != null && tree.right != null) {
            // two children
            // replace with the smallest in right tree
            delete = findMin(tree.right);
            tree.setData(delete.data);
            tree.setRight(remove(tree.data, tree.right));
            delete = null;
        } else {
            // one or zero child
            delete = tree;
            if (delete.left == null) {
                tree = tree.right;
            } else if (delete.right == null) {
                tree = tree.left;
            }
            delete = null;
        }

        return tree;
    }

    // 先序遍历 preorder traversal
    public void preorder() {
        System.out.print(data + " ");
        if (left != null)
            left.preorder();
        if (right != null)
            right.preorder();

    }

    // 中序遍历 inorder traversal
    public void inorder() {
        if (left != null)
            left.inorder();
        System.out.print(data + " ");
        if (right != null)
            right.inorder();

    }

    // 后序遍历 postorder traversal
    public void postorder() {
        if (left != null)
            left.postorder();

        if (right != null)
            right.postorder();
        System.out.print(data + " ");
    }

    public int getDepth(Searchtree root) {
        int depth;
        if (root == null)
            return 0;
        else {
            depth = 1 + Math.max(getDepth(root.left), getDepth(root.right));
            return depth;
        }
    }

    public static void main(String[] args) {
        Searchtree tree = new Searchtree(5);
        tree.add(3);
        tree.add(7);
        tree.add(2);
        tree.add(4);
        tree.add(6);
        tree.add(8);
        tree.add(1);
        tree.add(1);
        tree.remove(1);
        // tree.remove(2, tree);
        //tree.remove(tree.data);
        tree.preorder();
        System.out.println();
        tree.inorder();
        System.out.println();
        System.out.println(tree.getDepth(tree));
        System.out.println(tree.find(7).data);
        System.out.println(tree.findPrevious(8, tree).data);

    }

}
//该片段来自于http://outofmemory.cn

标签:java,算法

收藏

0人收藏

支持

0

反对

0

发表评论