【数据结构】树、二叉树与堆（长期维护）（2）-阿里云开发者社区

(三)、分析堆

1.向下调整算法建堆的时间复杂度分析

void AdjustDown(int* a, int size, int parent)
{
  int child = parent * 2 + 1;
  while (child < size)//思考1：while的结束条件是什么？
  {
    // 假设左孩子小，如果解设错了，更新一下
    if (child + 1 < size && a[child + 1] < a[child])//思考2：if中“child + 1 < size”的意义是什么？
    {
      ++child;
    }
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

结论：

向下调整算法时间复杂度为O(logN)

向下调整算法建堆的时间复杂度是多少？O(N)

2.向上调整算法建堆的时间复杂度分析

//小堆
void AdjustUp(HPDataType* a, int child)
{
  assert(a);
  int parent = (child - 1) / 2;
  while (child > 0) //思考：请思考while括号内的结束条件是什么？
  {                 //提示选项如下：1.parent>=0 2.child>=0 3.child>0          
    if (a[child] < a[parent])
    {
      Swap(&a[child], &a[parent]);
      child = parent;
      parent = (parent - 1) / 2;
    }
    else
    {
      break;
    }
  }
}

结论：

向上调整算法的时间复杂度为O(logN)

向上调整算法建堆的时间复杂度为：O(N * log(N))

思考：向上调整算法与向下调整算法同为调整算法，且时间复杂度都为O(logN),为什么向下调整算法建堆的时间复杂度为O(N)，而向上调整算法却到达了O(N*logN)?

答：

说的简单一点，对于单个结点的向上调整/向下调整，都大概最差要调整高度次，也就是差不多是logN，但是对于一整个堆而言，这个堆中如果用向上调整算法，第一行不需要调整，如果用向下调整算法，最后一行不需要调整，而往往在N足够大的情况下，最后一行的结点个数占百分之50左右。

3.堆排序的时间复杂度分析

堆排序有两部分组成，第一步是建堆，第二是首尾交换，尾不视为堆内，对N-1个数据向下调整算法重新成为堆。

在第一步，可以使用向上/向下调整算法建堆，肯定是选择向下调整算法建堆。时间复杂度上面经过分析为O(N)

在第二步，时间复杂度为O(N*logN)

代码如下：

void HeapSort(int* a, int n)
{
  // a数组直接建堆 O(N)
  for (int i = (n - 1 - 1) / 2; i >= 0; --i)
  {
    AdjustDown(a, n, i);
  }
  int end = n - 1;
  while (end > 0)//思考：while的结束条件是什么？
  {
    Swap(&a[0], &a[end]);
    AdjustDown(a, end, 0);
    --end;
  }
}

综上，堆排的时间复杂度为O(N*logN)

结论：堆排的时间复杂度为O(N*logN)

(四)、一般的二叉树

上面所说的堆是特殊的二叉树+满足大堆小堆的条件才可以称为堆，下面来简单说一下对于一般二叉树的常规知识点。

每棵树都可以分为根、左子树、右子树，其中左子树又可以分为根、左子树、右子树…二叉树也不例外。

同时，因为一般二叉树放入顺序结构中比较浪费空间，一般选用链式结构来构造一般的二叉树。

1.一般二叉树的遍历

二叉树的遍历可以分为前序遍历、中序遍历、后序遍历。

二叉树的前序遍历(根、左子树、右子树)：
前序遍历本质上是深度优先遍历

void PreOrder(Tree* root)
{
  if (root == NULL)
  {
    printf("N ");
    return;
  }
  printf("%d ", root->val);
  PreOrder(root->left);
  PreOrder(root->right);
}

拓展练习题：二叉树的前序遍历LINK

示例代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 int TreeSize(struct TreeNode* root)
 {
    if(root == NULL)
    {
        return 0;
    }
    return TreeSize(root->left) + TreeSize(root->right) + 1;
 }
void PreOrder(struct TreeNode* root,int* arr,int* pi)
{
    if(root == NULL)
    return;
    arr[(*pi)++] = root->val;//思考，这个小括号是否可以省略？
    PreOrder(root->left,arr,pi);
    PreOrder(root->right,arr,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    
    int n = *returnSize = TreeSize(root);
    int* arr = (int*)malloc(sizeof(int) * n);
    int i = 0;//思考：这里为什么要传地址
    PreOrder(root,arr,&i);
    return arr;
}

思考1：这个小括号是否可以省略？

不能，语法优先级问题。

思考2：这里为什么要传地址？

使用递归，要改变一个固定空间的i值，要传入地址或者搞一个全局变量。

二叉树的中序遍历(左子树、根、右子树)

void InOrder(Tree* root)
{
  if (root == NULL)
  {
    printf("N ");
    return;
  }
  InOrder(root->left);
  printf("%d ", root->val);
  InOrder(root->right);
}

拓展练习题：二叉树的中序遍历LINK

二叉树的后序遍历(左子树、右子树、根)

void PostOrder(Tree* root)
{
  if (root == NULL)
  {
    printf("N ");
    return;
  }
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->val);
}

拓展练习题：二叉树的后序遍历LINK

2.树的节点个数接口

思想1：分置思路

int TreeSize(Tree* root)
{
  if (root == NULL)
  {
    return 0;
  }
  
  return TreeSize(root->left) + TreeSize(root->left) + 1;
}

int TreeSize(Tree* root)
{
  return root == NULL ? 0 :TreeSize(root->left) + TreeSize(root->right) + 1;
}

size统计思路

//思考：如果用size进行统计结点个数，要定义为局部变量/全局变量/全局变量/指针变量？？？
//局部变量，否定，统计结果永远为0/1
//全局变量，可以，需要每次调用需要置为空size
//局部静态变量，否定，不能置空操作，多次调用之后会出问题
//指针变量：可以，每次也都需要置空

思考：size统计思路各种处理size方法的利弊。

如果用size进行统计结点个数，要定义为局部变量/全局变量/全局变量/指针变量？？？

//局部变量，否定，统计结果永远为0/1

//全局变量，可以，需要每次调用需要置为空size

//局部静态变量，否定，不能置空操作，多次调用之后会出问题

//指针变量：可以，每次也都需要置空

代码技巧：要想写好递归，需要控制好两个条件，

子问题

结束条件(返回条件)

对于本接口，那么需要把握好下面两个条件：

子问题：一棵树的结点个数 = 左子树结点个数 + 右子树结点个数 + 1

结束条件：NULL，返回0

拓展1：实现一棵树叶子结点个数：自己思考，参考代码如下

int TreeLeafSize(Tree* root)
{
  if (root == NULL)
  {
    return 0;
  }
  if (root->right == NULL && root->left == NULL)
  {
    return 1;
  }
  return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

拓展2：求树的第K层结点个数，参考代码如下：

int TreeSize_K(Tree* root,int k)
{
  if (root == NULL || k < 1)
  {
    return 0;
  }
  if (k == 1)
  {
    return 1;
  }
  return TreeSize_K(root->left, k - 1) + TreeSize_K(root->right, k - 1);
}

3.树的高度接口

思路：这里要求树的高度，那么就是对于一个子树的高度就是左子树的高度，右子树的高度取其大的进行返回 +1(这个1是指自己) 。

int TreeHeight(Tree* root)
{
  if (root == NULL)
  {
    return 0;
  }
  int leftheight = TreeHeight(root->left);//思考：这里为啥不直接返回而是用变量记录的意义。
  int rightheight = TreeHeight(root->right);
  return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
}

思考：这里为啥不直接返回而是用变量记录的意义

其意义在于，防止重复调用，这里其实就是一个不断多次重复的问题。

int TreeHeight(Tree* root)
{
  return root == NULL ? 0 : (TreeHeight(root->left) > TreeHeight(root->right) ? >TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1);
}

这样第一次多调用一次，那么第二层要多调用2^1 第三层要多调用2^2次第四层要多调用2^3次…

4.树的查找接口

Tree* TreeFind(Tree* root, int x)
{
  if (root == NULL)
  {
    return NULL;
  }
  if (root->val == x)
  {
    return root;
  }
  Tree* left = TreeFind(root->left,x);
  if (left)
  {
    return left;
  }
  Tree* right = TreeFind(root->right,x);
  if (right)//思考，这里为什么要加这个if条件
  {
    return right;
  }
  return NULL;
}

思考：至于为什么要加上if，防止空指针也被返回，如果没有if可能会提前返回出问题。

就是左子树返回后，会直接返回到上一级函数，没有机会执行右子树了。

拓展练习题：单值二叉树

LINK

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isUnivalTree(struct TreeNode* root) {
    if(root == NULL)//如果走到空结点，直接返回true
    {
        return true;
    }
    if(root->left && root->val!=root->left->val)
    {
        return false;
    }
    if(root->right && root->val!=root->right->val)
    {
        return false;
    }
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

拓展练习题2：对称二叉树LINK

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 bool _isSymme(struct TreeNode* q,struct TreeNode* p)
 {
    if(q == NULL && p == NULL)
    {
        return true;
    }
    if(q == NULL || p == NULL)
    {
        return false;
    }
    if(q->val != p->val)
    {
        return false;
    }
    return _isSymme(q->left,p->right) && _isSymme(q->right,p->left);
 }
bool isSymmetric(struct TreeNode* root) {
    return _isSymme(root,root);
}

拓展练习题：另一颗树的子树LINK

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* root, struct TreeNode* subRoot) {
    if(root == NULL && subRoot == NULL)
    {
        return true;
    }
    if(root == NULL || subRoot == NULL)
    {
        return false;
    }
    if(root->val != subRoot->val)
    {
        return false;
    }
    return isSameTree(root->left,subRoot->left) && isSameTree(root->right,subRoot->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if (root == NULL) {
        return false;
    }
    if (root->val == subRoot->val) {
        if(isSameTree(root, subRoot) == true)//思考：这里if的意义在哪里？
        {
            return true;
        }
    }
    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

思考：上面if返回的意义在于，要把整个树的每一个结点都比较一遍，防止特殊情况出现。

比如：

5.树的构建接口

Tree* TreeCreat(char* a, int* pi)
{
  if (a[*pi] == '#')
  {
    (*pi)++;
    return NULL;
  }
  Tree* root = (Tree*)malloc(sizeof(Tree));
  if (root == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  root->val = a[(*pi)++];
  root->left = TreeCreat(a, pi);
  root->right = TreeCreat(a, pi);
  return root;
}

test_TreeCreat()
{
  char* a = "abc##de#g##f###";
  int i = 0;
  Tree* root = TreeCreat(a, &i);
  PreOrder(root);
}
int main()
{
  //test_heap();
  //test_TopK();
  //test_HeapSort();
  //test_GenBTree();
  test_TreeCreat();
  return 0;
}

6.层序遍历接口

本质上是广度优先遍历

思路：

void TreeLevelOrder(Tree* root)
{
  Queue q;
  QueueInit(&q);
  if (root != NULL)
  {
    QueuePush(&q,root);
  }
  while (!QueueEmpty(&q))
  {
    Tree* front = QueueFront(&q);
    QueuePop(&q);
    printf("%d ", front->val);
    if (root->left != NULL)
    {
      QueuePush(&q, root->left);
    }
    if (root->right != NULL)
    {
      QueuePush(&q, root->right);
    }
  }
  printf("\n");
  QueueDestroy(&q);
}

7.树的销毁

oid TreeDestroy(Tree* root)
{
  if (root == NULL)
  {
    return;
  }
  TreeDestroy(root->left);
  TreeDestroy(root->right);
  free(root);
}

待续。

【数据结构】树、二叉树与堆（长期维护）（2）