树

一、简介

不再是顺序结构，而是递归结构

递归属性

一个树有N个节点就一定有N-1个链接

深度/高度

二、应用

1. 储存天然层级系统：磁盘系统

2. 组织数据，便于查找：二叉树

3. Trie树：储存字典，用于动态字符检查

4. 网络路由算法

三、二叉树

严格二叉树/完美二叉树/平衡二叉树

二叉树的操作时间大多和高度有关，所以我们希望二叉树尽量能向完美二叉树靠拢，这样高度能更低。

第 i 层最多可以有 2^i 个节点。整个树的最大节点数为 2^(i+1) -1。根所在层为 i=0 ，i也可以理解为高度。

3.1 链表实现

3.2 数组实现

3.3 二叉搜索树

right >root >=left

3.3.1 链表实现

#include<stdio.h>
#include<stdlib.h>

struct BstNode{
    int data;
    struct BstNode* left;
    struct BstNode* right;
};

struct BstNode* GetNewNode(int data){
    struct BstNode* newNode = (BstNode*)malloc(sizeof(struct BstNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
}

//插入函数
struct BstNode* Insert(struct BstNode* root,int data){
    if(root==NULL){
        root = GetNewNode(data);
    }
    else if(data <= root->data){
        root->left = Insert(root->left,data);
    }
    else{
        root->right = Insert(root->right,data);
    }
    return root;
}

int main(){
    struct BstNode* root=NULL;
    root = Insert(root,15);
    root = Insert(root,10);
    root = Insert(root,20);
    root = Insert(root,25);
    root = Insert(root,8);
    root = Insert(root,12);

    return 0;
}

3.3.2 搜索函数

//搜索函数
bool Search(BstNode* root,int data){
    if(root == NULL) return false;
    else if(root->data == data) return true;
    else if(data < root->data) return Search(root->left,data);
    else return Search(root->right,data);
}

3.3.3 查找最大最小值函数

//循环实现
int FindMin(BstNode* root){
    if(root == NULL){
        printf("Error\n");
        return -1;
    }
    while(root->left != NULL){
        root = root->left;
    }
    return root->data;
}
int FindMax(BstNode* root){
    if(root == NULL){
        printf("Error\n");
        return -1;
    }
    while(root->right != NULL){
        root = root->right;
    }
    return root->data;
}

//递归实现
int Min(BstNode* root){
    if(root == NULL){
        printf("Error\n");
        return -1;
    }else if(root->left == NULL){
        return root->data;
    }
    return Min(root->left);
}
int Max(BstNode* root){
    if(root == NULL){
        printf("Error\n");
        return -1;
    }else if(root->right == NULL){
        return root->data;
    }
    return Max(root->right);
}

3.3.4 计算二叉树的高度

int FindHeight(BstNode *root){
    //退出递归的条件
     if(root == NULL) return -1;
    //节点的高度为：左树和右树中，更高的高度+1
     return max(FindHeight(root->left),FindHeight(root->right))+1;
}

3.3.5 树的遍历

//广度优先
void LevelOrder(BstNode *root){
    if(root == NULL) return;
    //create a queue
    EnQueue(root);
    while(!IsEmpty()){
        struct BstNode* current = DeQueue();
        printf("%d\n",current->data);
        if(current->left != NULL){
            EnQueue(current->left);
        }
        if(current->right != NULL){  
            EnQueue(current->right);
        }
    }
}

//深度优先(前序，中序，后序三种顺序)
void Preorder(struct BstNode* root){
    if(root == NULL) return;
    printf("%d\n",root->data);
    Preorder(root->left);
    Preorder(root->right);
}

void Inorder(struct BstNode* root){
    if(root == NULL) return;
    Preorder(root->left);
    printf("%d\n",root->data);    
    Preorder(root->right);
}

void Postorder(struct BstNode* root){
    if(root == NULL) return;
    Preorder(root->left);
    Preorder(root->right);
    printf("%d\n",root->data);    
}