logo标签列表

在C#中实现完全二叉树，而非二叉搜索树

c#algorithmtreebinary-tree
8

我正在尝试在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块中，但我无法找到解决方法。
我尝试在网上寻找解决方案，但大多数地方都是二叉搜索树的实现。我喜欢的一个解决方案在这里，但该解决方案将输入数组作为递归调用的参数传递，我不知道在处理非常大的树时是否高效。还有其他几篇帖子，但没有一个能解决我的问题。
虽然我正在使用C#实现它，但更具体地说，我正在寻找修复AddNode(...)函数的逻辑，所以如果算法不是代码实现，则可以接受。
有什么帮助吗？
1
需要使用节点吗？可以使用数组来完成吗？ - Luiggi Mendoza
你想让树对输入数据进行排序还是只是添加它？ - horotab
9个回答
9

树是一种递归数据结构的定义。

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的节点：
  • 左子节点的索引为2*i + 1
  • 右子节点的索引为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，逐个添加节点的几种方法：

  • 从根节点向下遍历树（绝对）
  • 从先前添加的节点开始遍历（相对）
  • 维护一个无两个子节点的节点有序集合

由于第二种方法需要更长的行程距离（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;
该问题明确地质疑了“将输入数组作为[递归调用中的参数]传递”的效率。 - greybeard
3
你需要逐层填充树。第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)
这可能是有效的，但并不完全符合C#语言的规范。如果你坚持要从左到右填充树，则应该按照最高位到次低位的顺序处理二进制位。 - greybeard
@老程序员 为什么？我看不出有什么区别。没有规定级别的填充顺序。是的，它不是C#，也不是C，也不是Python。这是伪代码。 - user58697
为什么从左到右？问题中的草图看起来是这种类型，而在其他地方我看到过自上而下、从左到右定义的完全二进制——这就引出了在条件句中以相反顺序处理位的建议。 - greybeard
2
这个算法可以以相当简单和高效的方式解决您的问题。
考虑这个节点类：
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;}
}

这个课程将帮助你组织你的家谱。
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方法，因此在实现中我们将使用Queue<T>。
我们将从第一个节点开始，并首先附加其左子节点（然后将其添加到队列中），然后我们将附加其右子节点（并在之后也将其添加到队列中），只有在我们附加了两个子节点之后，我们才会将其从队列中删除，并开始将子节点附加到其左子节点（即队列中的下一个节点）。当我们完成左子节点的操作后，我们将开始将子节点附加到其右子节点（这将是队列中的下一个节点），我们将不断地从上到下，从左到右执行此操作，直到树被组成。
现在，您可以像这样从主方法中使用它：
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
    }
}
2
考虑到2016/10/21已经有两个有效答案，你认为需要注意什么？用户58697的二进制小端方法使用总节点数作为附加信息构建具有最小可能左右子节点数量差异的树，该方法使用一个队列来从左到右填充级别。 "二进制大端"也是从左到右填充的，"队列"可以修改为始终“出队”并“入队”旧节点，除非“满”，在这种情况下，所有后代都会被处理。 - greybeard
1
这是另一种获取答案的方法，无需跟踪左、右和/或父节点。实际上，当您调用tree1.Root时，Node类变得非常简单，Tree类会处理工作...下面我使用构造函数添加了值，但我已经包括了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();
    }

出于娱乐目的，我创建了一个扩展程序，可以将树状结构写入控制台，以帮助可视化树形结构。为了使用此功能，您需要确保Node和Tree类是公共的，并在Tree类中添加一个Values属性。因此，您的Tree类应如下所示：

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

这里是扩展类：

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

And you should see this:

                   10
           __________________
          /                  \
         20                  30
      ________            ________
     /        \          /        \
    40        50        60        70
    __        _
   /  \      /
  80  90   100
0
每个节点都需要知道其父节点，根节点是一个例外，因为它将具有空父节点。然后，每个节点都需要知道它上次传递值的路径。然后，当要求节点添加子节点时，它将按顺序进行：左、右、父亲、左、右、父亲...(根节点是一个例外，它将跳过父节点，并且只交替左、右、左、右...)。
我快速调整了您的代码，使其按照您的意图工作，如果再花点时间，这可能会更清晰简洁。
 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();
    }
  }
每个节点都需要知道它的父节点。这种需求从何而来？你使用的“二叉树”定义是什么？我承认，这个问题意味着该悲惨声明呈现为 Node AddNode(Node node, int data) 的 **public**。 - greybeard
当一个节点被要求添加一个子节点时，它可以将其设置在其左侧或右侧，但一旦这两个插槽都被填满，它必须将其移交给其左侧、右侧或父节点。这使得树可以水平遍历每个级别。否则就需要完全重写树/节点结构。我试图沿用初始帖子的逻辑。我已经找到了一种更好的基于列表生成树的方法。我将把它作为单独的答案发布。 - Larry Dukek
我并没有采用“public Node AddNode（Node node，int data）”这个可以有意义地实现的签名；首先它不是Node的实例方法，其次 我看不出来如何使用Node的已有成员 和 如果新的“Node”没有在node的子树中结束，那么它与“node”的关系到底是什么 ，最后我也看不出来每个节点中是否都具有#children（或等效项） ：请尝试在实例化后立即向您的树添加-1和0，获取其Root.Left，然后通过循环将数据添加到其中。 - greybeard
0

回答您的问题：

传递数组是通过向函数传递数组的引用来完成的。因此，在性能方面，它与传递任何类型的对象完全相同(https://msdn.microsoft.com/en-us/library/bb985948.aspx)。

就个人而言，我不是递归函数的忠实粉丝，这些函数总是传递相同的对象，也不喜欢调用将调用构造函数的递归函数。

没有数组，以下是一种解决方案：

有趣的一点是，在这样的树中，如果您从1开始寻址，则可以使用节点地址查找节点：

                0001
        0010            0011
    0100    0101    0110   0111
1000

如果您在树中跟踪节点计数，那么您知道要添加的下一个项将位于地址1001。

为了正确执行此操作，我们可以找到父节点（即1001向右移动一位：100），然后决定是添加左侧还是右侧（取决于1001模2 = 1：必须添加到右侧）。

因此，这里是可以完成它的代码：

节点类

//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 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);
    }
}
考虑到FindNodeWithAddress()从root开始处理Node<T>，这与user58697的2016年回答有何不同？ - greybeard
@老程序员，首先因为我回答了OP的问题。然后，尽管算法在概念上是相同的，但我用面向对象、递归和C#的方式呈现它。 - Martin Verjans
0
你尝试过使用数组来实现它吗？
你可以使用一个数组和一个整数来保存最后一个使用的位置。对于任何位置pos，左侧的“子节点”将位于位置2*pos，右侧的“子节点”将位于位置2*pos+1，而“父节点”将位于位置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];
    }
}
0
考虑到您真的想要构建分配节点的树，而不是像其他人建议的数组，有一个非常简单的算法：使用位置队列（给定节点的左或右子节点或根）在自上而下的级别中扩展树。在尾部添加新位置并从头部删除以添加每个连续的节点。无递归。
抱歉我暂时没有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
请查看投资者的2016年回答。 - greybeard
-1

二叉树是一种非平衡结构。树的布局取决于插入值的顺序。你可以有两棵完全相同值的树，但插入顺序不同，树看起来完全不同。

对于平衡树，请查看AVL树。这是一种流行的自平衡实现。

然而，对于实际应用，树已经过时了。字典更好，但如果你正在学习树，请查看AVL树：）。

AVL树有可能成为“完全二叉树”，但仅限于不按顺序插入键（非搜索BST的键）的情况下。字典用于查找某些内容，而“非二叉搜索树”（很可能）则不是。 - greybeard
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接