关于数据结构:二叉树

堆

1. 堆的概念

• 堆中某个结点的值总是不大于或不小于其父结点的值；
• 堆总是一棵齐全二叉树
• 堆能够存储在程序表中，假如父节点下标 x，则它的左右孩子下标别离为 2x+1、2x+2；若一个节点下标为 x，则它的父节点为（x-1)/2

2. 堆的实现

typedef int type;
typedef struct Heap
{
    type* a;
    int size;
    int capacity;
}Heap;

void heap_init(Heap* hp)
{assert(hp);
    hp->a = NULL;
    hp->size = hp->capacity = 0;
}
void heap_destroy(Heap* hp)
{assert(hp);
    free(hp->a);
    hp->a = NULL;
    hp->size = hp->capacity = 0;
}
// 这是小根堆的 up nlogn
void heap_small_up(type* a, int x)
{int parent = (x - 1) / 2;
    while (x > 0)
    {if (a[x] < a[parent])
        {heap_swap(&a[x], &a[parent]);
            x = parent;
            parent = (x - 1) / 2;
        }
        else
        {break;}                  
    }
}
// 这是大根堆的 up nlogn
void heap_big_up(type* a, int x)
{int parent = (x - 1) / 2;
    while (x > 0)
    {if (a[x] > a[parent])
        {heap_swap(&a[x], &a[parent]);
            x = parent;
            parent = (x - 1) / 2;
        }
        else
        {break;}                  
    }
}
void heap_push(Heap* hp, type x)
{assert(hp);
    if (hp->size == hp->capacity)
    {
        // 须要扩容
        int newcapa = (hp->capacity == 0) ? 4 : 2 * hp->capacity;
        type* t = (type*)realloc(hp->a,sizeof(type) * newcapa);
        if (t == NULL)
        {printf("realloc fail\n");
            exit(-1);
        }
        hp->a = t;
        hp->capacity = newcapa;
    }
    hp->a[hp->size] = x;
    ++hp->size;
    heap_up(hp->a, hp->size - 1);//nlogn
}
void heap_print(Heap* hp)
{assert(hp);
    for (int i = 0; i < hp->size; ++i)
    {printf("%d", hp->a[i]);
    }
    printf("\n");
}
void heap_swap(type* x, type* y)
{
    type t = *x;
    *x = *y;
    *y = t;
}
type heap_top(Heap* hp)
{assert(hp);
    assert(hp->size > 0);
    return hp->a[0];
}
void heap_pop(Heap* hp)// 删除 top 元素
{assert(hp);
    assert(hp->size > 0);
    heap_swap(&hp->a[0], &hp->a[hp->size - 1]);
    hp->size--;
    heap_down(hp->a,hp->size,0);//O(n)
}
bool is_empty(Heap* hp)
{assert(hp);
    return hp->size == 0;
}
int heap_size(Heap* hp)
{assert(hp);
    return hp->size;
}
// 小根堆的下沉 T = n
void heap_down(type* a,int size, int x)
{
    int child = 2 * x + 1;     
    while (child < size)
    {if (child+1<size&&a[child + 1] < a[child])
        {child++;}
        if (a[child] < a[x])
        {heap_swap(&a[child], &a[x]);
            x = child;
            child = 2 * x + 1;
        }
        else
        {break;}         
    }
}
// 大根堆的下沉 T = n
void heap_down(type* a,int size, int x)
{
    int child = 2 * x + 1;     
    while (child < size)
    {if (child+1<size&&a[child + 1] > a[child])
        {child++;}
        if (a[child] > a[x])
        {heap_swap(&a[child], &a[x]);
            x = child;
            child = 2 * x + 1;
        }
        else
        {break;}         
    }
}
void top_k(int *a, int k,int n)// 在 N 中找最大或者最小的前 k 个，N>>k
{
    //N100 亿，40G 内存能力放下
    
    //eg. 找最大的前 k 个，建设一个 k 的小堆
    // 步骤：1. 前 k 个数建设一个小堆；2. 剩下的 N - k 个数字外面，只有数字比堆顶要大，就进入堆；int *kmin = (int*)malloc(sizeof(int)*k);
    assert(kmin);
    for(int i=0;i<k;++i)
    {kmin[i] = a[i];
    }
    for(int i = (k-2)/2;i>=0;--i)
    {heap_small_down(kmin, k, i);
    }
    for(int j = k; k>n; ++k)
    {if(a[j]>kmin[0])
        {kmin[0] = a[j];
            heap_small_down(kmin, k, 0);
        }
    }
    
    
}
void heap_sort(type* a, int n)
{// 建堆 1.O(nlogn)
    for (int i = 1; i < n; ++i)
    {heap_small_up(a, i);
    }

    // 建堆 2.O(n)
    int i = (n - 2) / 2;// 最初一个结点的父亲，就是倒数第一个非叶子结点 
    for (; i >= 0; --i)
    {heap_small_down(a, n, i);
    }
    // 要排升序，如果建设小堆，每次取完头，须要再次建堆。如果每次都是建堆来选数据，那太慢了！(n*n) 没有应用到堆的劣势
    // 所以升序建设大堆, 降序建小堆,O(nlogn)
    int end = n - 1;
    while (end > 0)//nlogn
    {heap_swap(&a[0], &a[end]);
        heap_down(a, end, 0);
        --end;
    }
}

3. 链式存储的二叉树实现

typedef struct tree_node
{
    struct tree_node* l;
    struct tree_node* r;
    type data;
}node;
node* buy_node(type x)
{node* newnode = (node*)malloc(sizeof(node));
    assert(newnode);
    newnode->l = newnode->r = NULL;
    newnode->data = x;
    return newnode;
}
void pre_order(node* root)
{if (root == NULL)
    {printf("$");
        return;
    }
    printf("%d", root->data);
    pre_order(root->l);
    pre_order(root->r);
}
void in_order(node* root)
{if (root == NULL)
    {printf("$");
        return;
    }
    pre_order(root->l);
    printf("%d", root->data);
    pre_order(root->r);
}
void post_order(node* root)
{if (root == NULL)
    {printf("$");
        return;
    }
    pre_order(root->l);
    pre_order(root->r);
    printf("%d", root->data);
}
// 线程不平安
int count = 0;
void size1(node* root)
{if (root == NULL)
    {return;}
    count++;
    size1(root->l);
    size1(root->r);
}
int size2(node* root)
{if (root == NULL)
    {return 0;}
    return size2(root->l) + size2(root->r) + 1;
}
// 求一棵树有多少叶子
int count1 = 0;
int lead_size1(node* root)
{if (root == NULL)
        return;
    if (root->l == NULL && root->r == NULL)
        count1++;
    lead_size(root->l);
    lead_size(root->r);
}
int lead_size2(node* root)
{if (root == NULL)return 0; 
    if (root->l == NULL && root->r == NULL)
        return 1;
    return lead_size2(root->l) + lead_size2(root->r);
}
// 求第 k 层结点的个数
int k_num(node* root,int k)
{assert(k >= 1);
    if (root == NULL)return 0;
    if (k == 1)return 1;
    return k_num(root->l, k - 1) + k_num(root->r, k - 1);
}
// 求二叉树的深度
int deep(node* root)
{if (root == NULL)return 0;
    return deep(root->l) > deep(root->r) ? deep(root->l) + 1 : deep(root->r) + 1;
}
// 求值为 x 的结点
node* find(node* root, type x)
{if (root == NULL)
        return NULL;
    if (root->data == x)
        return root;
    node* ret1 = find(root->l, x);
    if (ret1)return ret1;
    node* ret2 = find(root->r, x);
    if (ret2)return ret2;
    return NULL;
}
// 二叉树的档次遍历
void bfs(node* root)
{
    queue<node*> q;
    if(root!=NULL)q.push(root);
    whlie(!q.empty)
    {node* t = q.top();
        q.pop();
        printf("%d", t->data);
        if (t->l != NULL)q.push(t->l);
        if (t->r != NULL)q.push(t->r);
    }
    printf("\n");
}
void destroy(node* root)
{
    // 应用后序遍历
    if (root == NULL)return;
    destroy(root->l);
    destroy(root->r);

    free(root);
}
// 判断一个二叉树是不是齐全二叉树
bool is()
{
    queue<node*> q;
    if (root != NULL)q.push(root);
    whlie(!q.empty())
    {node* t = q.top();
        q.pop();
        if (t)
        {q.push(t->l);
            q.push(t->r);
        }
        else
        {break;}
    }
    while (!q.empty())
    {node* t = q.top();
        q.pop();
        if (t)
        {q.destroy();
            return false;
        }             
    }
    q.destroy();
    return true;         
}

4. 链式存储的二叉树 oj

965. 单值二叉树 – 力扣（LeetCode）

// 办法一
bool f = true;
void pre_order(struct TreeNode* root, int val)
{if(root == NULL||f==false)return;
    if(root->val != val)
    {
        f = false;
        return;
    }
    pre_order(root->left, val);
    pre_order(root->right,val);
}
bool isUnivalTree(struct TreeNode* root){if(root==NULL)return true;
    f = true;
    pre_order(root,root->val);
    if(f)return true;
    return false;
} 
// 办法二
bool isUnivalTree(struct TreeNode* root){if(root==NULL)return true;
    if(root->left&&root->val != root->left->val)return false;
    if(root->right&&root->right->val!=root->val)return false;
    return isUnivalTree(root->left)&&isUnivalTree(root->right)    
}
     

100. 雷同的树 – 力扣（LeetCode）

bool isSameTree(struct TreeNode* p, struct TreeNode* q){if(p==NULL &&q==NULL)return true;
    if(p==NULL ||q==NULL)return false;
    if(p->val != q->val)return false;

    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

101. 对称二叉树 – 力扣（LeetCode）

bool is(struct TreeNode* p,struct TreeNode* q)
{if(p==NULL &&q==NULL)return true;
    if(p==NULL ||q==NULL)return false;
    if(p->val != q->val)return false;

    return is(p->left,q->right)&&is(p->right,q->left);
}
 
bool isSymmetric(struct TreeNode* root){if(root == NULL)return true;
    return is(root->left,root->right);
}

572. 另一棵树的子树 – 力扣（LeetCode）

bool issame(struct TreeNode* p, struct TreeNode* q){if(p==NULL &&q==NULL)return true;
    if(p==NULL ||q==NULL)return false;
    if(p->val != q->val)return false;

    return issame(p->left,q->left)&&issame(p->right,q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(root == NULL)return false;
    if(issame(root, subRoot))return true;
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

144. 二叉树的前序遍历 – 力扣（LeetCode）

vector<int>ans;
class Solution {
public:
    void pre_order(TreeNode* root)
    {if(root== NULL)return;
        ans.push_back(root->val);
        pre_order(root->left);
        pre_order(root->right);
    }
    vector<int> preorderTraversal(TreeNode* root) {ans.clear();
        pre_order(root);
        return ans;
    }
};

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

typedef char type;
typedef struct tree_node
{
    struct tree_node* l;
    struct tree_node* r;
    type data;
}node;
node* buy_node(type x)
{node* newnode = (node*)malloc(sizeof(node));
    assert(newnode);
    newnode->l = newnode->r = NULL;
    newnode->data = x;
    return newnode;
}
node*create(char*str, int*pi)
{if(str[*pi]=='#')
    {++(*pi);
        return NULL;
    }
    node* root = buy_node(str[(*pi)++]);
    root->l = create(str, pi);
    root->r = create(str, pi);

    return root;
}
void in_order(node*root)
{if(root==NULL)return;
    in_order(root->l);
    printf("%c",root->data);
    in_order(root->r);
}
int main() {char str[100];
    scanf("%s",str);
    int i = 0;
    node*root = create(str, &i);
    in_order(root);
    return 0;
}