• 本文也是自己自学的,如果有错误请及时指正谢谢~~

基本概念

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

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

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

• 需要注意的是

  • 当n>0时,根结点是唯一的,坚决不可能存在多个根结点
  • 当m>0时,子树的个数是没有限制的,但他们互相说一定不会相交的,即一个结点发展出来的子树是不可能相交的,并且这两个子树的结点也是不可以相交的

• 结点拥有的子树数称为节点的读Degree,树的度取树内各节点的度的最大值

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

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

二叉树

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

• 有右子树无左子树

• 具有完整两个子结点

• 满二叉树

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

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

二叉树的顺序存储

• 如上是用数组存储的,可以将二叉树按层来存储,其先存储根节点然后依次往下,直到所有结点存储完毕

• 那么我们怎么推算各个节点之间的关系呢?由于二叉树的结点树是固定的,所以总结如下

  • 对于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的间距来判断数组是够够长,如果没有左子树,那么右子树肯定也没有,但是事实不是这样的啊,我可能就有右子树没有左子树,那么咋办,其实上面的说法是没有问题的,这时候我们需要自己来构造左子树

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

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

二叉树的链式存储

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

  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;
        }
    }

• 二叉树的添加

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

  • 无子节点的即叶结点

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

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

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

• 这四种遍历方式,我就都画在一张图上了,因为这样好对比着看

• 好了,上面画的图是二叉树的一些基本操作,在写代码的过程中,我想到了一个好点子(对我来说哈哈),下面代码中有体现的,请注意看满子节点删除的代码

  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;
      }
  }