二叉树

  1. 云栖社区>
  2. 博客>
  3. 正文

二叉树

期待l 2018-12-07 16:55:08 浏览875
展开阅读全文
  • 本文也是自己自学的,如果有错误请及时指正谢谢~~

基本概念

  • 树是n(n>=0)个结点的有限集,当n=0时就是一个空树,在任意一颗非空树中

    • 有且仅有一个特定的称为根root的结点
    • 当n>1,其余结点可分为m(m>0)个互不相交的有限集T1,T2..,其中每个集合本身又是一棵树,并称为根的子树SubTree

markdown_img_paste_20181206102906199

-如上根结点是A,其他都是A结点的子树

  • 需要注意的是

    • 当n>0时,根结点是唯一的,坚决不可能存在多个根结点
    • 当m>0时,子树的个数是没有限制的,但他们互相说一定不会相交的,即一个结点发展出来的子树是不可能相交的,并且这两个子树的结点也是不可以相交的
  • 结点拥有的子树数称为节点的读Degree,树的度取树内各节点的度的最大值

    • 度为0时的结点称为叶结点leaf或终端结点
    • 度不为0的结点称为分支结点或非终端结点,除根结点外,分支结点也称为内部结点

markdown_img_paste_20181206104234540

  • 那么整个树的度就是取最大结点的度,所以整个树的度为3
  • 结点的子树的根称为结点的孩子child,那么该节点就为孩子child的双亲parent,同一双亲的孩子之间互称为兄弟sibling,即A是BC的双亲,BC是A的孩子,BC是兄弟
  • 节点的祖先是从根到该节点所经过分支上的所有节点.即D的祖先是A->B
  • 树的深度depth:就是从根结点发展出来到叶节点的最短距离,根节点是第一层,BC第二层,其他第三层,所以上面中的树深度为3
  • 如果将树中结点的各子树看成从左至右是有次序的,不能互换的,则称为该树为有序树,否则就称为无序树
  • 森林forest是m(m>0)棵互不相交的树的集合.对树中每个结点而言,其子树的集合即为森林,即BDEZ是一个森林,CFG 也是一个森林

二叉树

  • 在树结构中,二叉树是最简单的一种形式,在研究树结构的时候,二叉树也是重点,所以以二叉树为例学习
  • 什么是二叉树:看上面的图,如果把Z结点取到,那么和这个树就是一个二叉树,每个结点只能有两个子结点,分别称为左子树和右子树,因为他有左右之分,所以二叉树是一个有序树
  • 由于二叉树的结点的子结点只能有两个,所以二叉树的度一直都是2
  • 有左子树无右子树

markdown_img_paste_20181206161151220

  • 有右子树无左子树

markdown_img_paste_2018120616121126

  • 具有完整两个子结点

markdown_img_paste_20181206161223771

  • 满二叉树

markdown_img_paste_20181206161450812

  • 如上图,满二叉树的意思就是除了最下层的叶节点之外,每层的节点都有两个子结点
  • 完全二叉树

markdown_img_paste_20181206162028589

  • 如上图,完全二叉树的意思是在二叉树中除了最后一层外,其他各层的结点个数都达到了最大的个数,且最后一层叶结点按照从左往右的顺序连续存在,只缺最后一层右侧若干结点
  • 从上面我们也可以看到,满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树,因为其没有达到完全满分支的结构

二叉树的顺序存储

markdown_img_paste_20181206162557566

  • 如上是用数组存储的,可以将二叉树按层来存储,其先存储根节点然后依次往下,直到所有结点存储完毕
  • 那么我们怎么推算各个节点之间的关系呢?由于二叉树的结点树是固定的,所以总结如下

    • 对于D结点,他位于数组第四位,那么其父节点就是 4/2=2,所以它的父节点就是B
    • 对于A结点的左子树,由于A位于1的位置,那么他就是左子树就为2*1=2,所以为B
    • 对于A结点的左子树,由于A位于1的位置,那么他就是右子树就为2*1+1=3,所以为C
  • 那么上面的规律是怎么样的呢?假设n为全部节点数,然后树是按照顺序结构存储的,那么对于任意一个节点m来说

    • 如果m!=1,即不是根节点,那么节点的父节点为m/2
    • 如果2*m<=n,则节点m的左子树为2*m,如果2*m>n,说明没有左子树,也没有右子树
    • 如果2*m+1<=n,则节点m的右子树为2*m+1,如果2*m+1>n,则无右子树
  • 当你仔细考虑完上面的规律后,发现判断左子树和右子树位置,不过是根据二叉树的节点为2的间距来判断数组是够够长,如果没有左子树,那么右子树肯定也没有,但是事实不是这样的啊,我可能就有右子树没有左子树,那么咋办,其实上面的说法是没有问题的,这时候我们需要自己来构造左子树

markdown_img_paste_20181206164635503

  • 对于上面缺的节点,我们如果使用顺序结构存储,就需要伪造一个值存入数组就行了,比如

markdown_img_paste_2018120616585851

  • 补全的时候需要遵循完全二叉树的规则,即不能缺左侧的树,只能缺右侧若干的树,所以是上面的那种补法
  • 这时候就可以用上面的规律来算出各部分结点之间的关系
  • 但是很明显的缺点就是,为了补齐二叉树,数组内好多浪费空间的情况,所以这种顺序存储虽然简单但是只能适用于满二叉树的情况

二叉树的链式存储

  • 二叉树的链式结构包含结点元素及分别指向左子树和右子树的引用,甚至包含了父节点的引用,下面是我自己定义的二叉树链式结构

    public class Node {
          private final Integer element; //数据
          private Node parent;  //父节点引用
          private Node left;   //左结点引用
          private Node right;  //右结点引用
          public Node(Integer element, Node parent, Node left, Node right) {
              super();
              this.element = element;
              this.parent = parent;
              this.left = left;
              this.right = right;
          }
      }
  • 二叉树的添加

markdown_img_paste_20181207162841360

  • 二叉树的删除,会分为三种情况:满子节点的,只有一个子节点的和无子节点的

    • 无子节点的即叶结点

markdown_img_paste_20181207163014369

  • 只有一个子节点的,即只有一个左子树或右子树

markdown_img_paste_20181207163040224

  • 满子节点的,即左子树和右子树都存在的情况

markdown_img_paste_20181207163112327

  • 二叉树的遍历,分为四种:前序遍历,中序遍历,后序遍历,层级遍历

markdown_img_paste_20181207163244898

  • 这四种遍历方式,我就都画在一张图上了,因为这样好对比着看
  • 好了,上面画的图是二叉树的一些基本操作,在写代码的过程中,我想到了一个好点子(对我来说哈哈),下面代码中有体现的,请注意看满子节点删除的代码

    import java.util.LinkedList;
    public class MyBinaryTree {
        public class Node {
        ...
        }
        //根节点
        private Node root;
    
        public void add(Integer element) {
            add(element,root);
        }
    
        private void add(Integer element, Node initNode) {
            //根节点为空就新建
            if (root == null) {
                root = new Node(element, null, null, null);
                return;
            }
            Node node = initNode;
            while(node != null) {
                //代表往左子树中添加
                if (element < node.element) {
                    //左子树为空直接新建
                    if (node.left == null) {
                        node.left = new Node(element, node, null, null);
                        break;
                    }else {
                        //否则就挪到下一个node
                        node = node.left;
                    }
                    //代表往右子树中添加
                }else if (element > node.element) {
                    if (node.right == null) {
                        node.right = new Node(element, node, null, null);
                        break;
                    }else {
                        node = node.right;
                    }
                }
            }
        }
        public void remove (Integer element){
            //先查找出这个结点对象
            Node node = findNode(element);
            //如果没找到说明里面没有,所以直接返回
            if (node == null) return;
            //代表删除叶结点的逻辑
            if (node.left == null && node.right == null){
                removeLeafNode(node);
                //代表删除只有一个子结点的节点的逻辑
            }else if (node.left == null || node.right == null){
                removeSingleNode(node);
                //代表删除满子节点的逻辑
            }else if (node.left != null && node.right != null){
                removeFullNode(node);
            }
        }
        //删除满子节点
        private void removeFullNode(Node node) {
            Node parent = node.parent;
            Node left = node.left;
            Node right = node.right;
            node.left = null;
            node.right = null;
            //将被删除的节点的父节点的右结点指向被删除的节点的右结点
            parent.right = right;
            //现在就剩下了被删除节点的左结点没做处理
            //我们可以将被删除节点的右结点看做是一个root点,执行添加操作即可
            add(left.element,parent.right);
        }
        //删除只有一个子结点的节点
        private void removeSingleNode(Node node) {
            Node parent = node.parent;
            Node left = node.left;
            Node right = node.right;
            //因为只有一个节点有值,所以筛选出来
            Node singleNode = left == null ? right : left ;
    
            //判断被删除节点为父节点的左结点还是右结点
            if (parent.right.element.equals(node.element)){
                //右结点
                parent.right = singleNode;
            }else {
                //左结点
                parent.left = singleNode;
            }
        }
        //删除叶结点
        private void removeLeafNode(Node node) {
            Node parent = node.parent;
            //判断是那个方向的叶节点,直接赋值为null
            if (parent.left.element.equals(node.element)){
                parent.left = null;
            }else {
                parent.right = null;
            }
        }
        //按层遍历
        public void layerTraversal() throws InterruptedException {
            //利用LinkedList模拟队列,
            LinkedList<Node> list = new LinkedList<>();
            list.add(root);
            while (!list.isEmpty()){
                Node node = list.poll();
                if (node.left != null){
                    list.add(node.left);
                }
                if (node.right != null){
                    list.add(node.right);
                }
                System.out.println(node.element);
            }
        }
        //后序遍历
        public void endTraversals(){
            endTraversals(root);
        }
        //后序遍历
        private void endTraversals(Node node) {
            if (node == null)
                return;
            endTraversals(node.left);
            endTraversals(node.right);
            System.out.println(node.element);
        }
        //中序遍历
        public void middleTraversals(){
            middleTraversals(root);
        }
        //中序遍历
        private void middleTraversals(Node node) {
            if (node == null) return;
            middleTraversals(node.left);
            System.out.println(node.element);
            middleTraversals(node.right);
        }
        //前序遍历
        public void frontTraversals(){
            frontTraversals(root);
        }
        //前序遍历
        private void frontTraversals(Node node) {
            if (node == null)
                return;
            System.out.println(node.element);
            frontTraversals(node.left);
            frontTraversals(node.right);
        }
    
        //计算二叉树深度
        public int getDepth(){
            return getDepth(root);
        }
        //计算二叉树深度
        private int getDepth(Node node){
            if (node == null) return 0;
            int left , right;
            left = getDepth(node.left);
            right = getDepth(node.right);
            if (left > right) {
                return left + 1;
            }
                return right +1;
        }
        //查找节点根据element
        public Node findNode(Integer element){
            return  findNode(element,root);
        }
        //查找节点根据element
        private Node findNode (Integer element,Node node){
            if (node == null){
                return null;
            }
            //如果找到了直接返回该节点
            if (element.equals(node.element)){
                return node;
            }
            Node tmp = null;
            if ( element < node.element){
                //代表往左子树递归
                tmp = findNode(element,node.left);
            }else if (element > node.element ){
                //代表往右子树递归
                tmp = findNode(element,node.right);
            }
            //到这就说明没找到直接返回
            return tmp;
        }
        ////翻转二叉树
        public void invertTree(){
            invertTree(root);
        }
        //翻转二叉树
        private Node invertTree(Node root) {
            if (root == null) {
                return null;
            }
            root.left = invertTree(root.left);
            root.right = invertTree(root.right);
            Node tmp = root.left;
            root.left = root.right;
            root.right = tmp;
            return root;
        }
    }
附件下载: 演示文稿1.pp...[期待l].1544174276.pptx

网友评论

登录后评论
0/500
评论
期待l
+ 关注