0

二分木にノードを追加する簡単なプログラムを C# で作成しました。メインの親ノードを保持するオブジェクト フィールド「ルート」があります。ノードを追加するたびに、親ノードのデータを取得してツリーからトラバースします。

これが私のコードです

public class BTNode
    {
        public int Value { get; set; }        
        public BTNode Left { get; set; }
        public BTNode Right { get; set; }
        public BTNode Root { get; set; }
   }


public class BinaryTree
   {
       public  BinaryTree()
        {
            size = 0;
            Root = null; //To hold the main Parent Node
         }
        int size;
        object Root;

        public void AddNode(int value)
        {
            BTNode NewNode = new BTNode();
            if (Root != null)
            {
                NewNode = (BTNode)Root; //If tree exists, Get the Root Node
            }

            while (NewNode.Root != null)
            {
                if (value < NewNode.Value)
                {
                    NewNode.Root = NewNode.Left;
                }
                else if (value > NewNode.Value)
                {
                    NewNode.Root = NewNode.Right;
                }
            }

            size++;
            NewNode.Value = value;   //OBJECT 'ROOT' GETTING UPDATED AT THIS POINT
            NewNode.Root = NewNode;  //self pointer 
            NewNode.Left = null;
            NewNode.Right = null;

            if (size == 1)
            {
                Root = (object) NewNode;  //if this is the Parent Node(First Node) 
            }                             //then update the Root to be the parent Node
        }
    }

「ルート」にバイナリツリーの親ノードのみを保持したい..サイズ= 1の場合、つまりツリーの最初のノードである場合にのみ最後の行を実行したいが、何をしてもルートは毎回更新されるノード。なぜこれが起こっているのかを知るのに苦労しています。助けてください。ここにコンセプトやロジックがありませんか？

4

2 に答える 2

1
  1. プロパティRootはに入力できますBTNode。このようにあなたはそれをキャストする必要はありません
  2. この行NewNode = (BTNode)Root;はルートノード参照を取得しています。変更を加えるとNewNode、ルートノードに影響します。値型と参照型を知っていますか？
  3. なぜ上昇しているのか（をチェックしているのかRoot）、下降していないのか（左ノードまたは右ノードをチェックしているのか）がわかりません。

この解決策を確認してください。単純な再帰的方法を使用して、新しいノードを配置します。

public class BinaryTree
    {
        public BinaryTree()
        {
            size = 0;
            Root = null; //To hold the main Parent Node
        }
        int size;
        BTNode Root;

        public void AddNode(int value)
        {
            size++;
            BTNode NewNode = new BTNode()
            {
                Value = value
            };

            if (this.Root == null)
            {
                this.Root = NewNode;
                return;
            }

            this.PlaceNewNode(this.Root, NewNode);
        }

        public void PlaceNewNode(BTNode RootNode, BTNode NewNode)
        {
            if (NewNode.Value < RootNode.Value)
            {
                if (RootNode.Left != null)
                {
                    PlaceNewNode(RootNode.Left, NewNode);
                }
                else
                {
                    RootNode.Left = NewNode;
                    return;
                }
            }
            else
            {
                if (RootNode.Right != null)
                {
                    PlaceNewNode(RootNode.Right, NewNode);
                }
                else
                {
                    RootNode.Right = NewNode;
                    return;
                }
            }
        }
    }

お役に立てれば。

よろしく

于 2012-07-24T13:46:58.777 に答える
0

あなたのルートという言葉の使い方は紛らわしいと思います。ツリーは、ルート オブジェクトを 1 つだけ持つことができます。ノード オブジェクトは親ノードを持つことができます (ルートでない場合)。ツリー構造は、再帰コードに適しています。

Andre が投稿したものに似たコードを次に示します。

public class BTNode
{
    public BTNode() { }
    public BTNode(int value) { Value = value; }

    public int Value { get; set; }
    public BTNode Left { get; set; }
    public BTNode Right { get; set; }
    public BTNode Parent { get; set; }
}

public class BinaryTree
{
    public BinaryTree() { }

    public BTNode Root { get; private set; }
    public int Size { get; private set; }

    public void AddNode(int value)
    {
        BTNode insertNode = new BTNode(value);
        if (Root == null)
            Root = insertNode;
        else
            AddNodeToTree(Root, insertNode);
        Size++;
    }

    private void AddNodeToTree(BTNode parentNode, BTNode insertNode)
    {
        if (insertNode.Value >= parentNode.Value)
        {
            if (parentNode.Right != null)
                AddNodeToTree(parentNode.Right, insertNode);
            else
            {
                parentNode.Right = insertNode;
                insertNode.Parent = parentNode;
            }
        }
        else
        {
            if (parentNode.Left != null)
                AddNodeToTree(parentNode.Left, insertNode);
            else
            {
                parentNode.Left = insertNode;
                insertNode.Parent = parentNode;
            }
        }
    }

    public BTNode FindNode(int value)
    {
        return FindNode(Root, value);
    }

    public BTNode FindNode(BTNode parent, int value)
    {
        BTNode node = null;
        if (parent != null)
        {
            if (parent.Value == value)
                node = parent;
            else
            {
                if (parent.Value < value)
                    node = FindNode(parent.Right, value);
                else
                    node = FindNode(parent.Left, value);
            }
        }
        return node;
    }
}
于 2012-07-24T14:28:06.513 に答える