首页 计算机 算法与数据结构

不为情欲所惑，不为众邪所娆，精进无为，吾保此人必得道矣。

# 树

# 定义

# 递归定义

树是由nn 个节点组成的有限集合。若n=0n=0，称为空树。以后一般不考虑树为空树的情况。

树中有一个无前驱的节点，称为根 (root)，除根以外的每一个节点可以划分成mm 个互不相交的集合，每个集合都是一棵树，称为子树 (subtree)。每个节点的子树个数称为节点的度，度为00 的节点称为叶子节点 (leaf)，其余称为分支节点。树中节点的最大度称为树的度。树的层数称为树的深度。一些互不相交的树的集合称为森林。此外，我们还常用双亲 (parent)、孩子 (children)、兄弟 (sibling)、祖先 (ancestor)、后代 (descendent) 等来描述和命名对应的关系。

# 常见表示

树的常见表示包括四种表示方法，依次是树形表示法、文氏图表示法、凹入表示法及括号表示法。其中，括号表示法指的是树的根节点写在括号左，括号内采用每个逗号隔开各个子树的表示方法。

# 树的遍历

我们假设一棵树为 A (B (E,F),C (G),D (H,I,J))。以此例子讨论树的遍历方式。

# 按层次序遍历

按层次序遍历指的是自上至下遍历每一层，在每层中从左至右依次访问各个节点。例如，上述例子中树按层次序遍历的结果为 A,B,C,D,E,F,G,H,I,J。对于森林，按层次序遍历同样依次遍历森林中的各层节点。

# 先根次序遍历

先根次序遍历指的是对每一次访问，先访问根再从左至右依次访问根的各子树，又叫中序遍历，简称 VLR 或 DLR。例如上述例子中树的先根次序遍历的结果为 A,B,E,F,C,G,D,H,I,J，也即括号表示法的字母序。对于森林，只需要依次先根遍历各子树。

# 后根次序遍历

后根次序遍历指的是对每一次访问，先由左至右访问根的各子树，再访问根节点，又叫后序遍历，简称 LRD。例如上述例子中树的后根次序遍历的结果为 E,F,B,G,C,H,I,J,A。对于森林，只需要后根遍历各子树。事实上，对以上三种遍历方式在森林中的表示，我们可以视作对所有子树的根节点添加一个公共根节点再进行单个子树的遍历，最后删除添加的节点即可。

# 树的存储结构

对一个树，我们选择何种存储结构，即在树中构建哪些域，根本上取决于我们需要对这个树的节点作哪些操作。如果我们只需要从叶子至根遍历树，那么我们只需要构建一个指向父亲节点的指针即可；如果需要从根向下遍历，那么我们就需要建立指向孩子的指针。

# 二叉树

# 线索二叉树

线索二叉树是在节点中记录遍历方式的二叉树。其节点结构如下：

struct node{
    int data;
    node* leftChild;
    node* rightChild;
    int leftTag;
    int rightChild;
};

其中， Tag 标签是一个标志域，表示对应的 Child 标签指向的是其孩子还是前驱 / 后继。若 Tag = 0 ，则表示 Child 指向孩子，否则表示指向前驱。

线索二叉树几乎没有什么意义。线索二叉树寻找前驱后继的期望复杂度与未线索化的二叉树相同，都是O(1)O(1) 级别，而且线索二叉树的前驱后继查询不是严格O(1)O(1) 的！此外，线索二叉树的最初设计目的是为了利用叶子结点的空指针域，但是在这样的利用下需要重新添加 Tag 表示指向的对象是前驱还是孩子，这反而增大了空间开销。虽然线索二叉树可以降低内存时遍历树的堆栈开销，但是这点节约几乎不具有价值。但抛开线索二叉树不谈，对一个数据结构进行线索化的确是有价值的想法。

# 二叉搜索树

二叉搜索树可以用来表示数据的顺序关系。其节点结构仅需要包括 data,leftChild,RightChild 三个域。其中，一般规定左子树的所有数据小于父亲节点的数据，又小于右子树的所有节点的数据。于是一个二叉搜索树可以按如下方式定义：

二叉搜索树
typedef struct node{
    int data;
    node* leftChild;
    node* rightChild;
}node;

此外，如果有需要，也可以在节点内部定义一个子树的高度 height 和大小 size 等信息。

二叉搜索树与其余二叉树的组织方式就在于节点排序希望查找某数据在树中是否存在时，只需要从根节点开始进行区间分割，即可递归找到数据。代码如下：

二叉搜索树查找
node* findNode(int data, node* root){
    if (!root) return nullptr;
    if (data == root->data) return root;
    if (data < root->data) return findNode(data, root->leftChild);
    if (data > root->data) return findNode(data, root->rightChild);
}
bool ifExist(int data, node* root){
    return findNode(data, root);
}
此外，二叉搜索树的重要操作还包括插入节点和删除节点。在插入过程中，我们一般默认没有数据相同的两个节点。于是其插入过程就是一个递归寻找的过程。
二叉搜索树插入节点
void add(int data, node* root){
    if (data < root->data && !root->leftChild){
        node* p = (node*)malloc(sizeof(node));
        p->data = data;
        root->leftChild = p;
    }
    else if (data > root->data && !root->rightChild){
        node* p = (node*)malloc(sizeof(node));
        p->data = data;
        root->rightChild = p;
    }
    if (data < root){
        return add(data, root->leftChild);
    }
    else {
        return add(data, root->rightChild);
    }
}
删除过程包括删除最大 (最小) 节点和删除某一个数据对应的节点。删除最大和最小节点的操作是容易的，只需要递归找最左侧和最右侧的叶子就可以了。
二叉搜索树删除最大节点
void eraseMax(node* root){
    if (root->rightChild) eraseMax(node* root->rightChild);
    else free(root);
}
最小节点的删除也是类似的。
二叉搜索树删除最小节点
void eraseMin(node* root){
    if (root->leftChild) eraseMin(node* root->leftChild);
    else free(root);
}
若删除一个指定节点，关键的问题在于如何解决左右子树的安排问题。若待删除的节点没有左子树或右子树之一，那么直接将其唯一的子树根代替其位置即可。否则，我们可以将其左子树的最大值或右子树的最小值对应的叶子移至被删除的节点，这样仍然满足一个二叉搜索树结构。其代码如下：
二叉搜索树删除指定节点
void eraseNode(int data, node* root){
    findNode(data, root);
    if (!root->leftChild){
    }
}
# kd 树
kd 树 (k-dimension tree) 是用来描述kk 维空间中点分布的数据结构。