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
        }
    }

我只想在“Root”中保留二叉树的父节点。我只想在 size =1 时执行最后一行,即如果它是树的第一个节点,但无论我做什么,Root 都会为每个节点更新节点。我很难知道为什么会这样,请帮助我。我错过了任何概念,这里的逻辑。

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

我认为您对 Root 一词的使用令人困惑。一棵树只能有一个根对象。节点对象可以有一个父节点(除非它是根节点)。树结构非常适合递归代码。

这是一些类似于 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 回答