c#二叉樹如何轉(zhuǎn)換為雙向鏈表

c#
小樊
84
2024-07-26 02:43:14

要將二叉樹轉(zhuǎn)換為雙向鏈表，可以使用中序遍歷來(lái)實(shí)現(xiàn)。具體步驟如下：

  1. 創(chuàng)建一個(gè)類來(lái)表示雙向鏈表的節(jié)點(diǎn)，包括指向前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)的指針。
public class Node
{
    public int val;
    public Node prev;
    public Node next;

    public Node(int val)
    {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}
  1. 創(chuàng)建一個(gè)類來(lái)表示二叉樹的節(jié)點(diǎn)，包括左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。
public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val)
    {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}
  1. 編寫一個(gè)遞歸函數(shù)來(lái)實(shí)現(xiàn)中序遍歷，并在遍歷過(guò)程中將二叉樹轉(zhuǎn)換為雙向鏈表。
public class Solution
{
    private Node prev;

    public Node Convert(TreeNode root)
    {
        if (root == null)
            return null;

        Node dummy = new Node(-1);
        prev = dummy;

        InOrder(root);

        Node head = dummy.next;
        head.prev = null;

        return head;
    }

    private void InOrder(TreeNode node)
    {
        if (node == null)
            return;

        InOrder(node.left);

        Node current = new Node(node.val);
        prev.next = current;
        current.prev = prev;
        prev = current;

        InOrder(node.right);
    }
}
  1. 在主函數(shù)中調(diào)用Convert方法，將二叉樹轉(zhuǎn)換為雙向鏈表。
class Program
{
    static void Main(string[] args)
    {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);

        Solution solution = new Solution();
        Node head = solution.Convert(root);

        // 遍歷雙向鏈表
        Node currentNode = head;
        while (currentNode != null)
        {
            Console.Write(currentNode.val + " ");
            currentNode = currentNode.next;
        }
    }
}

運(yùn)行上面的代碼，即可將二叉樹轉(zhuǎn)換為雙向鏈表，并輸出雙向鏈表的值。

0 踩