4

Preliminaries

可以使用递归的方式来定义树(tree)，树是节点的集合。这个集合可以为空，也可以包含一个被称为根节点(root)的特殊的节点 \(r\) 以及0个或多个非空的子树，每个子树的根节点通过一有向边(edge)与根节点相连每个子树的根节点是 \(r\) 的子节点 (child) ，而 \(r\) 则是它们的父节点 (parent) 。下图为使用递归定义的树的结构 ![[recursion_tree.png]]

如果一个树有 \(N\) 个节点，那么其中一个节点是根节点，同时还存在 \(N-1\) 条边，如下图所示 ![[tree_sketch.png]]

没有子节点的节点被称为叶子节点(leave)，例如上图中的 \(B,C,H,I,P,Q,K,L,M\) 和 \(N\) 父节点相同的节点被称为兄弟节点(sibling)，例如上图中的 \(K,L,M\) 节点 \(n_1\) 到 \(n_k\) 的通路(path)是节点 \(n_1,n_2,\cdots, n_k\) 的序列，其中 \(n_i\) 是 \(n_{i+1}\) 的父节点通路的长度(length)是通路的边的数量，即 \(k-1\) 。在树中，从根节点到节点只有一条通路

节点到自身的通路长度为0

节点 \(n_i\) 的深度(depth)是从根节点到 \(n_i\) 的通路的长度

根节点的深度为0

节点 \(n_i\) 的高度(height)是从节点 \(n_i\) 到叶子节点的最长通路的长度

如果 \(n_1\) 和 \(n_2\) 之间存在一条通路，那么 \(n_1\) 是 \(n_2\) 的祖先(ancestor)，\(n_2\) 是 \(n_1\) 的后代(descendant)

Implementation of Tree

一种实现树的方式是让每个节点保存它的每一个子节点的链接这种方法的缺点是子节点的数量可能会非常多，并且不知道会有多少个子节点。实现起来不仅麻烦，而且会造成大量的空间浪费

另一种实现树的方式将子节点保存在两个链表中，如下图所示： ![[linked_tree.png]] 其中水平的箭头表示 firstChild ，而向左或者向右的箭头表示 nextSiblings 可以将节点定义为如下的结构

struct TreeNode
{
    Object element;
    TreeNode* firstChild;
    TreeNode* nextSiblings; 
};

Tree Traversals With an application

许多操作系统使用树来表示目录结构，包括 UNIX 和 DOS ![[unix_fs.png]]

Binary Tree

一个所有节点的子节点数量都不超过2的树被称为二叉树(binary tree) ,如下图所示，一个二叉树有一个根节点和两个子树(\(T_L\) 和 \(T_R\))组成

![[binary_tree_sketch.png]]

二叉树的平均深度为 \(O(\sqrt{N})\) ；而在最差情况下，其深度为 \(N-1\) ，此时，二叉树会退化为链表，如下图所示 ![[worst_case_binary.png]]

Implementation

因为二叉树的每个节点最大只有两个子节点，所以可以选择保存每个子节点的链接。可以将 BinaryNode 定义为

struct BinaryNode
{
    Object element;
    BinaryNode* left;
    BinaryNOde* right;
};

Expression Tree

二叉树的一个应用是表达式树，如下图所示 ![[expression_tree_example.png]] 叶子节点是操作数（常数或者变量名），而其他节点则是运算符下面这个算法展示了如何将后缀表达式转换为表达式树，一次读取一个表达式的一个符号，如果是操作数，则创建一个单节点的树并将指向它的指针压入栈中；如果是运算符，那么从栈中弹出两个树 \(T_1\) 和 \(T_2\) ，然后构建出一个以运算符为根节点，\(T_1\) 为右节点，\(T_2\) 为左节点的树

假设输入为

a b + c d e + * *

前两个符号都是操作数，构建两个单节点的树，并将指向它们的指针压入栈中 ![[expression_tree_1.png]]

然后，是一个 + ，所以从栈中弹出两个树，将 + 作为根节点构建一颗新树并压入栈中 ![[expression_tree_2.png]]

然后，c d e 都是操作数，构建三个单节点的树并压入栈中 ![[expression_tree_3.png]] 然后，是一个 + ，合并 d 和 e ![[expression_tree_4.png]] 然后，是一个 * ，从栈中弹出两颗树并合并 ![[expression_tree_5.png]]

最后，是一个 * 从栈中弹出两颗树并合并 ![[expression_tree_6.png]]

void expression_tree()
{
    std::string input;
    std::stack<Node*> trees;
    std::cin >> input;

    for (auto ch : input)
    {
        if (std::isalnum(ch))
        {
            Node* node = new Node(ch);
            trees.push(node);
        }
        else
        {
            Node* t1 = trees.top();
            trees.pop();
            Node* t2 = trees.top();
            trees.pop();

            Node* node = new Node(ch, t2, t1);
            trees.push(node);
        }
    }
}

Binary Search Tree

二叉搜索树的一个重要性质是对于任意节点，它的左子树的所有节点的值都小于它的值；它的右子树的所有节点的值都大于它的值。这意味着树中的所有元素可以以一个固定的方式进行排序下图左边的树是二叉搜索树，而右边的不是（7在6的左子树） ![[bst_example.png]]

二叉搜索树的元素类型必须是可比较的

下面是二叉搜索树的 ADT

template<typename T>
struct TreeNode
{
    T element;
    TreeNode* left;
    TreeNode* right;

    TreeNode(T elem, TreeNode* l = nullptr, TreeNode* r = nullptr);
};

template<typename T>
class BinarySearchTree
{
private:
    TreeNode<T>* root;

    void insert(const T& x, TreeNode<T>*& node);
    void remove(const T& x, TreeNode<T>*& node);
    bool contain(const T& x, TreeNode<T>* node) const;
    TreeNode<T>* findMin(TreeNode<T>* node) const;
    TreeNode<T>* findMax(TreeNode<T>* node) const;
    void printTree(TreeNode<T>* node) const;
    void makeEmpty(TreeNode<T>* node);

public:
    BinarySearchTree();
    ~BinarySearchTree();

    const T& findMin() const;
    const T& findMax() const;
    bool contain(const T& x) const;
    bool isEmpty() const;
    void printTree() const;
    void insert(const T& x);
    void remove(const T& x);
    void makeEmpty();
};

接下来是具体的实现，public 方法只是简单的调用 private 方法 contain 如果节点在树中则返回 true ，否则返回 false 。如果树是空的，那么就直接返回 false 利用二叉搜索树的性质，根据被查找节点的值和当前节点的大小关系，递归的搜索左子树或右子树

bool contain(const T& x, TreeNode<T>* node) const
{
    if (node == nullptr)
        return false;

    if (x < node->element)
        return contain(x, node->left);
    else if (x > node->element)
        return contain(x, node->right);
    else
        return true;
}

findMax 和 findMin 二叉搜索树最大的元素是最右边的元素，最小的元素是最左边的元素。所以只需要一直向右（或向左）查找，如果右子树（或左子树）为空则返回。可以使用递归或者递推来实现这个方法 FindMin() 和 FindMax 函数的时间复杂度均为 \(O(d)\)，\(d\) 为树的深度

// private method
TreeNode<T>* findMin(TreeNode<T>* node) const
{
    if (node == nullptr)
        return nullptr;

    if (node->left == nullptr)
        return node;
    else
        return findMin(node->left);
}

TreeNode<T>* findMax(TreeNode<T>* node) const
{
    if (node != nullptr)
    { 
        while (node->rgiht != nullptr)
        {
            node = node->right;
        }
    }
    return node;
}

// public method
const T& findMax() const
{
    TreeNode<T>* node = findMax(root);
    if (!node)
        throw std::runtime_error("empty tree");
    return node->element;
}

const T& findMin() const
{
    TreeNode<T>* node = findMin(root);
    if (!node)
        throw std::runtime_error("empty tree");
    return node->element;
}

insert 插入节点时只需要像 contain 一样向下寻找位置，如果 \(X\) 的已经在树中，那么什么都不需要做。如下图所示

![[bst_insertion.png]]

void insert(const T& x, TreeNode<T>*& node)
{
    if (node == nullptr)
        node = new TreeNode<T>(x, nullptr, nullptr);
    else if (x < node->element)
        insert(x, node->left);
    else if (x > node->element)
        insert(x, node->right);
    else
        ;
}

remove 这是二叉搜索树中最难处理的部分。我们要处理有三种情况： - 叶子结点 - 有一个孩子 - 有两个孩子

void remove(const T& x, TreeNode<T>*& node)
{
    if (node == nullptr)
        return;

    if (x < node->element)
        remove(x, node->left);
    else if (x > node->element)
        remove(x, node->right);
    else if (node->left != nullptr && node->right != nullptr)
    {
        node->element = findMin(node->right)->element;
        remove(node->element, node->right);
    }
    else
    {
        TreeNode<T>* old = node;
        node = (node->left != nullptr) ? node->left : node->right;
        delete old;
    }
}

destructor 析构函数调用 makeEmpty()，递归的释放树的节点

void makeEmpty(TreeNode<T>* node)
{
    if (node != nullptr)
    {
        makeEmpty(node->left);
        makeEmpty(node->right);
        delete node;
    }
}

~BinarySearchTree()
{
    makeEmpty(root);
    delete root;
}