树的定义

树（tree）是包含 $n(n \ge 1)$ 个结点， $(n-1)$ 条边的有穷集，其中：

每个元素成为结点 (node)，只有有限个子结点或无子结点
有一个特定的结点（无父结点）称为根结点 (root)
每一个非根节点有且只有一个父节点
除了根节点外，每个子节点可以分为多个不相交的子树 (subtree)
树里面没有环路 (cycle)
树没有结点的时候称为空树 (empty tree)

连通、边数等于顶点数减 1 的结构一定是一棵树

术语

结点的度(degree)：一个结点含有的子树的个数称为该节点的度
树的度：一棵树中，最大的结点度称为树的度
叶结点：又称 终端结点，度为零的结点
分支结点：又称 非终端结点，度不为零的结点
兄弟结点：具有相同父结点的节点互称为兄弟结点；
层次(layer)：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
深度(depth)：对于任意节点 i，i 的深度为从根到 i 的唯一路径长，根的深度为 0
高度(height)：对于任意节点 i，i 的高度为从 i 到一片树叶的最长路径长，所有树叶的高度为 0
祖先：从根到该结点所经分支上的所有结点
子孙：以某结点为根的子树中任一结点都称为该结点的子孙
森林(forest)：由 m（m>=0）棵互不相交的树的集合称为森林；

种类

无序树：树中任意结点的子结点之间没有顺序关系，也称为 自由树
- 无回路的连通图
有序树：树中任意结点的子结点之间有顺序关系
二叉树：每个结点最多含有两个子树的树称为二叉树
- 完全二叉树：对于一棵二叉树，假设其深度为 d（d>1）。除了第 d 层外，其它各层的节点数目均已达最大值，且第 d 层所有节点从左向右连续地紧密排列
- 满二叉树：所有叶节点都在最底层的完全二叉树
- 二叉查找树、AVL 树
- 哈夫曼树 (Huffman)：带权路径最短的二叉树，又称最优二叉树
- B 树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树

二叉树

存储结构与基本操作

存储结构

struct Node {
	typename data;
	Node* left;
	Node* right;
};

Node* newNode(int v) {
    Node* node = new Node;
    node->data = v;
    node->left = node->right = NULL;
    return node;
}

基本操作：主要有建立、查找、修改、插入与删除

查找、修改

void search(Node* root, int x, int newData) {
	if (root == NULL) return;
    if (root->data == x) {
        root->data = newData;
    }
    search(root->left, x, newData);
    search(root->right, x, newData);
}

由于是修改 root 指向的内容，即树的内容，因此无需引用

插入

void insert(Node * &root, int x) {
	if (root == null) {
        root = newNode(x);
        return;
    }
    if (根据二叉树的性质，x 应该插在左子树) {
        insert(root->left, x);
    } else {
        insert(root->right, x);
    }
}

由于要修改root，即修改树的结构，所以root 使用了引用 &

建立

Node* create(int data[], int n) {
	Node* root = NULL;
	for (int i = 0; i < n; i++) {
		insert(root, data[i]);
	}
	return root;
}

此外，对于完全二叉树，可以直接用数组存储：对于任意结点，编号为 x，则左孩子一定是 2x，右孩子一定是 2x + 1

遍历

二叉树有四种遍历方式：先序遍历、中序遍历、后序遍历、层次遍历。

先序遍历、中序遍历、后序遍历

void preorder(Node* root) {
    if (root == NULL) return;
    printf("%d\n", root->data);
    preorder(root->left);
    preorder(root->right);
}

void inorder(Node *root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d\n", root->data);
    inorder(root->right);
}

void postorder(Node *root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d\n", root->data);
}

先序遍历的第一个是根结点，后序遍历的最后一个是根结点
中序遍历有根结点的话，可以分出左右子树

层次遍历

void layerOrder(Node* root) {
    queue<Node*> q;
    q.push(root);
    while(!q.empty()) {
        Node* node = q.front();
        q.pop();
        printf("%d\n", node->data);
        if (node.left != NULL) q.push(node.left);
        if (node.right != NULL) q.push(node.right);
    }
}

根据先序遍历和中序遍历还原二叉树：

// 给定 pre、in 数组，还原二叉树
Node* create(int preL, int preR, int inL, int inR) {
    if (preL > preR) return NULL;
    
    Node* root = new node;
    root->data = pre[preL];
    
    int k; // 当前根结点在中序遍历的位置
    for (k = inL; k <= inR; k++) {
        if (in[k] == pre[preL]) break;
    }
    int numLeft = k - inL; //左子树结点个数
    
    root->left = create(preL + 1, preL + numLeft, inL, k - 1);
    root->right = create(preL + numLeft + 1, preR, k + 1, inR);
    
    return root;
}

还原二叉树必须要有中序遍历
已知中序遍历，再得到先序遍历、后序遍历、层次遍历的其中一个，就可以唯一确认一棵树

静态实现

与静态链表一样，二叉树也可以采用静态实现的方法，将结点的 left、right 变成在数组中的索引号

树

这里的“树”是一般意义上的树，即子结点个数不限且子结点没有先后次序的树，而不是二叉树

存储结构

struct Node {
    typename data;
    vector<Node*> child;
};

Node* newNode(int v) {
    Node* node = new Node;
    node->data = v;
    node->child.clear();
    return node;
}

遍历

一般树的遍历有：先根遍历、层序遍历

先根遍历

void preOrder(Node* root) {
	printf("%d\n", root->data);
    for (Node* i : root->child) {
        preOrder(i);
    }
}

层序遍历

void layerOrder(Node* root) {
    queue<Node*> q;
    q.push(root);
    while(!q.empty()) {
        Node* cur = q.front();
        q.pop();
        printf("%d\n", root->data);
        for (Node* i : root->child) {
            q.push(i);
        }
    }
}