二叉搜索树（Binary Search Tree）

二叉搜索树（Binary Search Tree）又称二叉查找树、二叉排序树它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均大于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均小于它的根结点的值； 它的左、右子树也分别为二叉排序树（下文称BST）。

（一）BST的储存结构
通常一个BST节点是由左右子节点和上父节点加上一个值组成。

储存结构.png

（二）BST的添加节点
由于BST自身的特性，每一个插入节点都会插入一个当前树的空节点位置，位置的选择满足左大右小（或右大左小）。

添加节点.png

（三）BST的递归遍历
BST的递归遍历很简单，直接看代码吧。

递归遍历.png

（四）BST的迭代遍历
BST的两种遍历都比较重要，迭代遍历要考虑到的因素要比递归迭代多很多。我这里采取的是移动节点的方式依次取到所有的极左位置（已取过的值不算）。

迭代遍历.png

遍历之后输出

演示png

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
/// <summary>
/// Binary Search Tree
/// </summary>
public class BSTree {

    public int value;
    /// <summary>
    /// max
    /// </summary>
    public BSTree left;
    /// <summary>
    /// min
    /// </summary>
    public BSTree right;
    /// <summary>
    /// top
    /// </summary>
    public BSTree parent;

    public BSTree(int value) {
        this.value = value;
    }

    public static BSTree BuildBST(List<int> iSet) {
        BSTree tree = new BSTree(iSet[0]);
        for(int i = 1; i < iSet.Count; i++) {
            tree.Append(iSet[i]);
        }
        return tree;
    }

    /// <summary>
    /// 向BSTree添加一个节点
    /// </summary>
    /// <param name="v"></param>
    /// <returns></returns>
    public BSTree Append(int v) {
        BSTree t = this,parent=null;
        bool left = false;
        //循环出一个适合的空位置t
        while (t != null) { 
            parent = t;
            if (t.value == v)   //若包含此元素则不添加
                return this;
            if (t.value > v) {  
                t = t.right;
                left = false;
            } else {
                t = t.left;
                left = true;
            }
        }
        t = new BSTree(v);
        t.parent = parent;
        if (left) parent.left = t; else parent.right = t;
        return t;
    }

    /// <summary>
    /// 遍历方法的迭代版本
    /// </summary>
    /// <returns></returns>
    public List<int> ToList() {
        List<int> result = new List<int>();
        BSTree tree = this;
        while (!(tree == this && result.Contains(tree.value))) {   //当指针回到根节点并且已经被取过时结束
            if(tree.left == null || result.Contains(tree.left.value)) {    //若左方向为空或已被包含，则当前位为最位（左，右）
                if(!result.Contains(tree.value))
                    result.Add(tree.value);
                if(tree.right !=null && !result.Contains(tree.right.value)) {   //若右方向（同上）,并向右移动
                    tree = tree.right;  //移位
                    continue;
                } else {    //往上方向移动
                    tree = tree.parent;
                }
            } else if(tree.left != null) {    //向左方向移动
                tree = tree.left;
            }
        }
        return result;
       }

    /// <summary>
    /// 遍历方法的递归方式
    /// </summary>
    /// <returns></returns>
    public List<int> ToList_Recursion() {
        List<int> result = new List<int>();
        if(this.left != null) {
            result.AddRange(this.left.ToList_Recursion());
        }
        result.Add(this.value);
        if (this.right != null) {
            result.AddRange(this.right.ToList_Recursion());
        }
        return result;
    }

    /// <summary>
    /// 重写object类的ToString方法
    /// </summary>
    /// <returns></returns>
    public override string ToString() {
        var list = ToList_Recursion();
        StringBuilder sb = new StringBuilder();
        foreach (var i in list) sb.Append(i.ToString() + " ");
        return sb.ToString();
    }
}