时间戳

首页 > 解决方案 > 如何连接叶子并返回 BST 周围节点的列表

c# - 如何连接叶子并返回 BST 周围节点的列表

问题描述

这是我对 BST（二叉搜索树）的实现。谁能帮我创建两种方法，一种是连接叶子，另一种是返回树周围的节点列表，例如：连接叶子示例在这张图片中，它显示了叶子应该如何连接，应该存储在列表中的节点以及存储在 List 中的节点的方式需要以这种方式，其中根是第一个元素，然后向左向下传递到从右侧返回根的叶子。在我的示例中，它应该是 8（根）、3、1、4、7、13、14、10、8（根）。谢谢你！

**class Node
{
    private int VL;
    private int Niv;
    public Node Parent, LC, RC;

    public Node()
    {
        this.Parent = this.LC = this.RC = null;
        this.Niv = -1;
    }
    public Node(int x)
    {
        this.VL = x;
        this.Parent = this.LC = this.RC = null;
        this.Niv = -1;
    }

    public int Vlera
    {
        get { return this.VL; }
        set { this.VL = value; }
    }

    public int Niveli
    {
        get { return this.Niv; }
        set { this.Niv = value; }
    }

}

class BSTree
{
    public Node Root;
    private int MaxNiv;

    public BSTree()
    {
        this.Root = null;
        this.MaxNiv = -1;
    }

    public void Insert(int x)
    {
        Node tmp = new Node(x);
        if (this.Root == null)
        {
            tmp.Niveli = 0;
            this.Root = tmp;
        }
        else InsertNode(tmp);

        if (tmp.Niveli > this.MaxNiv) MaxNiv = tmp.Niveli;

    }
    public void ConnectLeafs()
    {
        //TODO
    }
    public List<T> ReturnNodesAroundTheTree()
    {
        //TODO
    }
    public Node GoTo_Node(Node nd)
    {
        return GoTo_Node_Rec(this.Root, nd);
    }
    public Node GoTo_Node(int x)
    {
        return GoTo_Node_Rec(this.Root, x);
    }

    private Node GoTo_Node_Rec(Node root, Node nd)
    {
        if (root.Vlera == nd.Vlera) return root;
        if (root.Vlera > nd.Vlera) return GoTo_Node_Rec(root.LC, nd);
        else return GoTo_Node_Rec(root.RC, nd);
    }
    private Node GoTo_Node_Rec(Node root, int x)
    {
        if (root.Vlera == x) return root;
        if (root.Vlera > x) return GoTo_Node_Rec(root.LC, x);
        else return GoTo_Node_Rec(root.RC, x);
    }

    private void InsertNode(Node nd)
    {

        Node tmp = InsertRecNode(this.Root, nd.Vlera);

        if (nd.Vlera >= tmp.Vlera) tmp.RC = nd;
        else tmp.LC = nd;
        nd.Parent = tmp;
        nd.Niveli = nd.Parent.Niveli++;
        //if (nd.Niveli > this.MaxNiv) MaxNiv = nd.Niveli;

    }

    private Node InsertRecNode(Node root, int x)
    {

        if (x >= root.Vlera)
            if (root.RC != null) return InsertRecNode(root.RC, x);
            else return root;
        else
            if (root.LC != null) return InsertRecNode(root.LC, x);
        else return root;
    }
    private bool IsRoot(Node nd)
    {
        if (nd.Parent == null) return true;
        return false;

    }
    private bool IsLeaf(Node nd)
    {
        if (nd.LC == null && nd.RC == null) return true;
        return false;
    }**

标签： c#algorithm

解决方案

这是执行此操作的简单方法。我创建了所有节点的列表。当您创建一个新节点时，将节点添加到列表中。请参阅下面的代码

    class BSTree
    {
        public Node Root;
        private int MaxNiv;
        private List<Node> nodes = new List<Node>();

        public BSTree()
        {
            this.Root = null;
            this.MaxNiv = -1;
        }

        public void Insert(int x)
        {
            Node tmp = new Node(x);
            nodes.Add(tmp);
            if (this.Root == null)
            {
                tmp.Niveli = 0;
                this.Root = tmp;
            }
            else InsertNode(tmp);

            if (tmp.Niveli > this.MaxNiv) MaxNiv = tmp.Niveli;

        }
        public void ConnectLeafs()
        {
            //TODO
        }
        public List<Node> ReturnNodesAroundTheTree()
        {
            return nodes.Where(x => IsLeaf(x)).ToList();
        }
    }

推荐阅读