Mars Mission (1) : surface landing

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Mars_Mission
{
	public class classTernarySearchTree
	{
		static char chrNull = '\0';
		/// <summary>
		/// searches for a word in the database by interating through each char of the input word from left to right
		/// </summary>
		/// <param name="cLeaf">reference tree-leaf from which search is begun</param>
		/// <param name="strWord">word to be searched is left-chopped by one char for each iteration until null string or end of search</param>
		/// <returns>true if word is found, otherwise false</returns>
		public static bool wordInTree(ref classTernarySearchTreeLeaf cLeaf, string strWord)
		{
			// test first char of word against input Leaf's char field
			if (strWord[0] > cLeaf.chr)
			{ // first char belongs below this leaf
				if (cLeaf.down != null)
					return wordInTree(ref cLeaf.down, strWord);
				else
					return false;
			}
			else if (strWord[0] < cLeaf.chr)
			{ // first char belongs above this leaf
				if (cLeaf.up != null)
					return wordInTree(ref cLeaf.up, strWord);
				else
					return false;
			}
			else if (strWord[0] == cLeaf.chr)
			{ // first char matches this leaf
				if (strWord.Length == 1) // last char in input word
					return true;
				else // iterate along 'next' leaf for second char
					return wordInTree(ref cLeaf.next, strWord.Substring(1));
			}

			return false;
		}

		/// <summary>
		/// inserts word into database by iterating along tree proceeding one char at a time from left to right of input word
		/// </summary>
		/// <param name="cLeaf">reference to leaf from which insertino is to begin</param>
		/// <param name="strWord">word to be inserted</param>
	public static void insertWord(ref classTernarySearchTreeLeaf cLeaf, string strWord)
		{
			// test first char of word against this leaf
			if (strWord[0] > cLeaf.chr)
			{ // first char belongs below this one
				if (cLeaf.down != null)
					insertWord(ref cLeaf.down, strWord); // iterate through tree with current word
				else
				{ // there is no leaf going down -> create new leaf 
					classTernarySearchTreeLeaf cDown = new classTernarySearchTreeLeaf(strWord[0]);
					// set this leaf's down field to new leaf
					cLeaf.down = cDown;
					// if there are more letters in word, iterate through tree with current word
					if (strWord.Length > 1)
						insertWord(ref cDown, strWord);
				}
			}
			else if (strWord[0] < cLeaf.chr)
			{ // first char belongs above this leaf
				if (cLeaf.up != null)
					insertWord(ref cLeaf.up, strWord); // iterate through tree with current word
				else
				{ // there is no leaf going up -> create new leaf
					classTernarySearchTreeLeaf cUp = new classTernarySearchTreeLeaf(strWord[0]);
					// set this leaf's up field to new leaf
					cLeaf.up = cUp;
					// if there are more letters in word, iterate through tree with current word
					if (strWord.Length > 1)
						insertWord(ref cUp, strWord);
				}
			}
			else if (strWord[0] == cLeaf.chr)
			{ // first char is identical to this leaf's chr field
				if (strWord.Length > 1)
				{ // the word insertion is not complete
					if (cLeaf.next != null)
					{
						insertWord(ref cLeaf.next, strWord.Substring(1)); // iterate through tree with chopped word
					}
					else
					{ // there is no leaf going next -> create new leaf
						classTernarySearchTreeLeaf cNext = new classTernarySearchTreeLeaf(strWord[1]);
						// set this leaf's next field to new leaf
						cLeaf.next = cNext;
						// iterate through tree with current word
						insertWord(ref cNext, strWord.Substring(1)); // iterate through tree with chopped word
					}
				}
			}
		}

		public static void traverseTree(ref classTernarySearchTreeLeaf cLeaf, ref string[] strWords, string strThisWord)
		{
			if (cLeaf.up != null)
				traverseTree(ref cLeaf.up, ref strWords, strThisWord);

			string strExtendedWord = strThisWord + cLeaf.chr.ToString();
			if (cLeaf.chr == chrNull)
			{
				Array.Resize<string>(ref strWords, strWords.Length + 1);
				strWords[strWords.Length - 1] = strExtendedWord;
			}
			else
				if (cLeaf.next != null)
					traverseTree(ref cLeaf.next, ref strWords, strExtendedWord);

			if (cLeaf.down != null)
				traverseTree(ref cLeaf.down, ref strWords, strThisWord);
		}
	}

	public class classTernarySearchTreeLeaf
	{
		public classTernarySearchTreeLeaf down;
		public classTernarySearchTreeLeaf up;
		public classTernarySearchTreeLeaf next;
		public char chr;
		public object objData;

		public classTernarySearchTreeLeaf(char c)
		{
			chr = c;
		}
	}
}