.NET 数据结构：二叉树的概念与基本操作

class TreeNode<T>(T value)
{
	public T Value { get; set; } = value;  // 节点的值

	public TreeNode<T> LeftChild { get; set; }  // 左子节点
	
	public TreeNode<T> RightChild { get; set; }  // 右子节点
}

var root = new TreeNode<int>(1);
var leftChild = new TreeNode<int>(2);
var rightChild = new TreeNode<int>(3);
root.LeftChild = leftChild;  // 1 -> 2
root.RightChild = rightChild;  // 1 -> 3

var newNode = new TreeNode<int>(4);
root.LeftChild = newNode;  // 将父节点的左子节点指向新节点
newNode.LeftChild = leftChild;  // 将新节点的左子节点指向曾经的左子节点

root.LeftChild = leftChild;  // 将父节点的左子节点指向原来的左子节点，被删除的节点将不被引用

var root = new TreeNode<int>(1);
root.LeftChild = new TreeNode<int>(2);
root.RightChild = new TreeNode<int>(3);
root.LeftChild.LeftChild = new TreeNode<int>(4);
root.LeftChild.RightChild = new TreeNode<int>(5);
root.RightChild.LeftChild = new TreeNode<int>(6);
root.RightChild.RightChild = new TreeNode<int>(7);

IEnumerable<T> LevelOrder<T>(TreeNode<T> root)
{
	var queue = new Queue<TreeNode<T>>();  // 初始化队列
	queue.Enqueue(root);  // 根节点入队
	while (queue.Count != 0)
	{
		TreeNode<T> node = queue.Dequeue();
		yield return node.Value;  // 迭代地返回节点值
		if (node.LeftChild != null)
			queue.Enqueue(node.LeftChild);    // 左子节点入队
		if (node.RightChild != null)
			queue.Enqueue(node.RightChild);   // 右子节点入队
	}
}

/* 根节点 -> 左子树 -> 右子树 */
void PreOrder<T>(TreeNode<T> root)
{
	if (root == null) return;
	Console.WriteLine(root.Value);  // 1 2 4 5 3 6 7
	PreOrder(root.LeftChild);
	PreOrder(root.RightChild);
}

/* 左子树 -> 根节点 -> 右子树 */
void InOrder<T>(TreeNode<T> root)
{
	if (root == null) return;
	InOrder(root.LeftChild);
	Console.WriteLine(root.Value);  // 4 2 5 1 6 3 7
	InOrder(root.RightChild);
}

/* 左子树 -> 右子树 -> 根节点 */
void PostOrder<T>(TreeNode<T> root)
{
	if (root == null) return;
	PostOrder(root.LeftChild);
	PostOrder(root.RightChild);
	Console.WriteLine(root.Value);  // 4 5 2 6 7 3 1