二叉树算法的java实现

时间：2014-03-03 07:23:53 阅读：318 评论：0 收藏：0 [点我收藏+]

package Alg;

public class BSTreeNode {
    private BSTreeNode leftChild = null;
    private BSTreeNode rightChild = null;
    private BSTreeNode parent = null;
    private int value = Integer.MIN_VALUE;

    public static BSTreeNode createNode(int val) {
        return new BSTreeNode(val);
    }
    
    private BSTreeNode(int val) {
        leftChild = null;
        rightChild = null;
        parent = null;
        value = val;
    }
    
    public BSTreeNode search(int val) {
        if (val == value)
            return this;
        if (val > value ) {
            if (this.getRightChild() != null)
                return this.getRightChild().search(val);
        }
        else {
            if (this.getLeftChild() != null)
                return this.getLeftChild().search(val);
        }
        return this;
    }
    
    public boolean isLeaf() {
        if (getLeftChild() == null && getRightChild() == null)
            return true;
        return false;
    }
    
    public boolean isRoot() {
        if (getParent() == null)
            return true;
        return false;
    }
    
    public BSTreeNode getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(BSTreeNode leftChild) {
        this.leftChild = leftChild;
    }

    public BSTreeNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(BSTreeNode rightChild) {
        this.rightChild = rightChild;
    }

    public BSTreeNode getParent() {
        return parent;
    }

    public void setParent(BSTreeNode parent) {
        this.parent = parent;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }
}

View Code

package 
Alg;
 
public class BSTree {
    private 
BSTreeNode root = null;     //树根节点
    private 
int count = 0;      //树的节点数
     
    public 
int getCount() {
        return 
count;
    }
 
    public 
enum MatchType {E, GE, LE};
     
    /**
     * 根据值进行搜索
     * @param val 匹配值
     * @param matchType 匹配方式 E为严格相等匹配，GE为大于等于匹配，LE为小于等于匹配
     * @return 匹配模式为E时，如果没有找到匹配项，返回null，否则返回匹配到的节点
     *          匹配模式为GE时，如果匹配到数据，返回匹配到的数据，否则返回大于该数据的最小节点
     *          匹配模式为LE时，如果匹配到数据，返回匹配到的数据，否则返回小于该数据的最大节点
     */
    public 
BSTreeNode search(int 
val, MatchType matchType) {
        BSTreeNode n = search(val);
        if 
(n == null)
            return 
null;
        if 
(n.getValue() == val)
            return 
n;
        switch 
(matchType) {
        case 
LE:
            if 
(n.getValue() < val)
                return 
n;
            return 
getLittleSmaller(n);
        case 
GE:
            if 
(n.getValue() > val)
                return 
n;
            return 
getLittleBigger(n);
        default:
        }
 
        return 
null;
    }
     
    private 
BSTreeNode search(int 
val) {
        if 
(root == null)
            return 
null;
        return 
search(root, val);
    }
     
    /**
     * 获取距离该值最近的节点
     * @param n
     * @param val
     * @return
     */
    private 
BSTreeNode search(BSTreeNode n, int 
val) {
        int 
v = n.getValue();
        if 
(v == val)
            return 
n;
        else 
if (v > val) {
            if 
(n.getLeftChild() == null)
                return 
n;
            return 
search(n.getLeftChild(), val);
        }
        if 
(n.getRightChild() == null)
            return 
n;
        return 
search(n.getRightChild(), val);
    }
     
    /**
     * 进行插入操作
     * @param val
     */
    public 
void insert(int 
val) {
        if 
(root == null) {
            root = BSTreeNode.createNode(val);
            count++;
            return;
        }
         
        BSTreeNode x = search(val);
         
        if 
(x.getValue() == val) 
            return; 
        BSTreeNode n = BSTreeNode.createNode(val);
        count++;
        if 
(x.getValue() < val) 
            x.setRightChild(n);
        else
            x.setLeftChild(n);
        n.setParent(x);
    }
     
     
    /**
     * 删除值
     * @param val
     */
    public 
void delete(int 
val) {
        if 
(root == null)
            return;
         
        BSTreeNode x = root.search(val);
        if 
(x.getValue() != val)
            return; 
 
        count++;
        //当为叶子节点时从父节点将该节点的连接删除
        if 
(x.isLeaf()) {
            BSTreeNode p = x.getParent();
            if 
(p.getLeftChild() == x) 
                p.setLeftChild(null);
            else
                p.setRightChild(null);
        }
         
        BSTreeNode lc = x.getLeftChild();
        BSTreeNode rc = x.getRightChild();
        //如果具有两个非空子树，或者从左子树中取得最大的节点代替当前节点
        //或者从右子树取得最小节点代替当前节点
        //然后删除代替的节点
        if 
(lc != null 
&& rc != null) {
            BSTreeNode lr = getRightMostNode(lc);
            BSTreeNode rr = getLeftMostNode(rc);
            //如果是叶节点则可以简单替换节点进行处理，否则要替换后进行再次替换
            if 
(lr.isLeaf()) {
                x.setValue(lr.getValue());
                BSTreeNode rp = lr.getParent();
                rp.setRightChild(null);
                return 
;
            }
            else 
if (rr.isLeaf()) {
                x.setValue(rr.getValue());;
                BSTreeNode lp = rr.getParent();
                lp.setLeftChild(null);
                return 
;
            }
            else 
{
                //调换两个节点，并将删除转换为只有一个子树的情况
                x.setValue(lr.getValue());
                x = lr;
            }
        }
         
        //如果只有一个子树（左子树或右子树），则用子树中的根代替当前节点
        BSTreeNode p = x.getParent();
        if 
(lc != null) {
            if 
(p.getLeftChild() == x) 
                p.setLeftChild(lc);
            else
                p.setRightChild(lc);
            return 
;
        }
         
        if 
(rc != null) {
            if 
(p.getLeftChild() == x) 
                p.setLeftChild(rc);
            else
                p.setRightChild(rc);
        }
    }
     
    /**
     * 以升序方式打印树中节点，实际就是中根的树的访问次序
     */
    public 
void printInAscOrd() {
        if 
(root == null)
            System.out.println("没有数据");
        printInOrder(root);     
    }
     
    /**
     * 将二叉树转换为升序排列的数组
     * @return 返回升序排序后的数组
     */
    public 
BSTreeNode[] getAscOrderArray() {
        BSTreeNode[] ary = new 
BSTreeNode[count];
         
        int 
pos = fillArrayInOrd(ary, 0, root);
        if 
(pos != count)
            System.out.println("构造数组出错");
         
        return 
ary;
    }
     
    private 
int fillArrayInOrd(BSTreeNode[] ary, int 
pos, BSTreeNode root) {
        int 
npos = pos;
        if 
(root.getLeftChild() != null) {
            npos = fillArrayInOrd(ary, npos, root.getLeftChild());
        }
 
        ary[npos] = root;
        npos++;
         
        if 
(root.getRightChild() != null) {
            npos = fillArrayInOrd(ary, npos, root.getRightChild());
        }
        return 
npos;
    }
     
    /**
     * 获取大于当前节点的最小节点
     * @param x
     * @return 如果没有大于该节点的节点，则返回null
     */
    private 
BSTreeNode getLittleBigger(BSTreeNode x) {
        BSTreeNode rc = x.getRightChild();
        if 
(rc != null) {
            return 
getLeftMostNode(rc);
        }
        else 
{
            //回溯祖先节点，取得第一个令该节点为左子树节点的祖先节点
            BSTreeNode p = x.getParent();
            BSTreeNode s = x;
            while 
(p != null) {
                if 
(p.getLeftChild() == s)
                    break;
                s = p;
                p = p.getParent();
            }
            return 
p;
        }
    }
     
    private 
BSTreeNode getLittleSmaller(BSTreeNode x) {
        BSTreeNode lc = x.getLeftChild();
        if 
(lc != null) {
            return 
getRightMostNode(lc);
        }
        else 
{
            //回溯祖先节点，取得第一个令该节点为左子树节点的祖先节点
            BSTreeNode p = x.getParent();
            BSTreeNode s = x;
            while 
(p != null) {
                if 
(p.getRightChild() == s)
                    break;
                s = p;
                p = p.getParent();
            }
            if 
(p != null)
                return 
p;
        }
        return 
null;
    }
     
    private 
BSTreeNode getLeftMostNode(BSTreeNode x) {
        while 
(x.getLeftChild() != null) {
            x = x.getLeftChild();
        }
        return 
x;
    }
     
    private 
BSTreeNode getRightMostNode(BSTreeNode x) {
        while 
(x.getRightChild() != null) {
            x = x.getRightChild();
        }
        return 
x;
    }
     
    private 
void printInOrder(BSTreeNode n) {
        if 
(n.getLeftChild() != null)
            printInOrder(n.getLeftChild());
        printNode(n);
        if 
(n.getRightChild() != null)
            printInOrder(n.getRightChild());
    }
     
    private 
void printNode(BSTreeNode n) {
        System.out.print("[" 
+ n.getValue() + "]");
    }
     
    private 
void checkTreeValidation() throws 
Exception {
        BSTreeNode[] ary = this.getAscOrderArray();
        for 
(int i = 0; i < ary.length; i++) {
            if 
(ary[i].getValue() > ary[i + 1].getValue()) {
                throw 
new Exception("二叉树出现错误");
            }
        }
    }
     
    public 
static BSTree buildRandomTree1() {
        BSTree tree = new 
BSTree();
        try 
{
            tree.insert(8569);
            tree.insert(7556);
            tree.insert(3421);
            tree.insert(5665);
            tree.insert(5169);
            tree.insert(9189);
            tree.insert(5656);
            tree.insert(6691);
            tree.insert(6932);
            tree.insert(3511);
            tree.insert(4269);
            tree.insert(3556);
            tree.checkTreeValidation();
            return 
tree;
        } catch 
(Exception e) {
            e.printStackTrace();
            return 
null;
        }   
    }
     
    public 
static BSTree buildRandomTree2() {
        BSTree tree = new 
BSTree();
        try 
{
            tree.insert(53);
            tree.insert(12);
            tree.insert(27);
            tree.insert(99);
            tree.insert(46);
            tree.insert(5);
            tree.insert(38);
            tree.checkTreeValidation();
            return 
tree;
        } catch 
(Exception e) {
            e.printStackTrace();
            return 
null;
        }
    }
     
    public 
static void testInsertCase1() {
        BSTree tree = buildRandomTree1();
        if 
(tree == null)
            System.out.println("构造二叉树出错");
        tree.printInAscOrd();
    }
 
    public 
static void testInsertCase2() {
        BSTree tree = buildRandomTree2();
        if 
(tree == null)
            System.out.println("构造二叉树出错");
        tree.printInAscOrd();
    }
     
    public 
static void testGetArray() {
        BSTree tree = buildRandomTree2();
        if 
(tree == null)
            System.out.println("构造二叉树出错");
 
        BSTreeNode[] ary = tree.getAscOrderArray();
        for 
(int i = 0; i < ary.length; i++) {
            System.out.print("[");
            System.out.print(ary[i].getValue());
            System.out.print("]");
        }
    }
     
    public 
static void testGetLittleBigger(){
        BSTree tree = buildRandomTree2();
        if 
(tree == null)
            System.out.println("构造二叉树出错");
        tree.printInAscOrd();
        System.out.println("");
         
        BSTreeNode[] ary = tree.getAscOrderArray();
         
        for 
(int i = 0; i < ary.length - 1; i++) {
            BSTreeNode n = ary[i];
            BSTreeNode b = tree.getLittleBigger(n);
            System.out.println("当前数值" 
+ n.getValue() +"." 
+ "较大数值为" 
+ b.getValue());
            if 
(b.getValue() != ary[i + 1].getValue())
                System.out.println("出现错误");
            else
                System.out.println("正确");       
        }
    }
     
    public 
static void testGetLittleSmaller() {
        BSTree tree = buildRandomTree2();
        if 
(tree == null)
            System.out.println("构造二叉树出错");
        tree.printInAscOrd();
        System.out.println("");
         
        BSTreeNode[] ary = tree.getAscOrderArray();
         
        for 
(int i = ary.length - 1; i > 0; i--) {
            BSTreeNode n = ary[i];
            BSTreeNode s = tree.getLittleSmaller(n);
            System.out.println("当前数值" 
+ n.getValue() +"." 
+ "较小数值为" 
+ s.getValue());
            if 
(s.getValue() != ary[i - 1].getValue())
                System.out.println("出现错误");
            else
                System.out.println("正确");       
        }       
    }
     
}

二叉树算法的java实现,布布扣,bubuko.com

二叉树算法的java实现

原文：http://www.cnblogs.com/northhurricane/p/3576413.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)