树 Tree

标签：node Right curr comp Tree null Left

树的结构

后继节点 和该后继节点的父节点，（一个节点的后继节点是指，这个节点在中序遍历序列中的下一个节点，相应的，前驱节点是指这个节点在中序遍历序列中的上一个节点

树的结构多种多样，然而现实中最常用的是二叉树，也就是每个节点度至多为二的数
在这里我介绍两种主要的二叉树

二叉堆

堆（heap）是优先队列（priority queue）的一种实现，其主要接口为插入元素和删除最大（最小）元素
堆则是优先队列的树状实现，可在 \(T(n)=\log{n}\) 时间复杂度（最坏情况）下完成插入和删除，分最小堆和最大堆，除了二叉堆外也有三叉堆等，这里展示了二叉堆的实现

请主要关注 insert(), delete_head(), shift_up(), shift_down() 方法，不妨以最大堆为例

template <typename T>
class PriorityQueue
{
public:
    PriorityQueue(std::function<bool(T, T)> comp = std::less<T>())
        : _element(), _comp(comp) {}
    PriorityQueue(std::initializer_list<T> initializer,
                  std::function<bool(T, T)> comp = std::less<T>())
        : _element(initializer), _comp(comp)
    {
        std::sort(_element.begin(), _element.end(), std::not2(_comp));
    }
    template <typename Iterator>
    PriorityQueue(Iterator begin, Iterator end,
                  std::function<bool(T, T)> comp = std::less<T>())
        : _element(), _comp(comp)
    {
        while (begin != end)
            insert(*begin++);
    }

    size_t size() const { return _element.size(); }
    size_t capacity() const { return _element.capacity(); }

    auto cbegin() const { return _element.cbegin(); }
    auto cend() const { return _element.cend(); }
    // 只读，不允许修改，以保证堆的状态不被破坏

    void insert(const T &value)
    {
        _element.push_back(value);
        shift_up(size() - 1);
    }
    T delete_head()
    {
        if (_element.size() == 0)
            throw std::runtime_error("empty priority queue");
        swap(0, size() - 1); // 现在最值被放在最后了
        T res = _element.back();
        _element.pop_back();
        shift_down(size());
        return res;
    }

private:
    std::vector<T> _element;
    std::function<bool(T, T)> _comp;

    // 两个工具函数
    void swap(int i, int j)
    {
        T t(_element[i]);
        _element[i] = _element[j];
        _element[j] = t;
    }
    bool compare(int i, int j) { return _comp(_element[i], _element[j]); }

    void shift_down(int n) // 自顶向下
    {
        int i = 0;
        int down;
        while ((down = (i << 1) + 1) < n) // [down]是[i]的左子节点，而[down+1]是i的右子节点
        {
            if (down + 1 < n && compare(down, down + 1)) // 若[i]小于[down]或[down+1]，交换其中更大者
                ++down;
            if (compare(down, i))
                return;
            swap(down, i);
            i = down;
        }
    }
    void shift_up(int i) // 自底向上
    {
        int up; // up是i的父节点
        while (i > 0 && compare(up = (i - 1) >> 1, i)) // 若[up]小于[i]，交换二者
        {
            swap(i, up);
            i = up;
        }
    }
    // shift_up 和 shift_down 并称堆的有序化操作，方法都是化局部无序为有序
};

函数定义放在类中主要是为了方便读者阅读

二叉堆的应用

寻找最大的\(M\)个数

先举出使用不同方法的复杂度（\(N\)为输入量）

算法时间复杂度空间复杂度

排序 \(N\log{M}\) \(N\)

数组和链表 \(NM\) \(M\)

堆 \(N\log{M}\) \(M\)

可以看到堆对时间和空间的利用都很好
堆排序
堆排序和快速排序、归并排序并称三大 \(N\log{N}\) 排序算法
其思路为：从左至右将数组变为堆，将堆的最值取出从右至左放入

算法	时间复杂度	空间复杂度
排序	\(N\log{M}\)	\(N\)
数组和链表	\(NM\)	\(M\)
堆	\(N\log{M}\)	\(M\)

void heap_sort(int a[], int len)
{
    using std::swap;
    int index = 0;
    while (++index < len)
    {
        int up;
        int i = index;
        while (i > 0 && a[up = (i - 1) >> 1] < a[i])
        {
            swap(a[up], a[i]);
            i = up;
        }
    }
    while (--index)
    {
        swap(a[0], a[index]);
        int i = 0;
        int down;
        while ((down = (i << 1) + 1) < index)
        {
            if (down + 1 < index && a[down] < a[down + 1])
                ++down;
            if (a[down] < a[i])
                break;
            swap(a[down], a[i]);
            i = down;
        }
    }
}

二叉搜索树

二叉搜索树（Binary Search Tree）保证每一次查找都是二分搜索（\(T(n)=\log{n}\)），这是因为它的键值（值）是有序的，满足每个节点的键值都大于其左子树的任意节点的键值，小于其右子树的任意节点的键值

使用符号表，包含 Insert(), Remove(), IndexOf(), Select() 插入、删除、支持两种索引（下标和键值）的二叉搜索树

public class BinarySearchTree<TKey, TValue>
    where TKey : IComparable<TKey>, IEquatable<TKey>
{
    public class Node
    {
        public TKey Key { get; internal set; }
        public TValue Val { get; set; }
        public Node Left { get; internal set; }
        public Node Right { get; internal set; }
        public int SubNodeCount { get; internal set; }
        public Node(TKey key, TValue val, Node left, Node right, int subNodeCount)
        {
            Key = key;
            Val = val;
            Left = left;
            Right = right;
            SubNodeCount = subNodeCount;
        }
    }
    private Node _Root;
    public int Count { get => SubNodeCount(_Root); }
    private int SubNodeCount(Node node)
    {
        return node is null ? 0 : node.SubNodeCount;
    }
    public TValue this[TKey key]
    {
        get
        {
            Node node = _Root;
            while (node != null)
            {
                int comp = node.Key.CompareTo(key);
                if (comp < 0)
                    node = node.Left;
                else if (comp > 0)
                    node = node.Right;
                else
                    return node.Val;
            }
            return default(TValue);
        }
        set
        {
            if (_Root is null)
                return;
            Node prev;
            Node curr = _Root;
            int comp;
            do
            {
                comp = curr.Key.CompareTo(key);
                if (comp == 0)
                {
                    curr.Val = value;
                    return;
                }
                prev = curr;
                if (comp < 0)
                    curr = curr.Left;
                else
                    curr = curr.Right;
            }
            while (curr is not null);
            if (comp < 0)
                prev.Right = new Node(key, value, null, null, 1);
            else
                prev.Left = new Node(key, value, null, null, 1);
            ++prev.SubNodeCount;
        }
    }
    public void Insert(TKey key, TValue val)
    {
        if (_Root is null)
        {
            _Root = new Node(key, val, null, null, 1);
            return;
        }
        Node prev;
        Node curr = _Root;
        int comp;
        do
        {
            comp = curr.Key.CompareTo(key);
            if (comp == 0)
                return;
            prev = curr;
            if (comp > 0)
                curr = curr.Left;
            else
                curr = curr.Right;
        }
        while (curr is not null);
        if (comp < 0)
            prev.Right = new Node(key, val, null, null, 1);
        else
            prev.Left = new Node(key, val, null, null, 1);
        ++prev.SubNodeCount;
    }
    public bool Remove(TKey key)
    {
        if (_Root is null)
            return false;
        Node prev = _Root;
        Node curr = _Root;
        int comp;
        Stack<Node> path = new Stack<Node>();

        do
        {
            path.Push(curr);
            comp = curr.Key.CompareTo(key);
            if (comp == 0)
                break;
            prev = curr;
            if (comp > 0)
                curr = curr.Left;
            else
                curr = curr.Right;
        }
        while (curr is not null);

        if (curr is null)
            return false;

        if (curr.Left is null)
        {
            if (curr == _Root)
                _Root = _Root.Right;
            else if (curr == prev.Left)
                prev.Left = curr.Right;
            else
                prev.Right = curr.Right;
            --prev.SubNodeCount;
        }
        else if (curr.Right is null)
        {
            if (curr == _Root)
                _Root = _Root.Left;
            else if (curr == prev.Left)
                prev.Left = curr.Left;
            else
                prev.Right = curr.Right;
            --prev.SubNodeCount;
        }
        else
        {
            Node replacePrev;
            Node replaceCurr = curr.Right;
            while (replaceCurr.Left is not null)
            {
                path.Push(replaceCurr);
                replacePrev = replaceCurr;
                replaceCurr = replaceCurr.Left;
            }

            replacePrev = replaceCurr.Right;
            replaceCurr.Left = curr.Left;
            replaceCurr.Right = curr.Right;

            if (curr == _Root)
                _Root = replaceCurr;
            else if (curr == prev.Left)
                prev.Left = replaceCurr;
            else
                prev.Right = replaceCurr;

            curr = replaceCurr;
        }

        foreach (Node node in path)
            --node.SubNodeCount;
        curr.SubNodeCount = SubNodeCount(curr.Left) + SubNodeCount(curr.Right) + 1;
        return true;
    }
    public Node Select(int index)
    {
        if (_Root is null || index < 0 || _Root.SubNodeCount <= index)
            return null;
        Node node = _Root;
        int t;
        while ((t = SubNodeCount(node.Left)) != index)
        {
            if (t > index)
            {
                node = node.Left;
            }
            else
            {
                node = node.Right;
                index -= t + 1;
            }
        }
        return node;
    }
    public int IndexOf(TKey key)
    {
        Node node = _Root;
        int t = 0;
        int comp;
        while (node is not null && (comp = node.Key.CompareTo(key)) != 0)
        {
            if (comp < 0)
            {
                node = node.Left;
            }
            else
            {
                t += SubNodeCount(node.Left) + 1;
                node = node.Right;
            }
        }
        if (node is null)
            return -1;
        return t + SubNodeCount(node.Left);
    }
}

树的四种遍历方法（前序遍历、中序遍历、后序遍历和层序遍历）

下面列出这四种方法的迭代版本（使用栈或队列）

// 返回值也可以是IEnumerable<TValue>
public IEnumerator<TValue> PreorderTraversal()
{
    if (_Root is null)
        yield break;
    Stack<Node> nodeStack = new Stack<Node>();
    Node node = _Root;
    while (node is not null || !nodeStack.IsEmpty())
    {
        while (node is not null)
        {
            yield return node.Val;
            nodeStack.Push(node);
            node = node.Left;
        }
        node = nodeStack.Pop().Right;
    }
}
public IEnumerator<TValue> InorderTraversal()
{
    if (_Root is null)
        yield break;
    Stack<Node> nodeStack = new Stack<Node>();
    Node node = _Root;
    while (node is not null || !nodeStack.IsEmpty())
    {
        while (node is not null)
        {
            nodeStack.Push(node);
            node = node.Left;
        }
        node = nodeStack.Pop();
        yield return node.Val;
        node = node.Right;
    }
}
public IEnumerator<TValue> PostorderTraversal()
{
    if (_Root is null)
        yield break;
    Stack<Node> indexStack = new Stack<Node>();
    Node node = _Root;
    Node prev = null;
    while (node is not null || !indexStack.IsEmpty())
    {
        while (node is not null)
        {
            indexStack.Push(node);
            node = node.Left;
        }
        node = indexStack.Top;
        if (node.Right is null || node.Right == prev)
        {
            yield return node.Val;
            prev = node;
            node = null;
            indexStack.Pop();
        }
        else
            node = node.Right;
    }
}
public IEnumerator<TValue> LayerorderTraversal()
{
    if (_Root is null)
        yield break;
    Queue<Node> nodeQueue = new Queue<Node>();
    Node node;
    nodeQueue.Enqueue(_Root);
    while (nodeQueue.Count != 0)
    {
        node = nodeQueue.Dequeue();
        yield return node.Val;
        if (node.Left is not null)
            nodeQueue.Enqueue(node.Left);
        if (node.Right is not null)
            nodeQueue.Enqueue(node.Right);
    }
}

延伸阅读

常见的树除了二叉树还有四叉树、八叉树等。

四叉树常见的应用有图像处理、二维场景中的碰撞检测等。

标签：node,Right,curr,comp,Tree,null,Left
From： https://www.cnblogs.com/violeshnv/p/16833428.html

树的结构

二叉堆

二叉堆的应用

二叉搜索树

树的四种遍历方法（前序遍历、中序遍历、后序遍历和层序遍历）

延伸阅读

相关文章

赞助商

阅读排行