数据结构 树

树是一种非线性数据结构

树的基本概念

• 树
• 节点的度（degree）:
• 树的深度

二叉树

Binary Tree是最简单最基本的树结构

• 重要操作遍历：
  依据节点被访问的顺序分为：
  1.先序遍历
  2.中序遍历
  3.后序遍历
  4.层序遍历（迭代用队列完成）
  [注]一般用递归的方法，但是迭代效率（用栈来完成）更高
  对于所有的合法的DFS求解过程，都可以把它画成树的形式，此时死胡同等价于树中的叶子节点，岔路口等价于树的非叶子节点，对这棵树的DFS遍历过程就是树的先序遍历过程（见算法笔记DFS）

/*给出中序和后序遍历的序列，输出层序遍历的序列*/
#include<iostream>
#include<queue>
using namespace std;
int postorder[40] = { 0 };
int inorder[40] = { 0 };
//int postorder[7] = { 2 ,3 ,1 ,5, 7, 6, 4 };
//int inorder[7] = { 1,2,3,4,5,6,7 };

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) :val(x), left(NULL), right(NULL) {};
};
//先把树构造出来，再层序遍历
TreeNode* buildTree(int pstart, int pend, int istart, int iend) {
    if (pstart > pend || istart > iend) {
        return NULL;
    }
    int val = postorder[pend];
    int pos = 0;//头结点在中序序列的位置
    TreeNode* root = new TreeNode(val);
    for (;inorder[pos] != val; pos++);
    int num = pos - istart;//左子树有几个节点
    TreeNode* left = buildTree(pstart, pstart+num-1, istart, pos-1);
    TreeNode* right = buildTree(pstart+num, pend - 1, pos + 1, iend);
    root->left = left;
    root->right = right;
}

void LayerOrder(TreeNode *root) {
    //层序遍历用队列
    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()) {
        TreeNode* node = que.front();
        cout << node->val;
        que.pop();
        if (node->left != NULL) {
            que.push(node->left);
        }
        if (node->right != NULL) {
            que.push(node->right);
        }
        if (!que.empty()) {
            cout << " ";
        }
    }

}

int main() {
    //int n = 7;
    //TreeNode* tree = buildTree(0, 6, 0, 6);
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> postorder[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> inorder[i];
    }
    LayerOrder(buildTree(0,m-1,0,m-1));
    return 0;
}

• 二叉树的构建
  一般用层序遍历（从上到下，从左到右）来构建二叉树

二叉搜索树（BST）

有序特性：父节点比左子节点大，比右子节点小，中序遍历得到的序列是从小到大的排好序的序列。
对排序和查找都很有用：比如，查找最大值就找到最右分支端节点；利于动态二分查找（直接在左子树or右子树查找。。。）
基本操作
1.查找
最坏的复杂度O(h),h为二叉树的高度
2.插入
3.删除

平衡二叉树(AVL:严格平衡的二叉搜索树)

AVL的插入，删除，查找操作均可在O(logN)时间内完成。
定义：
【1】. 任一节点的左右子树均为AVL树；
【2】.任一节点左右子树高度差的绝对值不超过1
平衡因子：左子树和右子树的高度差称为该节点的平衡因子

【来自wiki百科AVL旋转描述】
假设平衡因子是左子树的高度减去右子树的高度所得到的值，又假设由于在二叉排序树上插入节点而失去平衡的最小子树根节点的指针为a（即a是离插入点最近，且平衡因子绝对值超过1的祖先节点），则失去平衡后进行的规律可归纳为下列四种情况：

• 单向右旋平衡处理LL：由于在a的左子树根节点的左子树上插入节点，a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次右旋转操作；
• 单向左旋平衡处理RR：由于在a的右子树根节点的右子树上插入节点，a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行一次左旋转操作；
• 双向旋转（先左后右）平衡处理LR：由于在a的左子树根节点的右子树上插入节点，a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。
• 双向旋转（先右后左）平衡处理RL：由于在a的右子树根节点的左子树上插入节点，a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。

-------AVL的构建----------

/*构造AVL树*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct Node {
    int val, height;//height为节点的高度
    Node* left, *right;
    Node(int x):val(x),height(1),left(NULL),right(NULL){}
};

class AVLtree{
    //Node* treeRoot;
public:
    AVLtree() {};
    AVLtree(Node* &root,vector<int> &input);//构造函数
    /*Node* getRoot() {
        return treeRoot;
    }*/
    int getH(Node* &root) {//一开始直接node->left->height...debug了好
//久，这样会出现nullptr->height的情况...一般写树都是这种错误orz...要注意！！！
        if (!root)
            return 0;
        return root->height;
    }
    int getBalanceFactor(Node* node){
        return getH(node->left) - getH(node->right);
    };//获取平衡因子
    void updateHeight(Node* node) {
        node->height = max(getH(node->left), getH(node->right)) + 1;
    }
    void build(Node* &root, vector<int> &input);
    void insert(int v, Node* &node);
    void Rrotate(Node* &node);//右旋
    void Lrotate(Node* &node);//左旋
};
AVLtree::AVLtree(Node* &root,vector<int> &input) {
    build(root,input);
}
void AVLtree::Rrotate(Node* &node) {
    Node* tmp = node->left;
    node->left = tmp->right;
    tmp->right = node;
    updateHeight(tmp);//更新高度
    updateHeight(node);
    node = tmp;
}
void AVLtree::Lrotate(Node* &node) {
    Node* tmp = node->right;
    node->right = tmp->left;
    tmp->left = node;
    updateHeight(tmp);//更新高度
    updateHeight(node);
    node = tmp;
}
void AVLtree::insert(int v,Node* &node) {
    if (node == NULL) {
        node = new Node(v);
        return;
    }
    if (v < node->val) {//插入左子树
        insert(v, node->left);
        updateHeight(node);
        if (getBalanceFactor(node) == 2) {// LL or LR
            if (getBalanceFactor(node->left) == 1) {//LL 一次右旋
                Rrotate(node);
            }
            else if (getBalanceFactor(node->left) == -1) {// LR 先左旋再右旋
                Lrotate(node->left);
                Rrotate(node);
            }

        }

    }
    else {//插入右子树
        insert(v, node->right);
        updateHeight(node);
        if (getBalanceFactor(node) == -2) {// RL or RR
            if (getBalanceFactor(node->right) == -1) {//RR 一次左旋
                Lrotate(node);
            }
            else if (getBalanceFactor(node->right) == 1) {// RL 先右旋再左旋
                Rrotate(node->right);
                Lrotate(node);
            }

        }
    }
}
void AVLtree::build(Node* &root,vector<int> &input) {
    //Node* root = NULL;
    for (int i = 0; i < input.size(); i++) {
        insert(input[i],root);
    }
    //this->treeRoot = root;
}
int main()
{
    int n;
    cin >> n;
    vector<int> input(n);
    for (int j = 0; j < n; j++) {
        cin >> input[j];
    }
    Node* root = NULL;
    AVLtree avl(root,input);
    cout << root->val;
    return 0;
}

B树

• B-树
  定义：~是一种M叉搜索树：
  1.定义任意非叶子结点最多只有M个儿子；且M>2；
  2.根结点的儿子数为[2, M]；
  3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
  4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
  5.非叶子结点的关键字个数=指向儿子的指针个数-1；
  6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
  7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
  8.所有叶子结点位于同一层；
  应用场景：B-树主要应用在文件系统
  （为了将大型数据库文件存储在硬盘上 以减少访问硬盘次数为目的 在此提出了一种平衡多路查找树——B-树结构 ）
• B+树： B+树是应文件系统所需而产生的一种B-树的变形树
  应用场景：B+树在数据库索引中的应用
  （目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构）

红黑树

树的应用

• 最大最小堆
• Huffman树和编码
• 并查集运算