javaBST - juedaiyuer/researchNote GitHub Wiki

#二叉搜索数算法BST#

BST1

##节点定义##

package myAlgorithm;

/**
 * Created by juedaiyuer on 16-9-28.
 */
public class TreeNode {
	int value;

	TreeNode left;
	TreeNode right;

	public TreeNode(int value){
	    this.value = value;
	    left = null;
	    right = null;
	    
	}
}

##插入功能（添加节点）##

public TreeNode insert(int key) {
	    //新增节点
	    TreeNode newNode = new TreeNode(key);
	    //当前节点
	    TreeNode current = root;
	    //上个节点
	    TreeNode parrent = null;
	    //如果根节点为空
	    if (current == null) {
	        root = newNode;
	        return newNode;
	    }

	    while (true) {
	        parrent = current;
	        if (key < current.value) {
	            current = current.left;
	            if (current == null) {
	                parrent.left = newNode;
	                return newNode;
	            }
	        } else {
	            current = current.right;
	            if (current == null) {
	                parrent.right = newNode;
	                return newNode;
	            }
	        }
	    }
	}


// 测试

##删除节点##

BST1

##最大值与最小值##

// 最大值一直往右走，最小值一直往左走
public int max(){
    TreeNode node = root;
    TreeNode parrent = null;
    while (node != null){
        parrent = node;
        node = node.right;
    }
    return parrent.value;
}

public int min(){
    TreeNode node = root;
    TreeNode parrent = null;
    while (node != null){
        parrent = node;
        node = node.left;
    }
    return parrent.value;
}

##遍历树##

// 中序遍历，迭代法

public void display(TreeNode node) { if (node != null) { display(node.left); System.out.println(node.value + ","); display(node.right); } }

##source##