树的快速记忆

概念：

树是一种非线性结构，数据元素存在一对多的关系。

度数：一个节点的子节点的个数

二叉树：

每一个节点最多只能有两个直接后继，因此二叉树的度数小于等于2.

满二叉树：

除了叶节点意外，其他节点都有左右子树，深度为K的满二叉树有个节点。（注意：叶节点不在同一层的也不是满二叉树）

完全二叉树：

n个节点的二叉树按照层次进行编号，如果编号为i的节点与同样深度的满二叉树中的编号为i的节点，在同一个位置的。

树的存储：

    【1】顺序存储

             用数组存储，一般分配空间大小是，如果是右树的话，非常浪费空间，所以一般用来存储完成二叉树

    【2】链式存储

             typedef struct tree{

                  unsigned long data;

                  struct tree *l_child,*r_child;

             }tree_t;

 

树的创建：

【完全二叉树】n个节点的完全二叉树，按照层次进行编号，对于任意一个阶段i都有一下特点:

i = 1的节点为根节点

i > 1这该节点的父节点是i/2

2×i<=n,则节点i的左子节点为2×i，负责为页节点

2×i+1<=n,则节点i的右节点为2×i+1，负责节点i无右节点

【非完全二叉树】

树的遍历：

【先序遍历】根左右

void pre_order(tree_t *root)
{
    if(root == NULL){
        return ;
    }
    
    printf("访问根节点数据域");

    if(root->l_child != NULL){
        per_order(root->l_child);
    }

    if(root->r_child != NULL){
        per_order(root->r_child);
    }

    return ;
}

【中序遍历】左根右

void min_order(tree_t *root)
{
    if(root == NULL){
        return ;
    }

    if(root->l_child != NULL){
        min_order(root->l_child);
    }
    
    printf("访问根节点数据域");

    if(root->r_child != NULL){
        min_order(root->r_child);
    }

    return ;
}

【后续遍历】左右根

void after_order(tree_t *root)
{
    if(root == NULL){
        return ;
    }

    if(root->l_child != NULL){
        after_order(root->l_child);
    }
    
    if(root->r_child != NULL){
        after_order(root->r_child);
    }

    printf("访问根节点数据域");

    return ;
}

【层次遍历】按层次，从上到下，从左到右

int level_order(tree_t *root)
{
    queue_t *q = create_queue();    
    in_queue(q,root);

    while(!is_empty(q)){
        root = out_queue(q);
        
        printf("数据"，root->data);

        if(root->l_child != NULL){
            in_queue(q,root->l_child);
        }
        
        if(root->r_child != NULL){
            in_queue(q,root->r_child);
        }
    }
    
    return 0;
}