二叉查找树

2018-09-12 本文已影响0人漫游之光

树

树是n（n大于等于0）个节点的有限集，且这些节点满足以下关系：

有且仅有一个结点没有父节点，该结点称为树的根；
除根外，其余每个节点有且仅有一个父结点；
树的每个节点都构成以它为根的树。

树的表示，由于每个节点的儿子数可以变化很大而且事先不知道，所以一般树的表示方法是儿子-兄弟表示法。具体的结构体如下：

struct TreeNode{
    Type element;
    struct TreeNode* firstChild; //指向最左边的孩子
    struct TreeNode* nexrSibling; //指向右边的兄弟结点
};

二叉树

二叉树在满足树的条件的同时，满足以下条件：每个节点最多有两个子树，这两个子树有左右之分，次序不可颠倒。

二叉树的表示：二叉树可以用以下的结构体保存，用链表方式存储：

struct TreeNode{
    Type element;
    struct TreeNode* left;
    struct TreeNode* right;
};

也可以用数组存放，按从上至下、从左到右顺序存储n个结点的二叉树的结点父子关系。若起始结点的编号为1，则编号为i的结点的左孩子在2i，右孩子在2i+1。

二叉树的深度遍历

二叉树的深度遍历分为前序、中序和后序。这里的前中后指的是访问根节点的时机，如果一开始就访问根节点，称为前序；在中间访问称为中序；最后访问称为后序。具体的代码如下。

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x):val(x),left(NULL),right(NULL){}
};

void depthTraversal(TreeNode *node){
    if(node == NULL){
        return;
    }
    printf("%d ",node->val); //前序
    depthTraversal(node->left);
    // 此时访问node为中序
    depthTraversal(node->right);
    // 此时访问node为后序
}

二叉树的层次遍历

二叉树的层次遍历，就和图的广度优先搜索基本上是一个框架，所以这里直接给出代码。

void breadthTraversal(TreeNode *root){
    if(root == NULL){
        return;
    }
    queue<TreeNode *> q;
    q.push(root);
    while(!q.empty()){
        TreeNode *node = q.front();
        q.pop();
        printf("%d ",node->val);
        if(node->left != NULL){
            q.push(node->left);
        }
        if(node->right != NULL){
            q.push(node->right);
        }
    }
}

二叉树的序列化和反序列化

个人认为二叉树的序列化还是很有用的，主要的用途是在刷题的时候，遇到二叉树的题目时，能够迅速生成一颗二叉树进行测试。虽然像Letcode这种平台可以查看其测试的代码，但自己写的总还是要熟悉一点。

这里提供的方式是层次遍历的方式，因为这种方式比较直观，代码这里参考的是左程云《程序员代码面试指南》里面的代码，只不过使用的语言改为了C++。下面看具体的代码。

string serialize(TreeNode *root){
    if(root == NULL){
        return "# ";
    }
    queue<TreeNode *> q;
    q.push(root);
    string res = to_string(root->val) + " ";
    while(!q.empty()){
        TreeNode *node = q.front();
        q.pop();
        if(node->left != NULL){
            res += to_string(node->left->val) + " ";
            q.push(node->left);
        }else{
            res += "# ";
        }
        if(node->right != NULL){
            res += to_string(node->right->val) + " ";
            q.push(node->right);
        }else{
            res += "# ";
        }
    }
    return res;
}

TreeNode *getTreeNode(string s){
    if(s == "#"){
        return NULL;
    }
    return new TreeNode(stod(s));
}

TreeNode *deserialize(string data){
    istringstream iss(data);
    string s;
    vector<string> v;
    while(iss>>s){
        v.push_back(s);
    }
    int index = 0;
    TreeNode *root = getTreeNode(v[index++]);
    if(root == NULL){
        return root;
    }
    queue<TreeNode*> q; 
    q.push(root);
    while(!q.empty()){
        TreeNode *node = q.front();
        q.pop();
        node->left = getTreeNode(v[index++]);
        if(node->left != NULL){
            q.push(node->left);
        }
        node->right = getTreeNode(v[index++]);
        if(node->right != NULL){
            q.push(node->right);
        }
    }
    return root;
}