二叉树到双链表在 C#.net 中

本文关键字：net 链表 二叉树 | 更新日期: 2023-09-27 18:35:33

我正在尝试在 C# 中将二叉树转换为双链表。

DLL 中节点的顺序必须是二叉树的顺序遍历。

这是代码：

public void BSTtoDLL(ref Node root,ref Node head,ref Node tail)
        {
            if (root == null) return;
            BSTtoDLL(ref root.left,ref head,ref tail);
            if (tail != null)
            {               
                root.left = tail;
                tail.right = root;
            }
            else
            {
                head = root;
            }
            tail = root;
            BSTtoDLL(ref root.right,ref head, ref tail);
        }

但是我得到堆栈溢出异常？

我错过了什么？

二叉树到双链表在 C#.net 中

虽然无序遍历没问题，但其余代码从根本上是错误的。虽然left和right字段是树结构的本机部分，但您在双链表中滥用了它们。结果是你使树结构无效，显然引入了一个圆圈，然后导致堆栈溢出。

如果您确实需要将这些引用保留在 Node 类本身中，则必须维护两对，如下所示：

  • treeLeft ， treeRight — 用于树数据结构
  • listPrev ， listNext — 用于双链表结构（请注意，将这些引用称为 Ever 和 Next 是一种常见的约定）

另外还有几件事需要考虑：

  • 没有理由传递根节点ref
  • 我建议完全消除ref，而是在DoubleLinkedList类上运行
    • 。
  • 通常，我建议从有用的数据有效载荷中分解数据结构的机制，创建一个TreeNode<T>和ListNode<T>，其中T表示有用的数据有效载荷。
public class TreeNode
{
    public TreeNode Left { get; set; }
    public int Data { get; set; }
    public TreeNode Right { get; set; }
    public TreeNode(int data)
    {
        this.Left = null;
        this.Data = data;
        this.Right = null;
    }
}
public class DLLNode
{
    public DLLNode Prev { get; set; }
    public int Data { get; set; }
    public DLLNode Next { get; set; }
    public DLLNode(int data)
    {
        this.Data = data;
    }
}
public class Tree
{
    public TreeNode Root { get; set; }
    public Tree()
    {
        // Creating a dummy tree;
        Root = new TreeNode(10);
        Root.Left = new TreeNode(12);
        Root.Left.Left = new TreeNode(25);
        Root.Left.Right = new TreeNode(30);
        Root.Right = new TreeNode(15);
        Root.Right.Left = new TreeNode(36);
    }
}
public class DLL
{
    private DLLNode Curr { get; set; }
    public DLLNode Head { get; set; }
    public void FromTree(Tree t)
    {
        ProcessInOrder(t.Root);
    }
    public void Display()
    {
        while(Head != null)
        {
            Console.Write(Head.Data + ", ");
            Head = Head.Next;
        }
    }
    private void ProcessInOrder(TreeNode n)
    {
        if(n != null)
        {
            ProcessInOrder(n.Left);
            CreateDLLNode(n);
            ProcessInOrder(n.Right);
        }        
    }
    private void CreateDLLNode(TreeNode n)
    {
        DLLNode node = new DLLNode(n.Data);
        if(Curr == null)
        {
            Curr = Head = node;
        }
        else
        {
            Curr.Next = node;
            node.Prev = Curr;
            Curr = node;
        }
    }
}
DLL d = new DLL();
d.FromTree(new Tree());
d.Display();
相关文章：