二叉树

作者: whupenger | 来源:发表于2019-03-11 11:38 被阅读0次

二叉树

二叉树(Binary Tree)是包含n个节点的有限集合,该集合或者为空集(此时,二叉树称为空树),或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

常见二叉树

  • 满二叉树:对于一棵二叉树,如果每一个非叶子节点都存在左右子树,并且二叉树中所有的叶子节点都在同一层中,这样的二叉树称为满二叉树。


    满二叉树
  • 完全二叉树

对于一棵具有n个节点的二叉树按照层次编号,同时,左右子树按照先左后右编号,如果编号为i的节点与同样深度的满二叉树中编号为i的节点在二叉树中的位置完全相同,则这棵二叉树称为完全二叉树。


完全二叉树

二叉树的遍历

  • 前序遍历:首先遍历根节点,其次遍历左孩子,再遍历右孩子,按照如此的顺序遍历整棵树
  • 中序遍历:先遍历左子树,其次遍历父节点,最后遍历右子树
  • 后序遍历:先遍历左子树,其次遍历右子树,最后遍历父节点
  • 层次遍历(广度优先BFS):
    • 数据结构:队列
    • 父节点入队,父节点出队列,先左子节点入队,后右子节点入队。递归遍历全部节点即可
  • 深度优先(DFS):根节点出发,沿着左子树方向进行纵向遍历,直到找到叶子节点为止。然后回溯到前一个节点,进行右子树节点的遍历,直到遍历完所有可达节点为止
    • 数据结构:栈
    • 父节点入栈,父节点出栈,先右子节点入栈,后左子节点入栈。递归遍历全部节点即可
package algorithm;

import lombok.Data;

import java.util.LinkedList;
import java.util.Optional;
import java.util.Stack;

/**
 * author: TAOPENG
 * time : 2019/3/11
 **/
@Data
public class TreeDemo {
    @Data
    public class TreeNode {
        private Integer value;
        private TreeNode leftChild;
        private TreeNode rightChild;

        public TreeNode(Integer value) {
            this.value = value;
        }
    }

    public void preOrder(TreeNode node) {
        Optional.ofNullable(node).ifPresent(n -> {
            System.out.print(n.getValue() + " ");
            preOrder(n.getLeftChild());
            preOrder(n.getRightChild());
        });
    }

    // 先序遍历非递归实现
    public void preOrder2(TreeNode node) {
        Optional.ofNullable(node).ifPresent(n -> {
            Stack<TreeNode> stack = new Stack<>();
            while (n != null || !stack.isEmpty()) {
                while (n != null) {
                    System.out.print(n.getValue() + " ");
                    stack.push(n);
                    n = n.getLeftChild();
                }
                if (!stack.isEmpty()) {
                    n = stack.pop().getRightChild();
                }
            }
        });

    }

    public void midOrder(TreeNode node) {
        Optional.ofNullable(node).ifPresent(n -> {
            midOrder(n.getLeftChild());
            System.out.print(n.getValue() + " ");
            midOrder(n.getRightChild());
        });
    }

    // 中序遍历非递归实现
    public void midOrder2(TreeNode node) {
        Optional.ofNullable(node).ifPresent(n -> {
            Stack<TreeNode> stack = new Stack<>();
            while (n != null || !stack.isEmpty()) {
                while (n != null) {
                    stack.push(n);
                    n = n.getLeftChild();
                }
                if (!stack.isEmpty()) {
                    TreeNode child = stack.pop();
                    System.out.print(child.getValue() + " ");
                    n = child.getRightChild();
                }
            }
        });

    }

    public void postOrder(TreeNode node) {
        Optional.ofNullable(node).ifPresent(n -> {
            postOrder(n.getLeftChild());
            postOrder(n.getRightChild());
            System.out.print(n.getValue() + " ");
        });
    }
    // 后序遍历非递归实现
    public void postOrder2(TreeNode node) {
        Optional.ofNullable(node).ifPresent(n -> {
            Stack<TreeNode> s = new Stack<>();

            TreeNode curNode = n; //当前访问的结点
            TreeNode lastVisitNode = null; //上次访问的结点
            //把currentNode移到左子树的最下边
            while (curNode != null) {
                s.push(curNode);
                curNode = curNode.getLeftChild();
            }
            while (!s.empty()) {
                curNode = s.pop();  //弹出栈顶元素
                //一个根节点被访问的前提是:无右子树或右子树已被访问过
                if (curNode.getRightChild() != null && curNode.getRightChild() != lastVisitNode) {
                    //根节点再次入栈
                    s.push(curNode);
                    //进入右子树,且可肯定右子树一定不为空
                    curNode = curNode.getRightChild();
                    while (curNode != null) {
                        //再走到右子树的最左边
                        s.push(curNode);
                        curNode = curNode.getLeftChild();
                    }
                } else {
                    //访问
                    System.out.print(curNode.getValue() + " ");
                    //修改最近被访问的节点
                    lastVisitNode = curNode;
                }
            }
        });

    }

    public void levelOrder(TreeNode node) {
        Optional.ofNullable(node).ifPresent(n -> {
            LinkedList<TreeNode> linkedList = new LinkedList<>();
            linkedList.add(n);
            while (!linkedList.isEmpty()) {
                TreeNode current = linkedList.poll();
                System.out.print(current.getValue() + " ");
                Optional.ofNullable(current.getLeftChild()).ifPresent(linkedList::add);
                Optional.ofNullable(current.getRightChild()).ifPresent(linkedList::add);
            }
        });
    }

    public void dfs(TreeNode node) {
        Optional.ofNullable(node).ifPresent(n -> {
            Stack<TreeNode> stack = new Stack<>();
            stack.add(n);
            while (!stack.isEmpty()) {
                TreeNode current = stack.pop();
                System.out.print(current.getValue() + " ");
                Optional.ofNullable(current.getRightChild()).ifPresent(stack::add);
                Optional.ofNullable(current.getLeftChild()).ifPresent(stack::add);
            }
        });
    }

    public Integer getHeight(TreeNode node) {
        return Optional.ofNullable(node).map(n -> {
            int leftHeight = getHeight(n.getLeftChild());
            int rightHeight = getHeight(n.getRightChild());
            return Math.max(leftHeight, rightHeight) + 1;
        }).orElse(0);
    }

    public Integer getMax(TreeNode node) {
        return Optional.ofNullable(node).map(n -> {
            int leftMax = getMax(n.getLeftChild());
            int rightMax = getMax(n.getRightChild());
            return Math.max(n.getValue(), Math.max(leftMax, rightMax));
        }).orElse(Integer.MIN_VALUE);
    }

    public static void main(String[] args) {
        TreeDemo treeDemo = new TreeDemo();
        TreeNode root = treeDemo.new TreeNode(10);
        TreeNode leftChild1 = treeDemo.new TreeNode(8);
        TreeNode rightChild1 = treeDemo.new TreeNode(13);
        TreeNode leftChild11 = treeDemo.new TreeNode(7);
        TreeNode rightChild12 = treeDemo.new TreeNode(9);
        TreeNode leftChild21 = treeDemo.new TreeNode(11);
        TreeNode rightChild22 = treeDemo.new TreeNode(14);
        root.setLeftChild(leftChild1);
        root.setRightChild(rightChild1);
        leftChild1.setLeftChild(leftChild11);
        leftChild1.setRightChild(rightChild12);
        rightChild1.setLeftChild(leftChild21);
        rightChild1.setRightChild(rightChild22);
        System.out.print("preOrder:");
        treeDemo.preOrder(root);
        System.out.println();
        System.out.print("preOrder2:");
        treeDemo.preOrder2(root);
        System.out.println();
        System.out.print("midOrder:");
        treeDemo.midOrder(root);
        System.out.println();
        System.out.print("midOrder2:");
        treeDemo.midOrder2(root);
        System.out.println();
        System.out.print("postOrder:");
        treeDemo.postOrder(root);
        System.out.println();
        System.out.print("postOrder2:");
        treeDemo.postOrder2(root);
        System.out.println();
        System.out.print("levelOrder:");
        treeDemo.levelOrder(root);
        System.out.println();
        System.out.print("DFS:");
        treeDemo.dfs(root);
        System.out.println();
        System.out.print("Height:" + treeDemo.getHeight(root));
        System.out.println();
        System.out.print("Max:" + treeDemo.getMax(root));
    }
}

二叉树的高度

左边的子树和右边的字数比,谁大就返回谁,那么再接上根节点+1就可以了

  public Integer getHeight(TreeNode node) {
        return Optional.ofNullable(node).map(n -> {
            int leftHeight = getHeight(n.getLeftChild());
            int rightHeight = getHeight(n.getRightChild());
            return Math.max(leftHeight, rightHeight) + 1;
        }).orElse(0);
    }

二叉树的最大值

如果是二叉排序树,直接递归取最后的右孩子;一般二叉树的话,递归取左边孩子最大值和右边孩子最大值,进行比较取最大,再与父节点比较

  public Integer getMax(TreeNode node) {
        return Optional.ofNullable(node).map(n -> {
            int leftMax = getMax(n.getLeftChild());
            int rightMax = getMax(n.getRightChild());
            return Math.max(n.getValue(), Math.max(leftMax, rightMax));
        }).orElse(Integer.MIN_VALUE);
    }

二叉排序树

二叉排序树,又称二叉查找树、二叉搜索树。
二叉排序树是具有下列性质的二叉树:

  • 若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
  • 左、右子树也分别为二叉排序树。

二叉排序树这个特点我们可以知道,二叉排序树的中序遍历一定是从小到大的


二叉树示意图

中序遍历结果是: 1 3 4 6 7 8 10 13 14

查找

根据二叉排序树的定义,我们可以知道在查找某个元素时:

  • 先比较它与根节点,相等就返回;或者根节点为空,说明树为空,也返回;
  • 如果它比根节点小,就从根的左子树里进行递归查找;
  • 如果它比根节点大,就从根的右子树里进行递归查找
 /**
     * 在指定二叉排序树中查找数据
     *
     * @param node
     * @param data
     * @return
     */
    public BinaryTreeNode search(BinaryTreeNode node, int data) {
        if (node == null || node.getData() == data) {    //节点为空或者相等,直接返回该节点
            return node;
        }
        if (data < node.getData()) {    //比节点小,就从左子树里递归查找
            return search(node.getLeftChild(), data);
        } else {        //否则从右子树
            return search(node.getRightChild(), data);
        }
    }

插入

二叉树中的插入,主要分两步:查找、插入:

  • 先查找有没有整个元素,有的话就不用插入了,直接返回;
  • 没有就插入到之前查到(对比)好的合适的位置。
/**
 * 查找、插入
 *
 * @param parent 要绑定的父节点
 * @param node   当前比较节点
 * @param data   数据
 */
private BinaryTreeNode searchAndInsert(BinaryTreeNode parent, BinaryTreeNode node, int data) {
    if (node == null) {  //当前比较节点为 空,说明之前没有这个数据,直接新建、插入
        node = new BinaryTreeNode();
        node.setData(data);
        if (parent != null) {    //父节点不为空,绑定关系
            if (data < parent.getData()) {
                parent.setLeftChild(node);
            } else {
                parent.setRightChild(node);
            }
        }
        return node;
    }
    //对比的节点不为空
    if (node.getData() == data) {    //已经有了,不用插入了
        return node;
    } else if (data < node.getData()) {   //比节点小,从左子树里查找、插入
        return searchAndInsert(node, node.getLeftChild(), data);
    } else {
        return searchAndInsert(node, node.getRightChild(), data);
    }
}

删除

  • 如果要删除的节点正好是叶子节点,直接删除;
  • 如果要删除的节点还有子节点,就需要建立父节点和子节点的关系:
  • 如果只有左孩子或者右孩子,直接把这个孩子上移放到要删除的位置就好了;
  • 如果有两个孩子,就需要选一个合适的孩子节点作为新的根节点,该节点称为继承节点

继承节点要比所有左子树的值大、右子树小,就从右子树里找最小的或者从左子树里找最大的

/**
 * 在整个树中 查找指定数据节点的父亲节点
 *
 * @param data
 * @return
 */
public BinaryTreeNode searchParent(int data) {
    return searchParent(null, mRoot, data);
}

/**
 * 在指定节点下 查找指定数据节点的父亲节点
 *
 * @param parent 当前比较节点的父节点
 * @param node   当前比较的节点
 * @param data   查找的数据
 * @return
 */
public BinaryTreeNode searchParent(BinaryTreeNode parent, BinaryTreeNode node, int data) {
    if (node == null) { //比较的节点为空返回空
        return null;
    }
    if (node.getData() == data) {    //找到了目标节点,返回父节点
        return parent;
    } else if (data < node.getData()) {   //数据比当前节点小,左子树中递归查找
        return searchParent(node, node.getLeftChild(), data);
    } else {
        return searchParent(node, node.getRightChild(), data);
    }
}
/**
 * 删除指定数据的节点
 *
 * @param data
 */
public void delete(int data) {
    if (mRoot == null || mRoot.getData() == data) {  //根节点为空或者要删除的就是根节点,直接删掉
        mRoot = null;
        return;
    }
  //接下来该找要删除的节点了
        BinaryTreeNode deleteNode =null;
        BinaryTreeNode parent=null;
        if( mRoot.getData() == data){//判断是否是根
            deleteNode=mRoot;
            isRoot=true;
        }else{
            //在删除之前需要找到它的父亲
             parent = searchParent(data);
            if (parent == null) {        //如果父节点为空,说明这个树是空树,没法删
                return;
            }
            //接下来该找要删除的节点了
            deleteNode = search(parent, data);
            if (deleteNode == null) {    //树中找不到要删除的节点
                return;
            }


        }

    //删除节点有 4 种情况
    //1.左右子树都为空,说明是叶子节点,直接删除
    if (deleteNode.getLeftChild() == null && deleteNode.getRightChild() == null) {
        //删除节点
         if(isRoot){ //根节点置空后直接返回
                mRoot=null;
                return;
            }
        deleteNode = null;
        //重置父节点的孩子状态,告诉他你以后没有这个儿子了
        if (parent.getLeftChild() != null && parent.getLeftChild().getData() == data) {
            parent.setLeftChild(null);
        } else {
            parent.setRightChild(null);
        }
        return;
    } else if (deleteNode.getLeftChild() != null && deleteNode.getRightChild() == null) {
        //2.要删除的节点只有左子树,左子树要继承位置
         if(isRoot){
                mRoot=mRoot.getLeftChild();
                return;
            }
        if (parent.getLeftChild() != null && parent.getLeftChild().getData() == data) {
            parent.setLeftChild(deleteNode.getLeftChild());
        } else {
            parent.setRightChild(deleteNode.getLeftChild());
        }
        deleteNode = null;
        return;
    } else if (deleteNode.getRightChild() != null && deleteNode.getRightChild() == null) {
          if(isRoot){
                mRoot=mRoot.getRightChild();
                return;
            }
        //3.要删除的节点只有右子树,右子树要继承位置
        if (parent.getLeftChild() != null && parent.getLeftChild().getData() == data) {
            parent.setLeftChild(deleteNode.getRightChild());
        } else {
            parent.setRightChild(deleteNode.getRightChild());
        }

        deleteNode = null;
    } else {
        //4.要删除的节点儿女双全,既有左子树又有右子树,需要选一个合适的节点继承,这里使用右子树中最左节点
        BinaryTreeNode copyOfDeleteNode = deleteNode;   //要删除节点的副本,指向继承节点的父节点
        BinaryTreeNode heresNode = deleteNode.getRightChild(); //要继承位置的节点,初始为要删除节点的右子树的树根
        //右子树没有左孩子了,他就是最小的,直接上位
        if (heresNode.getLeftChild() == null) {
            //上位后,兄弟变成了孩子
            heresNode.setLeftChild(deleteNode.getLeftChild());
        } else {
            //右子树有左孩子,循环找到最左的,即最小的
            while (heresNode.getLeftChild() != null) {
                copyOfDeleteNode = heresNode;       //copyOfDeleteNode 指向继承节点的父节点
                heresNode = heresNode.getLeftChild();
            }
            //找到了继承节点,继承节点的右子树(如果有的话)要上移一位
            copyOfDeleteNode.setLeftChild(heresNode.getRightChild());
            //继承节点先继承家业,把自己的左右孩子变成要删除节点的孩子
            heresNode.setLeftChild(deleteNode.getLeftChild());
            heresNode.setRightChild(deleteNode.getRightChild());
        }
         if(isRoot){
                mRoot=heresNode;
                return;
            }
        //最后就是确认位置,让要删除节点的父节点认识新儿子
        if (parent.getLeftChild() != null && parent.getLeftChild().getData() == data) {
            parent.setLeftChild(heresNode);
        } else {
            parent.setRightChild(heresNode);
        }
    }
}

相关文章

  • 数据结构与算法-二叉树02

    二叉树的定义 二叉树的特点 二叉树的五中基本形态 其他二叉树 斜二叉树 满二叉树 完全二叉树图片.png满二叉树一...

  • 二叉树

    二叉树 高度 深度真二叉树 满二叉树 完全二叉树 二叉树遍历前序 中序 后序层序遍历 翻转二叉树 递归法...

  • 二叉树 基础操作

    二叉树的使用 二叉树结构 先序创建二叉树 DFS 先序遍历二叉树 中序遍历二叉树 后序遍历二叉树 BFS 层次遍历...

  • 树与二叉树

    **树 ** 二叉树 满二叉树 完全二叉树 三种遍历方法 树与二叉树的区别 二叉查找树 平衡二叉树 红黑二叉树

  • 二叉树的宽度优先搜索(层次遍历,BFS)

    二叉树结构: 二叉树宽度优先搜索: 按照二叉树的层数依次从左到右访问二叉树的节点;例如:给定一个二叉树: 按照宽度...

  • 剑指 offer:39、平衡二叉树

    39. 平衡二叉树 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 解题思路: 平衡二叉树:Wiki:在...

  • Algorithm小白入门 -- 二叉树

    二叉树二叉树构造二叉树寻找重复子树 1. 二叉树 基本二叉树节点如下: 很多经典算法,比如回溯、动态规划、分治算法...

  • 14-树&二叉树&真二叉树&满二叉树

    一、树 二、二叉树 三、真二叉树 四、满二叉树

  • 二叉树的应用

    完美二叉树(满二叉树) 除了最下一层的节点外,每层节点都有两个子节点的二叉树为满二叉树 完全二叉树 除二叉树最后一...

  • 12.树Tree(2)

    目录:1.二叉树的基本概念2.二叉树的性质3.二叉树的创建4.二叉树的遍历 1.二叉树的基本概念 2.二叉树的性质...

网友评论

      本文标题:二叉树

      本文链接:https://www.haomeiwen.com/subject/vblppqtx.html