按顺序打印二叉树

本文关键字：二叉树 打印 顺序 | 更新日期: 2023-09-27 17:50:46

我有一个问题，将一个排序数组转换为二叉树。我想我已经做到了。现在我只想打印转换后的所有项目，以便再次检查。

我的问题是，我的打印部分不打印所有项目。'inOrderTraversalHelper'方法有问题。

class Program
{
    // Given an array where elements are sorted in ascending order, 
    // convert it to a height balanced BST
    static int[] arr = new int[8] {1,2,3,4,5,6,7,8};
    static TreeNode node { get; set; }
    static void Main(string[] args)
    {
         node = SortedArrayToBST(arr, 0, arr.Length-1);
         inOrderTraversal();
    }
    static void inOrderTraversal()
    {
        inOrderTraversalHelper(node);
    }
    static void inOrderTraversalHelper(TreeNode r)
    {
        if (r != null)
        {    
          **// UPDATED**
            inOrderTraversalHelper(r.leftNode);
             Console.Write("{0}   ", r.data);
            inOrderTraversalHelper(r.rightNode);
        }
    }
    static TreeNode SortedArrayToBST(int[] a,int start,int end)
    {
        if (start > end) return null;
        int mid = (start + end) / 2;
        TreeNode node = new TreeNode(a[mid]);
        node.leftNode= SortedArrayToBST(a, start, mid-1);
        node.rightNode = SortedArrayToBST(a, mid + 1, end);
        return node;
    }
}
public class TreeNode
{
    public int data;
    public TreeNode leftNode;
    public TreeNode rightNode;
    public TreeNode(int data)
    {
        this.data = data;
    }
}

按顺序打印二叉树

这是因为您将索引mid的值存储在mid的索引处，而不是值:

int mid = (start + end) / 2;
TreeNode node = new TreeNode(mid);

您正在计算mid的值，然后将其作为数据传递。相反，mid应该是你想要的值的index。例如，如果你有一个数据集，其中的数据是有序的，但不是顺序的，你会得到更奇怪的结果:

{-1,22,33,44,55,66,77,100}

所以你的代码应该查找索引mid的值:

var mid = (int)((start + end) / 2.0);
var node = new TreeNode(arr[mid]);

在SortedArrayToBST中，您使用索引mid，而不是元素a[mid], change:

TreeNode node = new TreeNode(mid);

: 

TreeNode node = new TreeNode(a[mid]);

在调用SortedArrayToBST函数时，您需要传递数组大小- 1，因为包含结束条件，更改:

node = SortedArrayToBST(arr, 0, arr.Length);

: 

node = SortedArrayToBST(arr, 0, arr.Length-1);

另外，您的inOrderTraversalHelper函数实际上不是按顺序的，而是后顺序的。

相关文章：