二叉搜索樹（Binary Search Tree）又稱二叉查找樹催享、二叉排序樹它或者是一棵空樹倒谷，或者是具有下列性質(zhì)的二叉樹： 若它的左子樹不空巷燥，則左子樹上所有結(jié)點的值均大于它的根結(jié)點的值陨献； 若它的右子樹不空俯艰，則右子樹上所有結(jié)點的值均小于它的根結(jié)點的值捡遍； 它的左、右子樹也分別為二叉排序樹（下文稱BST）竹握。

（一）BST的儲存結(jié)構(gòu)
通常一個BST節(jié)點是由左右子節(jié)點和上父節(jié)點加上一個值組成画株。

儲存結(jié)構(gòu).png

（二）BST的添加節(jié)點
由于BST自身的特性，每一個插入節(jié)點都會插入一個當(dāng)前樹的空節(jié)點位置啦辐，位置的選擇滿足左大右形酱（或右大左小）芹关。

添加節(jié)點.png

（三）BST的遞歸遍歷
BST的遞歸遍歷很簡單续挟，直接看代碼吧。

遞歸遍歷.png

（四）BST的迭代遍歷
BST的兩種遍歷都比較重要侥衬，迭代遍歷要考慮到的因素要比遞歸迭代多很多诗祸。我這里采取的是移動節(jié)點的方式依次取到所有的極左位置（已取過的值不算）。

迭代遍歷.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添加一個節(jié)點
    /// </summary>
    /// <param name="v"></param>
    /// <returns></returns>
    public BSTree Append(int v) {
        BSTree t = this,parent=null;
        bool left = false;
        //循環(huán)出一個適合的空位置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))) {   //當(dāng)指針回到根節(jié)點并且已經(jīng)被取過時結(jié)束
            if(tree.left == null || result.Contains(tree.left.value)) {    //若左方向為空或已被包含轴总，則當(dāng)前位為最位（左直颅，右）
                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();
    }
}