在树之前的笔记中讲到，树这种结构对比数组，链表，增删改查都很快。

二叉排序树简介

二叉排序树：BST，对于二叉排序树的任何一个非叶子节点要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。如果有相同的值，可以放在左右子节点都可以，但是要满足前面的条件。
二叉排序数插入图解

思路

添加

  1. 传入一个节点，这个节点得值和当前节点的值进行比较
  2. 如果传入节点的值比当前节点得值小
    1. 如果当前节点的左子节点为null，就把传入节点赋值给当前节点的左子节点
    2. 否则就向当前节点的左子节点递归添加

  3. 第2步否则（就是传入的节点的值大于等于当前节点的值）

    1. 如果当前节点的右子节点为null，就把传入节点赋值给当前节点的右子节点
    2. 否则就向当前节点的右子节点递归添加

      删除

      删除节点有三种情况

  4. 删除叶子节点

    1. 找到要删除节点target和它的父节点parent
    2. 确定target是parent的左右哪个子节点
    3. 根据前面的情况parent.left=null;或者parent.right=null;

  5. 删除只有一棵子树的节点

    1. 找到要删除节点target和它的父节点parent
    2. 确认target是parent的左右子节点
    3. 确定target的子树是它的左右子节点
    4. 然后target的对应子树的指针，赋值给parent对应taeget的哪个指针

  6. 删除有两棵子树的节点

    1. 找到要删除节点target和它的父节点parent
    2. 从target的右子树找到最小的节点（从左子树找，就要找到左子树最大的值，下面步骤同理）
    3. 用一个临时变量，将这个最小节点的值保存
    4. 删除该最小节点
    5. 这个临时变量赋值给target的值

代码

二叉排序树中序遍历出来就是拍好的顺序

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Text;
  5. namespace ConsoleApp1
  6. {
  7.     public class BST
  8.     {
  9.         public Node root;
  11.         //添加
  12.         public void add (Node node)
  13.         {
  14.             if (root == null)
  15.                 root = node;
  16.             else
  17.                 root.add(node);
  18.         }
  19.         //中序遍历
  20.         public void infixOrder()
  21.         {
  22.             if (root == null)
  23.             {
  24.                 Console.WriteLine("二叉树为空");
  25.                 return;
  26.             }
  27.             root.infixOrder();     
  28.         }
  29.         //查找要删除的节点
  30.         public Node search(int val)
  31.         {
  32.             if (root == null)
  33.                 return null;
  34.             else
  35.                 return root.search(val);
  36.         }
  37.         //查找要删除节点的父节点
  38.         public Node searchParent(int val)
  39.         {
  40.             if (root == null)
  41.                 return null;
  42.             else
  43.                 return root.searchParent(val);
  44.         }
  45.         //删除右边节点的最小的一个节点
  46.         //返回以node为根节点的二叉排序树的最小节点的值，并且删除这个节点
  47.         public int delRightTreeMin(Node node)
  48.         {
  49.             Node target = node;
  50.             while (target.left != null)
  51.             {
  52.                 target = target.left;
  53.             }
  54.             //这是target就指向了最小的节点
  55.             //删除这个最小节点,并且返回这个节点的值
  56.             delNode(target.id);
  57.             return target.id;
  58.         }
  59.         //删除节点
  60.         public void delNode(int val)
  61.         {
  62.             if (root == null)
  63.                 return;
  64.             else
  65.             {
  66.                 //找要删除的节点target和它的父节点parent
  67.                 Node target = search(val);
  68.                 if (target == null)//都没有找到要删除的节点，下面的代码也不用执行了
  69.                     return;
  70.                 //如果这个二叉树只有一个节点
  71.                 if (root.left == null && root.right == null)
  72.                 {
  73.                     root = null;
  74.                     return;
  75.                 }
  76.                 Node parent = searchParent(val);
  77.                 //要删除的节点是叶子节点
  78.                 if (target.left == null && target.right == null)
  79.                 {
  80.                     if (parent.left == target)
  81.                         parent.left = null;
  82.                     if (parent.right == target)
  83.                         parent.right = null;
  84.                 }
  85.                 //如果要删除的节点有两棵子树
  86.                 else if (target.left != null && target.right != null)
  87.                 {
  88.                     int minval = delRightTreeMin(target.right);
  89.                     target.id = minval;
  90.                 }
  91.                 //要删除的节点只有一棵子树
  92.                 else
  93.                 {
  94.                     if(target.left!=null)//要删除的节点有左子树
  95.                     {
  96.                         if (parent != null)
  97.                         {
  98.                             if (parent.left == target)
  99.                                 parent.left = target.left;
  100.                             if (parent.right == target)
  101.                                 parent.right = target.left;
  102.                         }
  103.                         else
  104.                             root = target.left;
  105.                     }
  106.                     else//要删除的节点有右子树
  107.                     {
  108.                         if (parent != null)
  109.                         {
  110.                             if (parent.left == target)
  111.                                 parent.left = target.right;
  112.                             if (parent.right == target)
  113.                                 parent.right = target.right;
  114.                         }
  115.                         else
  116.                             root = target.right;
  118.                     }
  119.                 }
  120.             }
  121.         }
  122.     }
  124.     public class Node
  125.     {
  126.         public int id;
  127.         public Node left;
  128.         public Node right;
  129.         public Node(int id)
  130.         {
  131.             this.id = id;
  132.         }
  134.         //二叉排序树添加
  135.         public void add(Node node)
  136.         {
  137.             if (node == null)
  138.                 return;
  139.             //判断传入的节点的值，和当前子树的根节点的关系
  140.             if (node.id < this.id)
  141.             {
  142.                 //如果当前的左子节点为null
  143.                 if (this.left == null)
  144.                     this.left = node;
  145.                 else
  146.                     this.left.add(node);//递归向左子节点添加
  147.             }
  148.             else
  149.             {
  150.                 if (this.right == null)
  151.                     this.right = node;
  152.                 else
  153.                     this.right.add(node);//递归向右节点添加
  154.             }
  155.         }
  156.         //中序遍历
  157.         public void infixOrder()
  158.         {
  159.             //1.如果当前节点的左子节点不为空，则递归继续中序遍历
  160.             if (this.left != null)
  161.                 this.left.infixOrder();
  162.             //2.输出当前节点
  163.             Console.WriteLine(this.id);
  164.             //3.如果当前节点的右子节点不为空,则递归继续中序遍历
  165.             if (this.right != null)
  166.                 this.right.infixOrder();
  167.         }
  169.         //查找节点
  170.         public Node search(int val)
  171.         {
  172.             if (val == this.id)
  173.                 return this;
  174.             else if (val < this.id)
  175.             {
  176.                 if (this.left == null)
  177.                     return null;
  178.                 return this.left.search(val);
  179.             }
  180.             else
  181.             {
  182.                 if (this.right == null)
  183.                     return null;
  184.                 return this.right.search(val);
  185.             } 
  186.         }
  187.         //查找要删除节点的父节点
  188.         public Node searchParent(int val)
  189.         {
  190.             //如果当前节点就是要删除的节点的父节点，就返回
  191.             if (this.left != null && this.left.id == val || this.right != null && this.right.id == val)
  192.                 return this;
  193.             else
  194.             {
  195.                 if (val < this.id && this.left != null)//左递归
  196.                     return this.left.searchParent(val);
  197.                 else if (val >= this.id && this.right != null)//右递归
  198.                     return this.right.searchParent(val);
  199.                 else//没有父节点
  200.                     return null;
  201.             }
  202.         }
  204.     }
  205. }