数据结构（三）二叉树

有n个结点时，叶子节点为：
1. n 为奇数时，(n+1)/2
2. n 为偶数时，n/2
用数组存树的时候，父节点为i时，左为 2i + 1 ，右为 2i + 1
哈弗曼树是带权路径长度最短的树。做法为将权由大到小排序，然后依次放置。例如[7 6 5 4 3 2]，如果是三叉树的话，路径半径为 7+6+5+4*2+3*2+2*2 = 46
在任意一颗二叉树中，度为0的叶子节点总是比度为2的结点多一个。
先序：先自己，左，右
中序：先左，自己，右
后序：先左，右，自己用代码表示就是：

public class Tree(int value)
{
    public int Value { get; set; } = value;
    public Tree? Left { get; set; }
    public Tree? Right { get; set; }
 
    /// <summary>
    /// 先序遍历 自己 -> 左 -> 右
    /// </summary>
    /// <returns></returns>
    public List<int> PreorderTraversal()
    {
        var list = new List<int> { Value };
 
        list.AddRange(Left?.PreorderTraversal() ?? []);
        list.AddRange(Right?.PreorderTraversal() ?? []);
 
        return list;
    }
 
    /// <summary>
    /// 中序遍历 左 -> 自己 -> 右
    /// </summary>
    /// <returns></returns>
    public List<int> InorderTraversal()
    {
        var list = new List<int>();
 
        list.AddRange(Left?.InorderTraversal() ?? []);
        list.Add(Value);
        list.AddRange(Right?.InorderTraversal() ?? []);
 
        return list;
    }
 
    /// <summary>
    /// 后序遍历 左 -> 右 -> 自己
    /// </summary>
    /// <returns></returns>
    public List<int> PostorderTraversal()
    {
        var list = new List<int>();
 
        list.AddRange(Left?.PostorderTraversal() ?? []);
        list.AddRange(Right?.PostorderTraversal() ?? []);
        list.Add(Value);
 
        return list;
    }
}

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。