一. 初识二叉树

1.1 树的定义

树是一种递归的数据结构，作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点

1. 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱
2. 树中所有结点可以有零个或多个后继

树中一个结点的孩子个数称为该结点的度

树的高度（或深度）是树中结点的最大层数

1. 结点的深度是从根节点开始自顶向下逐层累加的
2. 结点的高度是从叶节点开始自底向上逐层累加的

1.2 二叉树

二叉树是一种树形结构，其特点是每个结点至多只有两颗子树，并且二叉树的子树有左右之分，其次序不能任意颠倒

1.3 满二叉树

如果一棵二叉树只有度为 0 的结点和度为 2 的结点，并且度为 0 的结点在同一层上，则这棵二叉树为满二叉树

可以对满二叉树按层序编号：约定编号从根结点（根结点编号为 1），自上而下，自左向右。这样，每个结点对应一个编号，对于编号为 i 的结点，若有双亲，则其双亲为 “向下取整(i / 2)"，若有左孩子，则左孩子为 2i；若有右孩子，则右孩子为 2i+1

1.4 完全二叉树

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1)  个节点

1.5 二叉树的顺序存储结构

可以使用数组来存储二叉树，从索引 1 开始存储，对孩子结点和父节点的访问参考满二叉树的按层序编号

1.6 二叉树的链式存储结构

在二叉树中，链表结点至少包含 3 个域：数据域 data、左指针域 lchild、右指针域 rchild

class TreeNode{
public:
    int data;
    TreeNode *lchild;
    TreeNode *rchild;

public:
    explicit TreeNode(int data, TreeNode *lchild = nullptr, TreeNode *rchild = nullptr)
    :data(data), lchild(lchild), rchild(rchild){}
};

1.7由顺序存储转化为链式存储

class Tree{
private:
    TreeNode *root;
    std::vector<TreeNode *> tree_nodes;

public:
    Tree()
    :root(nullptr){}

    Tree(const std::vector<int> &data, const std::vector<int> &index){
        this->tree_nodes.emplace_back(nullptr);
        int j = 0;
        for(int i = 1; i < index.size(); ++i){
            TreeNode *tree_node = nullptr;
            if(index[i] == 1)
                tree_node = new TreeNode(data[j++]);
            this->tree_nodes.emplace_back(tree_node);
            if(i == 1)
                this->root = tree_node;
        }

        for(int i = 1; i * 2  < index.size(); ++i){
            if(this->tree_nodes[i] != nullptr){
                this->tree_nodes[i]->lchild = this->tree_nodes[2 * i];
                if(i * 2 + 1 < index.size())
                    this->tree_nodes[i]->rchild = this->tree_nodes[2 * i + 1];
            }
        }
    }

    ~Tree(){
        for(int i = 1; i < this->tree_nodes.size(); ++i){
            if(this->tree_nodes[i] != nullptr)
                delete this->tree_nodes[i];
        }
    }

    Tree(const Tree &) = delete;
    Tree &operator=(const Tree &) = delete;

public:
    TreeNode *getRoot(void) const{
        return this->root;
    }

    void show(void) const{
         auto inner = [](const auto &func, TreeNode *root, int depth = 1) -> void{
            if(root != nullptr){
                printf("%s%d\n", std::string(depth, '-').c_str(), root->data);
                func(func, root->lchild, depth+3);
                func(func, root->rchild, depth+3);
            }else
                printf("%s%s\n", std::string(depth, '-').c_str(), "NULL");  
        };
        inner(inner, this->root);
    }
};

int main(void){
    std::vector<int> data = {1, 2, 3, 4, 5, 6, 7};
    std::vector<int> index = {0, 1, 1, 1, 1, 1, 1, 1};
    Tree tree(data, index);
    tree.show();
    return 0;
}