C ＃ implements definition, insertion and construction of binary sort tree

This article explains C# Implement binary sort tree definition 、 Insert 、 structure
Binary sort tree （Binary Sort Tree）, Also called binary search tree （Binary Search Tree）, Also called binary search tree . It's a kind of data structure . In general , Query efficiency is higher than linked list structure .
step ： If the key value of the root node is equal to the search key , success .
otherwise , If it is less than the key value of the root node , Recursively look up the left subtree .
If it is greater than the key value of the root node , Recursively look up the right subtree .
If the subtree is empty , Unsuccessful search .
Analysis of the average situation （ In the case of two successful searches ）：
In general , set up P（n,i） It has several children of the left tree i The average search length of . The number of nodes is n = 6 And i = 3; be P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6
Be careful ： here P(3)、P(2) Yes. 3 Nodes 、2 The average search length of binary classification tree with nodes . In general ,P（i） For having i The average search length of binary classification tree with nodes . Average search length = The sum of the depth of each node / Sum up points
（ The binary tree graph should be a left subtree P(3), Right subtree P(2)）
P(3) = （1+2+2）/ 3 = 5/3
P(2) = （1+2）/ 2 = 3/2∴ P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n
∴ P（n）= P（n,i）/ n <= 2(1+I/n)lnn
because 2(1+I/n)lnn≈1.38logn so P(n)=O(logn)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Binary sort tree structure
{
class Program
{
static void Main(string[] args)
{
}
///
/// Non recursive search algorithm for binary sort tree
///
///
///
///
///
static BSTNode BST_Search(BSTNode T,int key ,ref BSTNode p) {
p = null;
while (T!=null&&key!=T.data) {
p = T;
if (key < T.data) { T = T.lchild; }
else {
T = T.rchild;
}
}
return T;
}
///
/// Insert operation of binary sort tree
///
///
///
///
static bool BST_Insert(ref BSTNode T,int key) {
if (Tnull) {
T = new BSTNode();
T.data = key;
T.lchild = T.rchild = null;
return true;
}
if (T.datakey) { return false; }
if (T.data>key) { return BST_Insert(ref T.lchild,key); }
else { return BST_Insert(ref T.rchild, key); }
}
///
/// The construction of binary sort tree
///
///
///
///
static void Creat_BST(ref BSTNode T,int[] str,int n) {
T = null;
int i = 0;
bool ggg;
while (i<n) {
BST_Insert(ref T,str[i]);
i++;}}}
///
/// Binary tree structure definition
///
public class BSTNode{
public BSTNode() { }
public int data;
public BSTNode lchild;
public BSTNode rchild;
}

}