【数据结构与算法篇】深入浅出——二叉树（详解）

struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 int _data; // 结点中的数据域
};

typedef int HPdataType;
typedef struct Heap
{
  HPdataType* arr; //动态数组
  int size; //有效元素个数
  int capacity; //数组容量
}Heap;

//向上调整
void AdjustUp(HPdataType* a,int child)
{
  //根据孩子找父亲
  int parent = (child - 1) / 2;
  //孩子下标小于等于0就结束
  while (child > 0)
  {
    //小堆情况下  孩子小于父亲就交换
    if (a[child] < a[parent])
    {
      HPdataType tmp = a[child];
      a[child] = a[parent];
      a[parent] = tmp;
      //更新节点，继续往上迭代找
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      //孩子大于等于父亲就结束循环
      break;
    }
  }
}
//堆的插入
void HeapPush(Heap* php, HPdataType x)
{
  assert(php);
  if (php->capacity == php->size)
  {
    int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
    HPdataType* a = (HPdataType*)realloc(php->arr,sizeof(HPdataType)* newcapacity);
    if (a == NULL)
    {
      perror("malloc fail");
      return;
    }
    php->arr = a;
    php->capacity = newcapacity;
  }
  php->arr[php->size] = x;
  php->size++;
  //为了保证堆的性质，需要进行向上调整
  AdjustUp(php->arr,php->size - 1);
}

//向下调整
void AdjustDown(int* a,int n,int parent)
{
   //根据父亲找孩子
  int child = parent * 2 + 1;//假设左孩子最小
  while (child < n)
  {
    //小堆情况下  
    //如果右孩子存在的情况下必须保证小于n
    if (child + 1 < n && a[child + 1] < a[child])
    {
      //如果右孩子小于左孩子
      //那么就把下标位置给到右孩子
      child++;
    }
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      //继续往下迭代走
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      //孩子大于父亲，符合小堆性质，跳出循环
      break;
    }
  }
}
//堆的删除操作
void HeapPop(Heap* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  //首尾元素交换
  Swap(&php->arr[0], &php->arr[php->size - 1]);
  php->size--;
  AdjustDown(php->arr, php->size, 0);
}

//创造数据
void CreateDate()
{
  int n = 10000;
  srand(time(NULL));
  FILE* fin = fopen("data.txt", "w");
  if (fin == NULL)
  {
    perror("fopen error");
    return;
  }
  int i = 0;
  for (i = 0; i < n; i++)
  {
    fprintf(fin, "%d\n", rand() % 1000);
  }
  fclose(fin);
}
void PrintTopK(int k)
{
  FILE* fout = fopen("data.txt", "r");
  if (fout == NULL)
  {
    perror("fopen error");
    return;
  }
  int* kminheap = (int)malloc(sizeof(int) * k);
  if (kminheap == NULL)
  {
    perror("malloc fail\n");
    return;
  }
  //读取前k个数到数组中
  for (int i = 0; i < k; i++)
  {
    fscanf(fout, "%d", &kminheap[i]);
  }
  //前k个数建立小堆
  for (int i = (k - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(kminheap, k, i);
  }
  //剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素(覆盖)
  int val = 0;
  while (!feof(fout))
  {
    fscanf(fout, "%d", &val);
    if (val > kminheap[0])
    {
      kminheap[0] = val;
      //向下调整
      AdjustDown(kminheap, k, 0);
    }
  }
  //打印剩余K个元素就是最大值
  for (int i = 0; i < k; i++)
  {
    printf("%d ", kminheap[i]);
  }
}
int main()
{
  //CreateDate();
  PrintTopK(5);
}

//向上调整
void AdjustUp(HPdataType* a, int child)
{
  //根据孩子找父亲
  int parent = (child - 1) / 2;
  //孩子下标小于等于0就结束
  while (child > 0)
  {
    //小堆情况下  孩子小于父亲就交换
    if (a[child] < a[parent])
    {
      HPdataType tmp = a[child];
      a[child] = a[parent];
      a[parent] = tmp;
      //更新节点，继续往上迭代找
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      //孩子大于等于父亲就结束循环
      break;
    }
  }
}
//向下调整
void AdjustDown(int* a,int n,int parent)
{
   //根据父亲找孩子
  int child = parent * 2 + 1;//假设左孩子最小
  while (child < n)
  {
    //小堆情况下  
    //如果右孩子存在的情况下必须保证小于n
    if (child + 1 < n && a[child + 1] < a[child])
    {
      //如果右孩子小于左孩子
      //那么就把下标位置给到右孩子
      child++;
    }
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      //继续往下迭代走
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      //孩子大于父亲，符合小堆性质，跳出循环
      break;
    }
  }
}
//交换
void Swap(HPdataType* p1, HPdataType* p2)
{
  HPdataType tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
void heapSort(int* a, int n)
{
  //法一：向上调整建堆(可以想象堆插入的过程，调整前元素前面已经满足堆的性质)
  /*for(int i = 1;i < n;i++)
  {
    AdjustUp(a, i);
  }*/
  //法二：向下调整建堆(从最后一个叶子节点的父亲开始倒着调整,因为叶子节点本来就可以看成堆)
  //O(N)
  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
  {
    AdjustDown(a, n, i);
  }
  //首尾交换再向下调整
  //O(N*logN)
  int end = n - 1;
  while(end > 0)
  {
    Swap(&a[0], &a[end]);
    AdjustDown(a, end, 0);
    end--;
  }
}
int main()
{
  int a[] = {8,40,91,14,39,72,4,81};
  heapSort(a, sizeof(a) / sizeof(int));
}

typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
  BTNode* node = (BTNode*)malloc(sizeof(BTNode));
  if (node == NULL)
  {
    perror("malloc fail\n");
    return NULL;
  }
  node->data = x;
  node->left = NULL;
  node->right = NULL;
  return node;
}
BTNode* CreatBinaryTree()
{
  BTNode* node1 = BuyNode(1);
  BTNode* node2 = BuyNode(2);
  BTNode* node3 = BuyNode(3);
  BTNode* node4 = BuyNode(4);
  BTNode* node5 = BuyNode(5);
  BTNode* node6 = BuyNode(6);
  node1->left = node2;
  node1->right = node4;
  node2->left = node3;
  node4->left = node5;
  node4->right = node6;
  return node1;
}

//前序遍历
void PrevOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("N ");
    return;
  }
  printf("%d ", root->data);
  PrevOrder(root->left);
  PrevOrder(root->right);
}
int main()
{
  BTNode* root = CreatBinaryTree();
  PrevOrder(root);
}

//中序遍历
void InOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("N ");
    return;
  }
  InOrder(root->left);
  printf("%d ", root->data);
  InOrder(root->right);
}
int main()
{
  BTNode* root = CreatBinaryTree();
  InOrder(root);
}

//后序遍历 
void PostOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("N ");
    return;
  }
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->data);
}
int main()
{
  BTNode* root = CreatBinaryTree();
  PostOrder(root);
}

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//链式队列
typedef struct BinaryTreeNode* QDataType;
//每个节点
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QueueNode;
//整个队列的结构
typedef struct Queue
{
  QueueNode* phead;//记录链表头
  QueueNode* ptail;//记录链表尾
  int size;//队列的大小
}Queue;
//队列的初始化
void QueueInit(Queue* pqe);
//队列的销毁
void QueueDestroy(Queue* pqe);
//队尾入队列
void QueuePush(Queue* pqe, QDataType x);
//队头出队列
void QueuePop(Queue* pqe);
//获取队头的数据
QDataType QueueFront(Queue* pqe);
//获取队尾的数据
QDataType QueueBack(Queue* pqe);
//获取队列中有效数据个数
int QueueSize(Queue* pqe);
//判断队列是否为空
bool QueueEmpty(Queue* pqe);

#include"Queue.h"
//队列的初始化
void QueueInit(Queue* pqe)
{
  assert(pqe);
  pqe->phead = pqe->ptail =  NULL;
  pqe->size = 0;
}
//队列的销毁
void QueueDestroy(Queue* pqe)
{
  assert(pqe);
  QueueNode* cur = pqe->phead;
  while (cur)
  {
    QueueNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pqe->phead = pqe->ptail = NULL;
  pqe->size = 0;
}
//队尾入队列
void QueuePush(Queue* pqe, QDataType x)
{
  assert(pqe);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  if (newnode == NULL)
  {
    perror("malloc fail\n");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
  //分为空节点和非空节点
  if (pqe->phead == NULL)
  {
    //ptial为断言，为了避免phead与ptail同时指向NULL
    assert(pqe->ptail == NULL);
    pqe->phead = pqe->ptail = newnode;
  }
  else
  {
    pqe->ptail->next = newnode;
      pqe->ptail = newnode;
  }
  pqe->size++;
}
//队头出队列
void QueuePop(Queue* pqe)
{
  assert(pqe);
  assert(!QueueEmpty(pqe));
  //分为一个节点和多个节点
  if (pqe->phead->next == NULL)
  {
    free(pqe->phead);
    pqe->phead = pqe->ptail = NULL;
  }
  else
  {
    QueueNode* next = pqe->phead->next;
    free(pqe->phead);
    pqe->phead = next;
  }
  pqe->size--;
}
//获取队头的数据
QDataType QueueFront(Queue* pqe)
{
  assert(pqe);
  assert(!QueueEmpty(pqe));
  return pqe->phead->data;
}
//获取队尾的数据
QDataType QueueBack(Queue* pqe)
{
  assert(pqe);
  assert(!QueueEmpty(pqe));
  return pqe->ptail->data;
}
//获取队列中有效数据个数
int QueueSize(Queue* pqe)
{
  assert(pqe);
  return pqe->size;
}
//判断队列是否为空
bool QueueEmpty(Queue* pqe)
{
  assert(pqe);
  //return pqe->phead == NULL && pqe->ptail == NULL;
  return pqe->size == 0;
}

#include "Queue.h"
// 层序遍历
void LevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  //根节点入队列
  if (root != NULL)
    QueuePush(&q, root);
  //队列不为空
  while (!QueueEmpty(&q))
  {
    //输出队头的元素
    BTNode* front = QueueFront(&q);
    printf("%d ", front->data);
    QueuePop(&q);
    //左孩子和右孩子都存在，就入队列
    if (front->left != NULL)
      QueuePush(&q, front->left);
    if (front->right != NULL)
      QueuePush(&q, front->right);
  }
  QueueDestroy(&q);
}

// 判断二叉树是否是完全二叉树(层序遍历思想)
bool BinaryTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root == NULL)
    QueuePush(&q, root);
  //队列不为空
  while (!QueueEmpty(&q))
  {
    //节点入队列
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    //遇到空树就跳出循环
    if (front == NULL)
      break;
    //左右子树入队列
    QueuePush(&q, front->left);
    QueuePush(&q, front->right);
  }
  //继续往后寻找，只要遇到非空说明不是完全二叉树 返回false
  //空树后面还是空说明是完全二叉树返回true
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front != NULL)
    {
      QueueDestroy(&q);
      return false;
    }
    QueuePush(&q, front->left);
    QueuePush(&q, front->right);
  }
  QueueDestroy(&q);
  return true;
}

// 二叉树节点个数
//法一：遍历计数(使用完后需要将size置为0)
//int size = 0;
//void BinaryTreeSize(BTNode* root)
//{
//  if (root == NULL)
//    return;
//  size++;
//
//  BinaryTreeSize(root->left);
//  BinaryTreeSize(root->right);
//}
//法二：分治算法
int  BinaryTreeSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  if (root->left == NULL && root->right == NULL)
    return 1;
  return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

//二叉树的高度
int BinaryTreeHeight(BTNode* root)
{
  if (root == NULL)
    return 0;
  int leftHeight = BinaryTreeHeight(root->left);
  int RightHeight = BinaryTreeHeight(root->right);
  return leftHeight > RightHeight ? leftHeight + 1 : RightHeight + 1;
}

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
  //层数都是从1开始
  assert(k > 0);
  //root 为空返回0
  if (root == NULL)
    return 0;
  //root为空且k = 1时，返回1
  if (k == 1)
    return 1;
  //分治：左子树和右子树
  return BinaryTreeLevelKSize(root->left, k - 1)
    + BinaryTreeLevelKSize(root->right, k - 1);
}

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{ 
  if (root == NULL)
    return NULL;
  if (root->data == x)
    return root;
  //分治
  BTNode* ret1 = BinaryTreeFind(root->left, x);
  if (ret1)
    return ret1;
  BTNode* ret2 = BinaryTreeFind(root->right, x);
  if (ret2)
    return ret2;
  //子树都没找到返回空 
  return NULL;
}

#include <stdio.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
  BTNode* node = (BTNode*)malloc(sizeof(BTNode));
  if (node == NULL)
  {
    perror("malloc fail\n");
    return NULL;
  }
  node->data = x;
  node->left = NULL;
  node->right = NULL;
  return node;
}
//构建树（前序遍历）
BTNode* CreateTree(char* a,int* pi)
{
    if(a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root = BuyNode(a[*pi]);
        (*pi)++;
    root->left =  CreateTree(a,pi);
    root->right =  CreateTree(a,pi);
    return root;
}
//中序遍历输出
void InOrder(BTNode* root)
{
    if(root == NULL)
        return;
    InOrder(root->left);
    printf("%c ",root->data);
    InOrder(root->right);
}
int main() {
    char str[100];
    scanf("%s",str);
    int i = 0;
    BTNode* root = CreateTree(str,&i);
    InOrder(root);
    printf("\n");
    return 0;
}