C ＃ clue binary tree through middle order traversal

This article explains
C# Cue the binary tree through middle order traversal
A binary tree with clues added to its nodes is called a threaded binary tree , In some way of traversing a binary tree （ In the same order 、 Middle preface 、 After the order or level, etc ） Traversal , The process of turning it into a threaded binary tree is called threaded binary tree . [1]
about n A binary tree of nodes , In the binary chain storage structure, there are n+1 An empty chain field , These empty chain fields are used to store the pointers of the precursor node and the successor node of the node in a certain traversal order , These pointers are called cues , A binary tree with clues is called a threaded binary tree .

This kind of binary list with clues is called clue list , The corresponding binary tree is called the clue binary tree (Threaded BinaryTree). According to the nature of the clue , Clue binary tree can be divided into preorder clue binary tree 、 There are three kinds of binary trees: middle order clue binary tree and post order clue binary tree .
Be careful ： The clue linked list solves the problem that the precursor and successor nodes of the node in a certain traversal sequence cannot be found directly , Solved the problem of binary linked list to find the left 、 The difficult problem of the right child .

///
/// Cue binary tree through middle order traversal
///
///
///
static void InThread(ref ThreadNode p, ref ThreadNode pre)
{
if (p != null)
{
InThread(ref p.lchild,ref pre);
if (p.lchild == null) { p.lchild = pre; p.ltag = 1; }
if (pre!=null&&pre.rchild==null) { pre.rchild = p;pre.rtag = 1; }
pre = p;
InThread(ref p.rchild, ref pre);
}
}
///
/// Create clue binary tree main logic
///
///
static void CreateInThread(ref ThreadNode T) {
ThreadNode pre = null;
if (T!=null) {
InThread(ref T,ref pre);
pre.rchild = null;
pre.rtag = 1;
}