【数据结构】二叉树顺序存储结构实现

r囧r小猫 2021-09-21 08:18 557阅读 0赞

二叉树顺序结构的存储实现是用数组存储的，使用下标存储第i个节点。

二叉树的顺序存储结构非常适合存储满二叉树，这使得二叉树的存储占用最少。在数组中完全二叉树中没有双亲节点的值用0填充。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70]

**二叉树顺序存储结构实现**

/* * 二叉树的顺序存储结构使用数组存储 * 以节点编号存储在数组中, 例如节点1就存储在数组索引为1的存储单元中 * 对于完全二叉树, 按照层序存储即可 特点:适合存储满二叉树 */
    
    #include<iostream>
    
    #define MAX_SIZE 100
    #define OK 1
    #define ERROR 0
    using namespace std;
    
    typedef int Status;
    
    typedef int TElemType;
    
    typedef TElemType SqBiTree[MAX_SIZE];
    
    
    void initSQBiTree(SqBiTree &T) { 
        for (int i = 0; i < MAX_SIZE; i++) { 
            T[i] = 0;
        }
    }
    
    /* * 为第i个节点设置值 */
    Status setNode(SqBiTree &T, int i, TElemType e) { 
        if (T == NULL) return ERROR;
        if (i >= MAX_SIZE)return ERROR;
        T[i] = e;
        return OK;
    }
    
    /* * 为第i个节点的左孩子设置值 */
    Status setLeftChild(SqBiTree &T, int i, TElemType e) { 
        if (T == NULL)return ERROR;
        if (i * 2 >= MAX_SIZE)return ERROR;
        T[i * 2] = e;
        return OK;
    }
    
    
    /* * 为第i个节点的右孩子设置值 */
    Status setRightChild(SqBiTree &T, int i, TElemType e) { 
        if (T == NULL) return ERROR;
        if (i * 2 + 1 >= MAX_SIZE) return ERROR;
        T[i * 2 + 1] = e;
        return OK;
    }
    
    
    void printTree(SqBiTree T) { 
        for (int i = 1; i < MAX_SIZE; i++) { 
            cout << "第" << i << "个节点值为:" << T[i] << endl;
        }
    }
    
    
    int main() { 
        SqBiTree T;
        initSQBiTree(T);
    
        setNode(T,1,1);
        setLeftChild(T,1,2);
        setRightChild(T,1,4);
    
        setLeftChild(T,3,6);
        setRightChild(T,3,7);
    
        printTree(T);
    
        return 0;
    }

**测试的完全二叉树**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70 1]

--------------------

> **想了解作者更多，请移步我的个人网站，欢迎交流、留言~**  
> **极客技术空间：[https://elltor.com/][https_elltor.com]**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70]: /images/20210920/9d9799c6489643feacdb6adc74038ca4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70 1]: /images/20210920/c825cbd2b65b4308beb0aa2ec5e04163.png
[https_elltor.com]: https://elltor.com/