Author: nice01qc
Time : March 09, 2018

二叉树算法

简单的二叉树规划，及其前中后序遍历…

二叉树定义：所有节点的值小于右边的值，大于左边的值

设计一个根节点 Node root; 为入口

存储数据节点为：

private class Node{
    private Key key;		// 键
    private Value val;		// 值
    private Node left, right;	//左右节点
    private int N;		// 该节下总数
    public Node(Key key, Value val, int N){
        this.key = key;
        this.val = val;
        this.N = N;
    }
}

查找：通过判断找到合适的位置，值相同则覆盖（递归查找）

private Value get(Node root, Key key){
    if (root == null) return null;
    int cmp = key.compareTo(root.key);
    if(cmp < 0){
        return get(root.left,key);
    }else if(cmp > 0){
        return get(root.right,key);
    }else{
        return root.val;
    }
}

插入（略，也是同上递归判断，然后插入，并重新递归计算每个节点总数）

删除操作：

先找到要删除的节点
如果此节点的左节点为null，直接返回右节点接上就好了
如果此节点的右节点为null，直接返回左节点接上就好了
如果左右节点都在，则找有节点下最小值，然后替换就好

前序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树 (根左右）

实现1：递归调用略

实现2：堆实现

public void preorder(Node root){
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while(!stack.empty()){
        Node tmproot = stack.pop();
        System.out.println(tmproot.key);	// 此处输出节点或者 处理节点
        if(tmproot.right != null) stack.push(rmproot.right);
        if(tmproot.left != null) stack.push(rmproot.left);
    }
}

中序遍历：先遍历左子树，然后遍历根结点，最后遍历右子树 (左根右）

实现1：递归调用略

实现2：堆实现

public void midorder(Node root){
    if(root == null) return ;
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while(!stack.empty()){
        Node tmproot = stack.pop();
        if(tmproot.left != null){
            if(tmproot.right != null) stack.push(tmproot.right);
            stack.push(tmproot);
            stack.push(tmproot.left);
        }else{
            System.out.println(tmproot.key);	// 此处处理节点
        }
    }
}

后序遍历：先遍历左子树，然后遍历右子树，最后遍历根节点（左右根）

实现1：递归调用略

实现2：堆实现

public void midorder(Node root){
    if(root == null) return ;
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    while(!stack.empty()){
        Node tmproot = stack.pop();
        if(tmproot.left != null){
            if(tmproot.right != null) stack.push(tmproot.right);
            stack.push(tmproot.left);		// 在变换右根顺序就好
            stack.push(tmproot);
        }else{
            System.out.println(tmproot.key);	// 此处处理节点
        }
    }
}

其他：

如果已知中序遍历和前序遍历（或者后续遍历），就可以推到出整个二叉树。

题如：牛客网

参考资源：

http://blog.csdn.net/prince_jun/article/details/7699024

← → Top