1. 二叉树

二叉树结构：image.png

  1. 概念：任何一个节点的子节点数量不超过2
  2. 特点：子节点分左节点和右节点。左右节点不能随意颠倒位置image.png
  3. 满二叉树：所有叶子节点都在最后一层，而且节点的总数为2-1，n是树的高度
  4. 完全二叉树：所有叶子节点都在最后一层或倒数第二层，且最后一层的叶子节点在左边连续，倒数第二节的叶子节点在右边连续
  5. 遍历二叉树：image.png

    前序遍历：1 2 4 5 3 6 7 中序遍历：4 2 5 1 6 3 7 后序遍历：4 5 2 6 7 3 1 层序遍历：1 2 3 4 5 6 7

前序遍历、前序遍历，后序遍历和层序遍历，以及其他操作

  1. package pegatron.sw.learn;
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  6. public class TreeNode {
  8.     //数的权（值）
  9.     int data;
  11.     //创建左儿子
  12.     TreeNode leftNode;
  13.     //创建右儿子
  14.     TreeNode rightNode;
  16.     public TreeNode() {
  17.     } 
  19.     public TreeNode(int data) {
  20.         this.data=data;
  21.     } 
  23.     public void setLeftNode(TreeNode leftNode) {
  24.         this.leftNode = leftNode;
  25.     }
  27.     public void setRightNode(TreeNode rightNode) {
  28.         this.rightNode = rightNode;
  29.     }
  30.     //获取二叉树高度
  31.     public int depth(TreeNode node){
  32.         if(node != null){
  33.             int l=depth(node.leftNode);
  34.             int r=depth(node.rightNode);
  35.             if(l>r){
  36.                 return l+1;
  37.             }else{
  38.                 return r+1;
  39.             }
  40.         }
  41.         return 0;
  42.     }
  43.     //前序遍历(递归方法)  根节点 -> 左节点  -> 左子节点 -> 右子节点  -> 右节点-> 左子节点 -> 右子节点  
  44.     public void frontShow() {
  45.         System.out.println(data);//先打印自己
  46.         //在打印左节点
  47.         if(leftNode != null){
  48.             leftNode.frontShow();
  49.         }
  50.         //在遍历右节点
  51.         if(rightNode != null){
  52.             rightNode.frontShow();
  53.         }
  54.     }
  55.     //中序遍历（递归方法）左节点  -> 根节点 ->右节点
  56.     public void middleShow() {
  57.         //先遍历左节点
  58.         if(leftNode != null){
  59.             leftNode.middleShow();
  60.         }
  61.         //打印当前节点数据
  62.         System.out.println(data);
  63.         //在遍历右节点
  64.         if(rightNode != null){
  65.             rightNode.middleShow();
  66.         }
  67.     }
  69.     //后序遍历（递归方法） 左节点 -> 右节点 -> 根节点
  70.     public void afterShow() {
  71.         //先遍历左节点
  72.         if(leftNode != null){
  73.             leftNode.afterShow();
  74.         }
  75.         //在遍历右节点
  76.         if(rightNode != null){
  77.             rightNode.afterShow();
  78.         }
  79.         //后打印当前节点
  80.         System.out.println(data);
  81.     }
  82.     //层序遍历（递归方法）  根节点 -> 左节点  -> 右节点-> 左子节点 -> 右子节点  -> 左子节点 -> 右子节点  
  83.     public void levelShow(TreeNode node) {
  84.         if(node == null) return;
  85.         Queue<TreeNode> queue=new LinkedList<TreeNode>();
  86.         queue.add(node);
  87.         while(!queue.isEmpty()){
  88.             TreeNode root=queue.poll();
  89.             System.out.println(root.data);
  90.             if(root.leftNode != null){
  91.                 queue.add(root.leftNode);
  92.             }
  93.             if(root.rightNode!=null){
  94.                 queue.add(root.rightNode);
  95.             }
  97.         }
  99.     }
  101.     //二叉树的镜像
  102.     public TreeNode jingxiang(TreeNode node){
  103.          if(node == null){
  104.              return null;
  105.          }
  106.          TreeNode root=node.leftNode;
  107.          node.leftNode=node.rightNode;
  108.          node.rightNode=root;
  109.          jingxiang(node.leftNode);
  110.          jingxiang(node.rightNode);
  111.         return node;
  112.     }
  114.     //前需查找
  115.     public TreeNode frontSearch(int i) {
  116.         //先创建一个值作为找到的值
  117.         TreeNode value=null;
  118.         //判断当前值是否与要查的值一样
  119.         if(this.data == i){
  120.             return this;//如果一样则返回
  121.         //如果不一样
  122.         }else {
  123.             //就先查询左节点中又是否有要查的值
  124.             if(leftNode != null){
  125.                 //有可能查到，也可能查不到，查不到的话，value还是一个null
  126.                 value=leftNode.frontSearch(i);
  127.             }
  128.             //如果不为空，说明左节点中已经查到，
  129.             if(value != null){
  130.                 return value;
  131.             }
  132.             //如果左节点没有就查询右节点
  133.             if(rightNode != null){
  134.                 value=rightNode.frontSearch(i);
  135.             }
  136.         }
  137.         return value;
  138.     }
  140.     //中序查找
  141.     public TreeNode midSearch(int i) {
  142.         //先创建一个值作为找到的值
  143.         TreeNode value=null;
  144.         //就先查询左节点中又是否有要查的值
  145.         if(leftNode != null){
  146.             //有可能查到，也可能查不到，查不到的话，value还是一个null
  147.             value=leftNode.midSearch(i);
  148.         }
  149.         //如果不为空，说明左节点中已经查到，
  150.         if(value != null){
  151.             return value;
  152.         }
  153.         if(this.data == i){
  154.             return this;
  155.         }
  156.         //如果左节点没有就查询右节点
  157.         if(rightNode != null){
  158.             value=rightNode.midSearch(i);
  159.         }
  160.         return value;
  161.     }
  163.     //后序查找
  164.     public TreeNode afterSearch(int i) {
  165.         //先创建一个值作为找到的值
  166.         TreeNode value=null;
  167.         if(leftNode != null){
  168.             //有可能查到，也可能查不到，查不到的话，value还是一个null
  169.             value=leftNode.midSearch(i);
  170.         }
  171.         //如果不为空，说明左节点中已经查到，
  172.         if(value != null){
  173.             return value;
  174.         }
  175.         //如果左节点没有就查询右节点
  176.         if(rightNode != null){
  177.             value=rightNode.midSearch(i);
  178.         }
  179.         //如果不为空，说明右节点中已经查到，
  180.         if(value != null){
  181.             return value;
  182.         }
  183.         if(this.data == i){
  184.             return this;
  185.         }
  187.         return value;
  188.     }
  190.     /**删除树
  191.      * @param i 要删除的节点的数据
  192.      * 
  193.      * 逻辑：先判断左节点的数据是否是要删除的数据，如果是则让左儿子为空即为删除。右儿子同理
  194.      *         如果上面条件不符合，则递归检查删除左右儿子
  195.      * 
  196.      */
  197.     public void delete(int i) {
  198.         TreeNode parent=this;
  199.         //判断左儿子
  200.         if(parent.leftNode != null && parent.leftNode.data ==i){
  201.             parent.leftNode=null;
  202.             return;
  203.         }
  205.         //判断右儿子
  206.         if(parent.rightNode!= null &&parent.rightNode.data == i){
  207.             parent.rightNode=null;
  208.             return;
  209.         }
  211.         //递归检查并删除左儿子
  212.         parent=leftNode;
  213.         if(parent != null){
  214.             parent.delete(i);
  215.         }
  217.         //递归检查并删除左儿子
  218.         parent=rightNode;
  219.         if(parent != null){
  220.             parent.delete(i);
  221.         }
  223.     }
  224. }

顺序存储二叉树

  1. 顺序存储的二叉树通常情况只考虑完全二叉树
  2. 特点：
    1. 第n个元素的左子节点是：2*n+1
    2. 第n个元素的右子节点是：2*n+2
    3. 第n个元素的父节点是：（n-1）/2