在 C# 中实现一个完整的二叉树，而不是二叉搜索树
Implementing a complete binary tree, not binary search tree in C#
我正在尝试用 C# 实现二叉树，而不是二叉搜索树。我实现了下面的代码，它工作正常但不是我想要的。基本上我正在尝试实现一个完整的二叉树，但是使用下面的代码，我得到了一个不平衡的二叉树。
Input : 10, 20, 30, 40, 50, 60, 70, 80, 90, 100
Desired Output :
10
/ \
20 30
/ \ / \
40 50 60 70
/ \ /
80 90 100
Current Output :
10
/ \
20 30
/ \
40 50
/ \
60 70
/ \
80 90
/
100
这是我的代码：
class Node
{
public int data;
public Node left;
public Node right;
public Node()
{
data = 0;
left = null;
right = null;
}
}
class Tree
{
private Node root;
public Tree()
{
root = null;
}
public void AddNode(int data)
{
root = AddNode(root, data);
}
public Node AddNode(Node node, int data)
{
if (node == null)
{
node = new Node();
node.data = data;
}
else
{
if (node.left == null)
{
node.left = AddNode(node.left, data);
}
else
{
node.right = AddNode(node.right, data);
}
}
return node;
}
}
class Program
{
static void Main(string[] args)
{
int[] nodeData = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
Tree tree1 = new Tree();
foreach (int i in nodeData)
{
tree1.AddNode(i);
}
Console.ReadKey();
}
}
我知道问题出在我的 AddNode(Node node, int data) {...} 函数的 else 块中，但我无法找出解决方案。
我试图在网上寻找解决方案，但大多数地方都是二叉搜索树实现。我喜欢的解决方案之一是 here 但解决方案是将输入数组作为递归调用的参数传递，我不知道在非常大的树的情况下这是否有效。还有其他几篇文章，但其中 none 正在解决我的问题。
虽然我是在 C# 中实现它，但更具体地说，我正在寻找修复我的 AddNode(...) 函数的逻辑，所以即使不是代码实现，我也能接受算法。
有什么帮助吗？
二叉树是一种非平衡结构。树的布局取决于您插入值的顺序。您可以拥有两棵具有完全相同值的树，但以不同的顺序插入，这棵树看起来将完全不同。
对于平衡树，请查看 AVL 树。那是一种流行的自平衡实现。
不过，对于实际使用来说，树木已经过时了。字典更好，但如果你正在学习树，请查看 AVL 树 :)。
该算法可以非常简单有效地解决您的问题。
考虑这个节点 class:
public class Node<T>
{
public Node(T data)
{
Data = data;
}
public T Data { get; }
public Node<T> Left { get; set;}
public Node<T> Right { get; set;}
}
这 class 将帮助您构建您的树：
public class TreeBuilder<T>
{
private readonly Queue<Node<T>> _previousNodes;
public Node<T> Root { get; }
public TreeBuilder(T rootData)
{
Root = new Node<T>(rootData)
_previousNodes = new Queue<Node<T>>();
_previousNodes.Enqueue(Root);
}
public void AddNode(T data)
{
var newNode = new Node<T>(data);
var nodeToAddChildTo = _previousNodes.Peek();
if(nodeToAddChildTo.Left == null)
{
nodeToAddChildTo.Left = node;
}
else
{
nodeToAddChildTo.Right = node;
_previousNodes.Dequeue();
}
_previousNodes.Enqueue(newNode);
}
}
AddNode 方法背后的逻辑基于 FIFO methodology so we will use Queue<T> 的实现。
我们将从第一个节点开始，先附加一个左节点 child（然后将其添加到队列中），然后再附加一个右节点（并将其添加到队列中）之后排队）并且只有在我们附加两者之后，我们才会将其从队列中删除并开始将 children 附加到它的左侧 child （这是队列中的下一个）以及何时完成我们将开始将 children 附加到它的右边 child （这将是队列中的下一个），我们将不断地从左到右从上到下执行此操作，直到树将组成。
现在您可以像这样在主方法中使用它：
public class Program
{
public static void Main(string[] args)
{
int[] values = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
var treeBuilder = new TreeBuilder<int>(values[0]);
foreach (int value in values.Skip(1))
{
treeBuilder.AddNode(value);
}
//here you can use treeBuilder Root property as an entry point to the tree
}
}
您需要逐级填充树。级别 n 有 2^n 个节点，即从根有 2^n 条路径。每条路径都可以编码为 n 位数（0 表示走左分支，1 表示走右分支）。也就是说，要填充第n层，
for path from 0 to 2^n - 1
value = get_next_value()
node = root
for level = 0 to n - 1
if path & 0x1 == 0
node = node->left
else
node = node->right
++level
path >>= 1
if path == 0
node->left = new node(value)
else
node->right = new node(value)
根据定义，树是递归数据结构。
class Node<T>
{
public Node(T data)
{
Data = data;
}
public T Data { get; }
public Node<T> Left { get; set; }
public Node<T> Right { get; set; }
}
因此，使用递归构造它们要直观得多。
Input: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100
Desired output --complete binary tree:
10
/ \
20 30
/ \ / \
40 50 60 70
/ \ /
80 90 100
Matching index of input:
0
/ \
1 2
/ \ / \
3 4 5 6
/ \ /
7 8 9
出现一个模式，对于索引为 i 的节点：
- 左边child有索引2*i + 1
- 右边child有索引2*i + 2
有了递归的基本情况，
i >= input.length
我们需要做的就是在根上调用递归方法。
class TreeBuilder<T>
{
public Node<T> Root { get; }
public TreeBuilder(params T[] data)
{
Root = buildTree(data, 0);
}
private Node<T> buildTree(T[] data, int i)
{
if (i >= data.Length) return null;
Node<T> next = new Node<T>(data[i]);
next.Left = buildTree(data, 2 * i + 1);
next.Right = buildTree(data, 2 * i + 2);
return next;
}
}
用法：
int[] data = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
TreeBuilder<int> builder = new TreeBuilder<int>(data);
Node<int> tree = builder.Root;
切换API，一对一添加节点的方法：
- 从根向下遍历树（绝对）
- 从之前添加的节点（相对）出发
- 维护没有两个 child 节点的有序节点集合
由于第二个涉及到较长的行进距离（2 * 树的高度），第三个已经实现（排队记账），让我们看一下第一个。
这一次，可视化给定位置的节点数：
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /
8 9 10
映射到二进制表示：
1
/ \
10 11
/ \ / \
100 101 110 111
/ \ /
1000 1001 1010
如果我们忽略最左边的位，同样会出现一个模式。我们可以将这些位用作路线图，或者在本例中为节点图。
class TreeBuilder<T>
{
private int level;
private int nodeCount;
public Node<T> Root { get; }
public TreeBuilder(T data)
{
Root = new Node<T>(data);
nodeCount = 1;
level = 0;
}
public void addNode(T data)
{
nodeCount++;
Node<T> current = Root;
if (nodeCount >= Math.Pow(2, level + 1)) level++;
for (int n=level - 1; n>0; n--)
current = checkBit(nodeCount, n) ? current.Left : current.Right;
if (checkBit(nodeCount, 0))
current.Left = new Node<T>(data);
else
current.Right = new Node<T>(data);
}
private bool checkBit(int num, int position)
{
return ((num >> position) & 1) == 0;
}
}
用法：
int[] data = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
TreeBuilder<int> builder = new TreeBuilder<int>(data[0]);
for (int i=1; i<data.Length; i++)
{
builder.addNode(data[i]);
}
Node<int> tree = builder.Root;
每个节点都需要知道它的父节点，根节点是例外，因为它的父节点为空。然后每个节点都需要知道它最后向下传递值的路径。然后，当一个节点被要求添加一个子节点时，它将按照以下顺序进行：左、右、父节点、左节点、右节点、父节点，...（根节点是例外，因为它将跳过父节点，只是交替左、右, 左, 右...)
我快速调整了您的代码，使其按您的预期工作，再花一点时间，这可能会更清晰。
class Node
{
private readonly Node parent;
private Direction lastPath;
public int Data { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
public Node(int data, Node parent = null)
{
Data = data;
this.parent = parent;
}
public Node AddChild(int data)
{
if (Left == null)
{
lastPath = Direction.Left;
Left = new Node(data, this);
return this;
}
if (Right == null)
{
lastPath = Direction.Right;
Right = new Node(data, this);
return parent ?? this;
}
if (lastPath == Direction.Parent || parent==null && lastPath == Direction.Right)
{
lastPath = Direction.Left;
return Left.AddChild(data);
}
if (lastPath == Direction.Left)
{
lastPath = Direction.Right;
return Right.AddChild(data);
}
lastPath = Direction.Parent;
return parent?.AddChild(data);
}
}
enum Direction
{
Left,
Right,
Parent
}
class Tree
{
public Node Root { get; private set; }
private Node current;
public void AddNode(int data)
{
if (current == null)
{
Root = new Node(data);
current = Root;
}
else
{
current = current.AddChild(data);
}
}
}
class Program
{
static void Main(string[] args)
{
var nodeData = new [] { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
var tree1 = new Tree();
foreach (var data in nodeData)
{
tree1.AddNode(data);
}
Console.ReadKey();
}
}
这是另一种无需跟踪左、右跟踪即可获得答案的方法 and/or parent。事实上，节点 class 变得非常简单，当您调用 tree1.Root 时，树 class 会完成工作......下面我使用构造函数添加值，但我已经包含了 AddNodes方法，您可以在其中添加一个新节点，您可以通过一次调用添加任意数量的值。
class Node<T>
{
public T Data { get; set; }
public Node<T> Left { get; set; }
public Node<T> Right { get; set; }
public override string ToString()
{
return Data.ToString();
}
}
class Tree<T>
{
private readonly List<T> list;
private static readonly Func<List<T>, int, Node<T>> LeftFunc = (l, i) =>
{
var lix = Convert.ToInt32(Convert.ToString(i, 2) + "0", 2) - 1;
return l.Count > lix ? new Node<T> {Data = l[lix], Left = LeftFunc(l, lix + 1), Right = RightFunc(l, lix + 1) } : null;
};
private static readonly Func<List<T>, int, Node<T>> RightFunc = (l, i) =>
{
var rix = Convert.ToInt32(Convert.ToString(i, 2) + "1", 2) - 1;
return l.Count > rix ? new Node<T> { Data = l[rix], Left = LeftFunc(l, rix + 1), Right = RightFunc(l, rix + 1) } : null;
};
public Node<T> Root => list.Any() ? new Node<T>{Data=list.First(), Left = LeftFunc(list,1), Right= RightFunc(list,1)} : null;
public Tree(params T[] data)
{
list = new List<T>(data);
}
public int Count => list.Count;
public void AddNodes(params T[] data)
{
list.AddRange(data);
}
public double Levels => Math.Floor(Math.Log(list.Count,2))+1;
public override string ToString()
{
return (list?.Count ?? 0).ToString();
}
}
class Program
{
static void Main(string[] args)
{
var nodeData = new [] { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
var tree1 = new Tree<int>(nodeData);
Console.ReadKey();
}
为了好玩，我创建了一个扩展，可以将树写入控制台，以帮助可视化树。为了使用它，您需要确保节点和树 classes 是 public 并添加一个 Values 属性 到树 class 还有。所以你的树 class 看起来像这样：
public class Tree<T>
{
private readonly List<T> list;
private static readonly Func<List<T>, int, Node<T>> LeftFunc = (l, i) =>
{
var lix = Convert.ToInt32(Convert.ToString(i, 2) + "0", 2) - 1;
return l.Count > lix ? new Node<T> {Data = l[lix], Left = LeftFunc(l, lix + 1), Right = RightFunc(l, lix + 1) } : null;
};
private static readonly Func<List<T>, int, Node<T>> RightFunc = (l, i) =>
{
var rix = Convert.ToInt32(Convert.ToString(i, 2) + "1", 2) - 1;
return l.Count > rix ? new Node<T> { Data = l[rix], Left = LeftFunc(l, rix + 1), Right = RightFunc(l, rix + 1) } : null;
};
public Node<T> Root => list.Any() ? new Node<T>{Data=list.First(), Left = LeftFunc(list,1), Right= RightFunc(list,1)} : null;
public Tree(params T[] data)
{
list = new List<T>(data);
}
public int Count => list.Count;
public void AddNodes(params T[] data)
{
list.AddRange(data);
}
public IEnumerable<T> Values => list.ToArray();
public double Levels => Math.Floor(Math.Log(list.Count,2))+1;
public override string ToString()
{
return (list?.Count ?? 0).ToString();
}
}
这里是扩展 class:
public static class TreeAndNodeExtensions
{
public static void Write<T>(this Tree<T> tree)
{
var baseMaxNodes = Convert.ToInt32(Math.Pow(2, tree.Levels - 1));
// determine the required node width based on the the last two levels and their value lengths...
var nodeWidth = Math.Max(tree.Values.Skip(Convert.ToInt32(Math.Pow(2, tree.Levels - 2) - 1)).Max(n => n.ToString().Length), tree.Values.Skip(Convert.ToInt32(Math.Pow(2, tree.Levels - 1) - 1)).Max(n => n.ToString().Length) + 1) + 1;
var baseWidth = baseMaxNodes * nodeWidth;
Console.CursorLeft = baseWidth/2;
tree.Root.Write(baseWidth);
}
private static void Write<T>(this Node<T> node, int nodeWidth, int level=0)
{
var cl = Console.CursorLeft;
var ct = Console.CursorTop;
if (Console.CursorLeft >= Convert.ToInt32(Math.Ceiling(node.Data.ToString().Length / 2.0)))
{
Console.CursorLeft -= Convert.ToInt32(Math.Ceiling(node.Data.ToString().Length / 2.0));
}
Console.Write(node.Data);
if (node.Left != null)
{
var numCenter = cl - nodeWidth/4;
Console.CursorLeft = numCenter;
Console.CursorTop = ct + 2;
Console.Write('/');
Console.CursorTop = ct + 1;
Console.Write(new string('_',cl-Console.CursorLeft));
Console.CursorLeft = numCenter;
Console.CursorTop = ct+3;
node.Left.Write(nodeWidth/2, level+1);
}
if (node.Right != null)
{
var numCenter = cl + nodeWidth/4;
Console.CursorLeft = cl;
Console.CursorTop = ct + 1;
Console.Write(new string('_', numCenter-cl-1));
Console.CursorTop = ct + 2;
Console.Write('\');
Console.CursorLeft = numCenter;
Console.CursorTop = ct+3;
node.Right.Write(nodeWidth/2,level + 1);
}
Console.SetCursorPosition(cl,ct);
}
}
然后您可以更新您的程序以使用此扩展程序：
class Program
{
static void Main(string[] args)
{
var nodeData = new [] { 10, 20, 30, 40, 50, 60, 70, 80,90,100 };
var tree1 = new Tree<int>(nodeData);
tree1.Write();
Console.ReadKey();
}
}
你应该看到这个：
10
__________________
/ \
20 30
________ ________
/ \ / \
40 50 60 70
__ _
/ \ /
80 90 100
回答你的问题：
传递数组是通过向函数传递对数组的引用来完成的。所以就性能而言，它与传递任何类型的对象完全相同(https://msdn.microsoft.com/en-us/library/bb985948.aspx)。
就个人而言，我不太喜欢总是传递相同对象的递归函数，构造函数调用递归函数也不会调用构造函数。
没有数组，这里有一个解决方案：
需要注意的一个有趣的事情是，在这样的树中，如果从 1:
开始寻址，节点地址可用于查找节点
0001
0010 0011
0100 0101 0110 0111
1000
因此，如果您跟踪树中的节点数，就会知道要添加的下一个项目将位于地址 1001。
为了正确地做到这一点，我们可以找到父节点（1001 右移一次：100）然后决定我们是向左添加还是向右添加（取决于 1001 模 2 = 1：必须向右添加）。
所以这里是可以做到这一点的代码：
节点class
//Having a generic here allows you to create a tree of any data type
class Node<T>
{
public T Data { get; set; }
public Node<T> Left { get; set; }
public Node<T> Right { get; set; }
public Node(T Data)
{
this.Data = Data;
}
}
树class
class Tree<T>
{
Node<T> root = null;
int nodeCount = 0;
public void AddNode(T Data)
{
AddNode(new Node<T>(Data));
}
public void AddNode(Node<T> Node)
{
nodeCount++;
if (root == null)
root = Node;
else
{
//First we find the parent node
Node<T> parent = FindNodeWithAddress(nodeCount >> 1);
//Then we add left or right
if (nodeCount % 2 == 0)
parent.Left = Node;
else
parent.Right = Node;
}
}
private Node<T> FindNodeWithAddress(int address)
{
if (address == 1)
return root;
//To find the proper address we use the same trick
//We first find our parent's address
Node<T> parent = FindNodeWithAddress(address >> 1);
//Then we go left or right
return (address % 2 == 0 ? parent.Left : parent.Right);
}
}
您是否尝试过使用数组实现它？
您将使用一个数组和一个 int 来保存最后使用的位置
对于任何位置 pos，左侧 "child node" 将位于位置 2*pos
右边的 "child node" 会在位置 2*pos+1
"father node" 将位于 pos/2
位置
（不要认为这段代码在语法上是正确的，这只是一个例子）
template<class T>
class CompleteBinTree<T>{
private int[] arr;
private int arrSize;
private int pos;
public CompleteBinTree(){
arrSize = 100;
arr = new int[arrSize]//you can always change this number
int pos = 1; //you can use 0 instead of 1, but this way it's easier to understand
}
public AddNode(T t){
if(pos + 1 == arrSize){
int[] aux = int[arrSize];
for(int i = 0; i < arrSize; i++)
aux[i] = arr[i];
arr = aux[i];
arrSize = arrSize * 2;
}
arr[pos] = t;
pos++;
}
public IndexOfLeftSon(int x){
return 2*x;
}
public IndexOfRightSon(int x){
return 2*x + 1;
}
public DeleteNode(int x){
for(int i = x; i < pos; i++)
arr[i] = arr[i+1];
}
}
鉴于您真的想构建一棵已分配节点的树，而不是其他人建议的数组，有一个非常简单的算法：使用位置队列（给定节点的左或右子节点或根节点) 以自上而下的级别展开树。在尾部添加新位置并从头部移除以添加每个后续节点。没有递归。
抱歉，我目前无法访问 C# 环境，所以我会在 Java 中展示它。翻译应该很简单。
import java.util.ArrayDeque;
import java.util.Deque;
public class CompleteBinaryTree {
final Deque<Location> queue = new ArrayDeque<>();
/** Build a tree top-down in levels left-to-right with given node values. */
Node build(int [] vals) {
Node root = null;
queue.clear();
queue.add(new Location(root, Location.Kind.ROOT));
for (int val : vals) {
Location next = queue.pollFirst();
switch (next.kind) {
case ROOT: root = addNode(val); break;
case LEFT: next.node.left = addNode(val); break;
case RIGHT: next.node.right = addNode(val); break;
}
}
return root;
}
/** Create a new node and queue up locations for its future children. */
Node addNode(int val) {
Node node = new Node(val);
queue.addLast(new Location(node, Location.Kind.LEFT));
queue.addLast(new Location(node, Location.Kind.RIGHT));
return node;
}
static class Node {
final int val;
Node left, right;
Node(int val) {
this.val = val;
}
void print(int level) {
System.out.format("%" + level + "s%d\n", "", val);
if (left != null) left.print(level + 1);
if (right != null) right.print(level + 1);
}
}
static class Location {
enum Kind { ROOT, LEFT, RIGHT }
final Node node;
final Kind kind;
Location(Node node, Kind kind) {
this.node = node;
this.kind = kind;
}
}
public static void main(String [] args) {
int [] vals = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
new CompleteBinaryTree().build(vals).print(1);
}
}
当 运行 时，如您所愿，这会产生
10
20
40
80
90
50
100
30
60
70
我正在尝试用 C# 实现二叉树，而不是二叉搜索树。我实现了下面的代码，它工作正常但不是我想要的。基本上我正在尝试实现一个完整的二叉树，但是使用下面的代码，我得到了一个不平衡的二叉树。
Input : 10, 20, 30, 40, 50, 60, 70, 80, 90, 100
Desired Output :
10
/ \
20 30
/ \ / \
40 50 60 70
/ \ /
80 90 100
Current Output :
10
/ \
20 30
/ \
40 50
/ \
60 70
/ \
80 90
/
100
这是我的代码：
class Node
{
public int data;
public Node left;
public Node right;
public Node()
{
data = 0;
left = null;
right = null;
}
}
class Tree
{
private Node root;
public Tree()
{
root = null;
}
public void AddNode(int data)
{
root = AddNode(root, data);
}
public Node AddNode(Node node, int data)
{
if (node == null)
{
node = new Node();
node.data = data;
}
else
{
if (node.left == null)
{
node.left = AddNode(node.left, data);
}
else
{
node.right = AddNode(node.right, data);
}
}
return node;
}
}
class Program
{
static void Main(string[] args)
{
int[] nodeData = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
Tree tree1 = new Tree();
foreach (int i in nodeData)
{
tree1.AddNode(i);
}
Console.ReadKey();
}
}
我知道问题出在我的 AddNode(Node node, int data) {...} 函数的 else 块中，但我无法找出解决方案。
我试图在网上寻找解决方案，但大多数地方都是二叉搜索树实现。我喜欢的解决方案之一是 here 但解决方案是将输入数组作为递归调用的参数传递，我不知道在非常大的树的情况下这是否有效。还有其他几篇文章，但其中 none 正在解决我的问题。
虽然我是在 C# 中实现它，但更具体地说，我正在寻找修复我的 AddNode(...) 函数的逻辑，所以即使不是代码实现，我也能接受算法。
有什么帮助吗？
二叉树是一种非平衡结构。树的布局取决于您插入值的顺序。您可以拥有两棵具有完全相同值的树，但以不同的顺序插入，这棵树看起来将完全不同。
对于平衡树，请查看 AVL 树。那是一种流行的自平衡实现。
不过，对于实际使用来说，树木已经过时了。字典更好，但如果你正在学习树，请查看 AVL 树 :)。
该算法可以非常简单有效地解决您的问题。
考虑这个节点 class:
public class Node<T>
{
public Node(T data)
{
Data = data;
}
public T Data { get; }
public Node<T> Left { get; set;}
public Node<T> Right { get; set;}
}
这 class 将帮助您构建您的树：
public class TreeBuilder<T>
{
private readonly Queue<Node<T>> _previousNodes;
public Node<T> Root { get; }
public TreeBuilder(T rootData)
{
Root = new Node<T>(rootData)
_previousNodes = new Queue<Node<T>>();
_previousNodes.Enqueue(Root);
}
public void AddNode(T data)
{
var newNode = new Node<T>(data);
var nodeToAddChildTo = _previousNodes.Peek();
if(nodeToAddChildTo.Left == null)
{
nodeToAddChildTo.Left = node;
}
else
{
nodeToAddChildTo.Right = node;
_previousNodes.Dequeue();
}
_previousNodes.Enqueue(newNode);
}
}
AddNode 方法背后的逻辑基于 FIFO methodology so we will use Queue<T> 的实现。
我们将从第一个节点开始，先附加一个左节点 child（然后将其添加到队列中），然后再附加一个右节点（并将其添加到队列中）之后排队）并且只有在我们附加两者之后，我们才会将其从队列中删除并开始将 children 附加到它的左侧 child （这是队列中的下一个）以及何时完成我们将开始将 children 附加到它的右边 child （这将是队列中的下一个），我们将不断地从左到右从上到下执行此操作，直到树将组成。
现在您可以像这样在主方法中使用它：
public class Program
{
public static void Main(string[] args)
{
int[] values = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
var treeBuilder = new TreeBuilder<int>(values[0]);
foreach (int value in values.Skip(1))
{
treeBuilder.AddNode(value);
}
//here you can use treeBuilder Root property as an entry point to the tree
}
}
您需要逐级填充树。级别 n 有 2^n 个节点，即从根有 2^n 条路径。每条路径都可以编码为 n 位数（0 表示走左分支，1 表示走右分支）。也就是说，要填充第n层，
for path from 0 to 2^n - 1
value = get_next_value()
node = root
for level = 0 to n - 1
if path & 0x1 == 0
node = node->left
else
node = node->right
++level
path >>= 1
if path == 0
node->left = new node(value)
else
node->right = new node(value)
根据定义，树是递归数据结构。
class Node<T>
{
public Node(T data)
{
Data = data;
}
public T Data { get; }
public Node<T> Left { get; set; }
public Node<T> Right { get; set; }
}
因此，使用递归构造它们要直观得多。
Input: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100
Desired output --complete binary tree:
10
/ \
20 30
/ \ / \
40 50 60 70
/ \ /
80 90 100
Matching index of input:
0
/ \
1 2
/ \ / \
3 4 5 6
/ \ /
7 8 9
出现一个模式，对于索引为 i 的节点：
- 左边child有索引2*i + 1
- 右边child有索引2*i + 2
有了递归的基本情况，
i >= input.length
我们需要做的就是在根上调用递归方法。
class TreeBuilder<T>
{
public Node<T> Root { get; }
public TreeBuilder(params T[] data)
{
Root = buildTree(data, 0);
}
private Node<T> buildTree(T[] data, int i)
{
if (i >= data.Length) return null;
Node<T> next = new Node<T>(data[i]);
next.Left = buildTree(data, 2 * i + 1);
next.Right = buildTree(data, 2 * i + 2);
return next;
}
}
用法：
int[] data = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
TreeBuilder<int> builder = new TreeBuilder<int>(data);
Node<int> tree = builder.Root;
切换API，一对一添加节点的方法：
- 从根向下遍历树（绝对）
- 从之前添加的节点（相对）出发
- 维护没有两个 child 节点的有序节点集合
由于第二个涉及到较长的行进距离（2 * 树的高度），第三个已经实现（排队记账），让我们看一下第一个。
这一次，可视化给定位置的节点数：
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /
8 9 10
映射到二进制表示：
1
/ \
10 11
/ \ / \
100 101 110 111
/ \ /
1000 1001 1010
如果我们忽略最左边的位，同样会出现一个模式。我们可以将这些位用作路线图，或者在本例中为节点图。
class TreeBuilder<T>
{
private int level;
private int nodeCount;
public Node<T> Root { get; }
public TreeBuilder(T data)
{
Root = new Node<T>(data);
nodeCount = 1;
level = 0;
}
public void addNode(T data)
{
nodeCount++;
Node<T> current = Root;
if (nodeCount >= Math.Pow(2, level + 1)) level++;
for (int n=level - 1; n>0; n--)
current = checkBit(nodeCount, n) ? current.Left : current.Right;
if (checkBit(nodeCount, 0))
current.Left = new Node<T>(data);
else
current.Right = new Node<T>(data);
}
private bool checkBit(int num, int position)
{
return ((num >> position) & 1) == 0;
}
}
用法：
int[] data = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
TreeBuilder<int> builder = new TreeBuilder<int>(data[0]);
for (int i=1; i<data.Length; i++)
{
builder.addNode(data[i]);
}
Node<int> tree = builder.Root;
每个节点都需要知道它的父节点，根节点是例外，因为它的父节点为空。然后每个节点都需要知道它最后向下传递值的路径。然后，当一个节点被要求添加一个子节点时，它将按照以下顺序进行：左、右、父节点、左节点、右节点、父节点，...（根节点是例外，因为它将跳过父节点，只是交替左、右, 左, 右...)
我快速调整了您的代码，使其按您的预期工作，再花一点时间，这可能会更清晰。
class Node
{
private readonly Node parent;
private Direction lastPath;
public int Data { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
public Node(int data, Node parent = null)
{
Data = data;
this.parent = parent;
}
public Node AddChild(int data)
{
if (Left == null)
{
lastPath = Direction.Left;
Left = new Node(data, this);
return this;
}
if (Right == null)
{
lastPath = Direction.Right;
Right = new Node(data, this);
return parent ?? this;
}
if (lastPath == Direction.Parent || parent==null && lastPath == Direction.Right)
{
lastPath = Direction.Left;
return Left.AddChild(data);
}
if (lastPath == Direction.Left)
{
lastPath = Direction.Right;
return Right.AddChild(data);
}
lastPath = Direction.Parent;
return parent?.AddChild(data);
}
}
enum Direction
{
Left,
Right,
Parent
}
class Tree
{
public Node Root { get; private set; }
private Node current;
public void AddNode(int data)
{
if (current == null)
{
Root = new Node(data);
current = Root;
}
else
{
current = current.AddChild(data);
}
}
}
class Program
{
static void Main(string[] args)
{
var nodeData = new [] { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
var tree1 = new Tree();
foreach (var data in nodeData)
{
tree1.AddNode(data);
}
Console.ReadKey();
}
}
这是另一种无需跟踪左、右跟踪即可获得答案的方法 and/or parent。事实上，节点 class 变得非常简单，当您调用 tree1.Root 时，树 class 会完成工作......下面我使用构造函数添加值，但我已经包含了 AddNodes方法，您可以在其中添加一个新节点，您可以通过一次调用添加任意数量的值。
class Node<T>
{
public T Data { get; set; }
public Node<T> Left { get; set; }
public Node<T> Right { get; set; }
public override string ToString()
{
return Data.ToString();
}
}
class Tree<T>
{
private readonly List<T> list;
private static readonly Func<List<T>, int, Node<T>> LeftFunc = (l, i) =>
{
var lix = Convert.ToInt32(Convert.ToString(i, 2) + "0", 2) - 1;
return l.Count > lix ? new Node<T> {Data = l[lix], Left = LeftFunc(l, lix + 1), Right = RightFunc(l, lix + 1) } : null;
};
private static readonly Func<List<T>, int, Node<T>> RightFunc = (l, i) =>
{
var rix = Convert.ToInt32(Convert.ToString(i, 2) + "1", 2) - 1;
return l.Count > rix ? new Node<T> { Data = l[rix], Left = LeftFunc(l, rix + 1), Right = RightFunc(l, rix + 1) } : null;
};
public Node<T> Root => list.Any() ? new Node<T>{Data=list.First(), Left = LeftFunc(list,1), Right= RightFunc(list,1)} : null;
public Tree(params T[] data)
{
list = new List<T>(data);
}
public int Count => list.Count;
public void AddNodes(params T[] data)
{
list.AddRange(data);
}
public double Levels => Math.Floor(Math.Log(list.Count,2))+1;
public override string ToString()
{
return (list?.Count ?? 0).ToString();
}
}
class Program
{
static void Main(string[] args)
{
var nodeData = new [] { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
var tree1 = new Tree<int>(nodeData);
Console.ReadKey();
}
为了好玩，我创建了一个扩展，可以将树写入控制台，以帮助可视化树。为了使用它，您需要确保节点和树 classes 是 public 并添加一个 Values 属性 到树 class 还有。所以你的树 class 看起来像这样：
public class Tree<T>
{
private readonly List<T> list;
private static readonly Func<List<T>, int, Node<T>> LeftFunc = (l, i) =>
{
var lix = Convert.ToInt32(Convert.ToString(i, 2) + "0", 2) - 1;
return l.Count > lix ? new Node<T> {Data = l[lix], Left = LeftFunc(l, lix + 1), Right = RightFunc(l, lix + 1) } : null;
};
private static readonly Func<List<T>, int, Node<T>> RightFunc = (l, i) =>
{
var rix = Convert.ToInt32(Convert.ToString(i, 2) + "1", 2) - 1;
return l.Count > rix ? new Node<T> { Data = l[rix], Left = LeftFunc(l, rix + 1), Right = RightFunc(l, rix + 1) } : null;
};
public Node<T> Root => list.Any() ? new Node<T>{Data=list.First(), Left = LeftFunc(list,1), Right= RightFunc(list,1)} : null;
public Tree(params T[] data)
{
list = new List<T>(data);
}
public int Count => list.Count;
public void AddNodes(params T[] data)
{
list.AddRange(data);
}
public IEnumerable<T> Values => list.ToArray();
public double Levels => Math.Floor(Math.Log(list.Count,2))+1;
public override string ToString()
{
return (list?.Count ?? 0).ToString();
}
}
这里是扩展 class:
public static class TreeAndNodeExtensions
{
public static void Write<T>(this Tree<T> tree)
{
var baseMaxNodes = Convert.ToInt32(Math.Pow(2, tree.Levels - 1));
// determine the required node width based on the the last two levels and their value lengths...
var nodeWidth = Math.Max(tree.Values.Skip(Convert.ToInt32(Math.Pow(2, tree.Levels - 2) - 1)).Max(n => n.ToString().Length), tree.Values.Skip(Convert.ToInt32(Math.Pow(2, tree.Levels - 1) - 1)).Max(n => n.ToString().Length) + 1) + 1;
var baseWidth = baseMaxNodes * nodeWidth;
Console.CursorLeft = baseWidth/2;
tree.Root.Write(baseWidth);
}
private static void Write<T>(this Node<T> node, int nodeWidth, int level=0)
{
var cl = Console.CursorLeft;
var ct = Console.CursorTop;
if (Console.CursorLeft >= Convert.ToInt32(Math.Ceiling(node.Data.ToString().Length / 2.0)))
{
Console.CursorLeft -= Convert.ToInt32(Math.Ceiling(node.Data.ToString().Length / 2.0));
}
Console.Write(node.Data);
if (node.Left != null)
{
var numCenter = cl - nodeWidth/4;
Console.CursorLeft = numCenter;
Console.CursorTop = ct + 2;
Console.Write('/');
Console.CursorTop = ct + 1;
Console.Write(new string('_',cl-Console.CursorLeft));
Console.CursorLeft = numCenter;
Console.CursorTop = ct+3;
node.Left.Write(nodeWidth/2, level+1);
}
if (node.Right != null)
{
var numCenter = cl + nodeWidth/4;
Console.CursorLeft = cl;
Console.CursorTop = ct + 1;
Console.Write(new string('_', numCenter-cl-1));
Console.CursorTop = ct + 2;
Console.Write('\');
Console.CursorLeft = numCenter;
Console.CursorTop = ct+3;
node.Right.Write(nodeWidth/2,level + 1);
}
Console.SetCursorPosition(cl,ct);
}
}
然后您可以更新您的程序以使用此扩展程序：
class Program
{
static void Main(string[] args)
{
var nodeData = new [] { 10, 20, 30, 40, 50, 60, 70, 80,90,100 };
var tree1 = new Tree<int>(nodeData);
tree1.Write();
Console.ReadKey();
}
}
你应该看到这个：
10
__________________
/ \
20 30
________ ________
/ \ / \
40 50 60 70
__ _
/ \ /
80 90 100
回答你的问题：
传递数组是通过向函数传递对数组的引用来完成的。所以就性能而言，它与传递任何类型的对象完全相同(https://msdn.microsoft.com/en-us/library/bb985948.aspx)。
就个人而言，我不太喜欢总是传递相同对象的递归函数，构造函数调用递归函数也不会调用构造函数。
没有数组，这里有一个解决方案：
需要注意的一个有趣的事情是，在这样的树中，如果从 1:
开始寻址，节点地址可用于查找节点 0001
0010 0011
0100 0101 0110 0111
1000
因此，如果您跟踪树中的节点数，就会知道要添加的下一个项目将位于地址 1001。
为了正确地做到这一点，我们可以找到父节点（1001 右移一次：100）然后决定我们是向左添加还是向右添加（取决于 1001 模 2 = 1：必须向右添加）。
所以这里是可以做到这一点的代码：
节点class
//Having a generic here allows you to create a tree of any data type
class Node<T>
{
public T Data { get; set; }
public Node<T> Left { get; set; }
public Node<T> Right { get; set; }
public Node(T Data)
{
this.Data = Data;
}
}
树class
class Tree<T>
{
Node<T> root = null;
int nodeCount = 0;
public void AddNode(T Data)
{
AddNode(new Node<T>(Data));
}
public void AddNode(Node<T> Node)
{
nodeCount++;
if (root == null)
root = Node;
else
{
//First we find the parent node
Node<T> parent = FindNodeWithAddress(nodeCount >> 1);
//Then we add left or right
if (nodeCount % 2 == 0)
parent.Left = Node;
else
parent.Right = Node;
}
}
private Node<T> FindNodeWithAddress(int address)
{
if (address == 1)
return root;
//To find the proper address we use the same trick
//We first find our parent's address
Node<T> parent = FindNodeWithAddress(address >> 1);
//Then we go left or right
return (address % 2 == 0 ? parent.Left : parent.Right);
}
}
您是否尝试过使用数组实现它？
您将使用一个数组和一个 int 来保存最后使用的位置
对于任何位置 pos，左侧 "child node" 将位于位置 2*pos
右边的 "child node" 会在位置 2*pos+1
"father node" 将位于 pos/2
（不要认为这段代码在语法上是正确的，这只是一个例子）
template<class T>
class CompleteBinTree<T>{
private int[] arr;
private int arrSize;
private int pos;
public CompleteBinTree(){
arrSize = 100;
arr = new int[arrSize]//you can always change this number
int pos = 1; //you can use 0 instead of 1, but this way it's easier to understand
}
public AddNode(T t){
if(pos + 1 == arrSize){
int[] aux = int[arrSize];
for(int i = 0; i < arrSize; i++)
aux[i] = arr[i];
arr = aux[i];
arrSize = arrSize * 2;
}
arr[pos] = t;
pos++;
}
public IndexOfLeftSon(int x){
return 2*x;
}
public IndexOfRightSon(int x){
return 2*x + 1;
}
public DeleteNode(int x){
for(int i = x; i < pos; i++)
arr[i] = arr[i+1];
}
}
鉴于您真的想构建一棵已分配节点的树，而不是其他人建议的数组，有一个非常简单的算法：使用位置队列（给定节点的左或右子节点或根节点) 以自上而下的级别展开树。在尾部添加新位置并从头部移除以添加每个后续节点。没有递归。
抱歉，我目前无法访问 C# 环境，所以我会在 Java 中展示它。翻译应该很简单。
import java.util.ArrayDeque;
import java.util.Deque;
public class CompleteBinaryTree {
final Deque<Location> queue = new ArrayDeque<>();
/** Build a tree top-down in levels left-to-right with given node values. */
Node build(int [] vals) {
Node root = null;
queue.clear();
queue.add(new Location(root, Location.Kind.ROOT));
for (int val : vals) {
Location next = queue.pollFirst();
switch (next.kind) {
case ROOT: root = addNode(val); break;
case LEFT: next.node.left = addNode(val); break;
case RIGHT: next.node.right = addNode(val); break;
}
}
return root;
}
/** Create a new node and queue up locations for its future children. */
Node addNode(int val) {
Node node = new Node(val);
queue.addLast(new Location(node, Location.Kind.LEFT));
queue.addLast(new Location(node, Location.Kind.RIGHT));
return node;
}
static class Node {
final int val;
Node left, right;
Node(int val) {
this.val = val;
}
void print(int level) {
System.out.format("%" + level + "s%d\n", "", val);
if (left != null) left.print(level + 1);
if (right != null) right.print(level + 1);
}
}
static class Location {
enum Kind { ROOT, LEFT, RIGHT }
final Node node;
final Kind kind;
Location(Node node, Kind kind) {
this.node = node;
this.kind = kind;
}
}
public static void main(String [] args) {
int [] vals = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
new CompleteBinaryTree().build(vals).print(1);
}
}
当 运行 时，如您所愿，这会产生
10
20
40
80
90
50
100
30
60
70