C#代码 二叉搜索树 根据后序遍历输出中序遍历
时间: 2023-06-23 13:50:48 浏览: 54
好的,下面是 C# 代码实现:
```csharp
using System;
using System.Collections.Generic;
namespace BinaryTree
{
class Node
{
public int value;
public Node left;
public Node right;
public Node(int value)
{
this.value = value;
left = null;
right = null;
}
}
class BinaryTree
{
public Node root;
public BinaryTree(int[] postorder)
{
root = BuildTree(postorder, 0, postorder.Length - 1);
}
private Node BuildTree(int[] postorder, int start, int end)
{
if (start > end)
{
return null;
}
Node node = new Node(postorder[end]);
int i;
for (i = end - 1; i >= start; i--)
{
if (postorder[i] < node.value)
{
break;
}
}
node.right = BuildTree(postorder, i + 1, end - 1);
node.left = BuildTree(postorder, start, i);
return node;
}
public void InorderTraversal()
{
List<int> result = new List<int>();
Stack<Node> stack = new Stack<Node>();
Node current = root;
while (current != null || stack.Count > 0)
{
while (current != null)
{
stack.Push(current);
current = current.left;
}
current = stack.Pop();
result.Add(current.value);
current = current.right;
}
Console.WriteLine(string.Join(" ", result));
}
}
class Program
{
static void Main(string[] args)
{
int[] postorder = { 2, 4, 3, 6, 5, 1 };
BinaryTree tree = new BinaryTree(postorder);
tree.InorderTraversal();
}
}
}
```
这里使用了后序遍历构建二叉搜索树,然后进行中序遍历输出。如果你对代码中的某些地方有疑问,可以随时问我~