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

Question

这是我为BST(二进制搜索树(实现的。有人能帮我创建两个方法吗，一个是连接叶子，另一个是返回树周围的节点列表，例如：连接叶子示例在这张图中，它显示了叶子应该如何连接，应该存储在List中的节点以及存储在List的节点需要以这种方式存储，其中根是第一个元素，并向左传递到从右返回根的叶。在我的示例中，它应该是8(根(、3、1、4、7、13、14、10、8(根(root((。非常感谢。

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

Answer 1

这里有一个简单的方法。我创建了一个所有节点的列表。创建新节点时，将节点添加到列表中。参见下方的代码

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();
}
}