バイナリルックアップツリーを並べ替えた双方向チェーンテーブルのC#アルゴリズム実装

この問題はJulyがCSDNで発表したマイクロソフトのプログラミング面接100問題の第1題で、とても面白いと思って、今日も持ってきて遊びに来て、JulyのコードはC++で実現して、ポインタがあるせいか、比較的に全体の実現過程を理解しやすいように見えますが、私は、C#でこのような機能を完成してみました.
完全なテーマは以下の通りです.
二元ルックアップツリーをソートされた双方向チェーンテーブルに変換するには、新しいノードを作成できず、ポインタの指向だけを調整する必要があります.
      10
   / \
  6    14
 /\   /\4 8  12 16
ダブルチェーンテーブル4=6=8=10=12=14=16に変換
手動で符号化する前に、任意のノードの左サブツリーが現在のノードよりも小さく、右サブツリーが現在のノードよりも大きいという二叉ルックアップツリーの特徴を振り返ります.ある値をクエリーし、必要な時間の複雑さはO(lgN)です.
現在のノードの左サブツリーの範囲内で最も右のノード(左サブツリーの最大値ノードでもある)と、右サブツリーの範囲内で最も左のノード(右サブツリーの最小値ノードでもある)を取得し、この2つのノードの現在のノードの左右の順序を調整することに重点を置いて、ツリー構造から線形構造に変更する双方向チェーンテーブルが求められている.すなわち,8,10間と12,10間の関係を調整する.
アルゴリズムの考え方:

木の根ノードで、左右のサブツリーに分かれています.まず、現在のノードの左サブツリー範囲内で最も右のノードleftRを探し出し、右サブツリー範囲内で最も左のノードrightLを探し出す(この2つのステップは最初に置く.このとき、左右のサブツリー内の関係はまだ変わっていないので、先に取り出し、時間消費O(lgN).ノードを検索するだけで、スペースにはインデックスが1つしかなく、新しいメモリ割り当ては発生しません).

左サブツリーがリーフノードである場合、その右インデックスが親ノードを指し、左再帰が終了するように直接設定する.そうでなければ、このノードをルートノードとして、最初のステップを再帰的に呼び出します.

右サブツリーがリーフノードである場合、その左インデックスが親ノードを指し、右再帰が終了するように直接設定します.そうでなければ、このノードをルートノードとして再帰呼び出しの最初のステップです.

ルートノードを設定左ノードはleftR、leftRの右ノードはルートノード(その左ノード、bとcの2ステップの再帰過程で値が付与された)、ルートノードを設定右ノードはrightL、rightLの左ノードはルートノード(その右ノード、bとcの2ステップの再帰過程で値が付与された)

である.
C#ソース:
まず、ルートノードと左右のサブツリーノードを定義します.

        private int value;

        private MyLinkedNode left;

        private MyLinkedNode right;



        public MyLinkedNode(int value)

        {

            this.value = value;

        }



        public MyLinkedNode Left

        {

            get { return this.left; }

            set { this.left = value; }

        }



        public MyLinkedNode Right

        {

            get { return this.right; }

            set { this.right = value; }

        }

次のコードは論理再帰コードです.

        private static void ProcessTreeToLinked(MyLinkedNode node)

        {

            if (null==node)

            {

                return;

            }



            //          

            MyLinkedNode leftR = getMostRightNode(node.Left);



            //          

            MyLinkedNode rightL = getMostLeftNode(node.Right);



            //     ，       

            if (null == node.Left)

            {

                ProcessLeftNode(node.Left, node);

            }



            //      ，       

            if (null == node.Right)

            {

                ProcessRightNode(node.right, node);

            }



            //          ，        

            if (null != leftR)

            {

                leftR.Right = node;

                node.Left = leftR;

            }



            //           ，        

            if (null != rightL)

            {

                rightL.Left = node;

                node.Right = rightL;

            }

        }



        private static void ProcessRightNode(MyLinkedNode right, MyLinkedNode node)

        {

            //         ，             ，   

            if (isLeafNode(right))

            {

                right.Left = node;

                return;

            }



            ProcessTreeToLinked(right);

        }



        private static void ProcessLeftNode(MyLinkedNode left, MyLinkedNode node)

        {

            //         ，             ，   

            if (isLeafNode(left))

            {

                left.Right = node;

                return;

            }



            //        ，    

            ProcessTreeToLinked(left);

        }



        private static bool isLeafNode(MyLinkedNode node)

        {

            return (null == node.Left) && (null == node.Right);

        }



        private static MyLinkedNode getMostLeftNode(MyLinkedNode right)

        {

            if (null == right)

            {

                return null;

            }



            if (null == right.Left)

            {

                return right;

            }



            return getMostLeftNode(right.Left);

        }



        private static MyLinkedNode getMostRightNode(MyLinkedNode left)

        {

            if (null==left)

            {

                return null;

            }



            if (null==left.Right)

            {

                return left;

            }



            return getMostRightNode(left.Right);

        } 

　　
このコードを書くのは難しくありません.難しいのはどのように問題を解く構想をはっきりさせるかです.次の面接の準備をして、前回の面接でStringを実現すると聞かれました.Replace()メソッドですが、APIを呼び出すことはできません.テストスタッフとして、このようなコードの難易度は私にとってまだ大きいと言わざるを得ませんが、克服できないわけではありません.ただ、自分を向上させるために努力し続ける必要があります.軽く、自分に言って、がんばってください.