C # indexe l'arbre binaire en traversant l'ordre moyen

Cet article explique
C#Indice de l'arbre binaire par traversée de l'ordre médian
Un arbre binaire qui ajoute des indices aux noeuds d'un arbre binaire est appelé Arbre binaire des indices,Sur un arbre binaire d'une manière ou d'une autre（Comme d'habitude.、Dans l'ordre、Ordre ou hiérarchie, etc.）Traverser,Le processus de transformation de l'arbre binaire en arbre binaire est appelé indice de l'arbre binaire. [1]
PournArbre binaire à noeuds,Il y an+1Champs de chaînes vides,Utilisez ces champs de chaînes vides pour stocker des pointeurs vers les noeuds précurseurs et les noeuds suivants du noeud dans un certain ordre de traversée,Ces pointeurs sont appelés indices,Un arbre binaire avec des indices s'appelle un arbre binaire avec des indices.

Cette liste binaire avec des indices s'appelle la liste des indices,L'arbre binaire correspondant est appelé Arbre binaire indice(Threaded BinaryTree).Selon la nature de l'indice,L'arbre binaire des indices peut être divisé en arbre binaire des indices pré - ordonnés、Arbre binaire à indice intermédiaire et arbre binaire à indice postérieur trois espèces.
Attention!：La liste des indices résout le problème de ne pas trouver directement les noeuds avant et après le noeud dans une séquence de traversée,Résolution de la liste binaire à gauche、Problèmes difficiles avec les enfants de droite.

///
/// Indexer l'arbre binaire en traversant l'ordre médian
///
///
///
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);
}
}
///
/// Créer la logique principale de l'arbre binaire des indices
///
///
static void CreateInThread(ref ThreadNode T) {
ThreadNode pre = null;
if (T!=null) {
InThread(ref T,ref pre);
pre.rchild = null;
pre.rtag = 1;
}