AI 助理
备案控制台
开发者社区 人工智能 文章 正文

链式二叉树的基本操作和相关OJ题训练（建议收藏！！！）（3）

2023-11-15 39
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 链式二叉树的基本操作和相关OJ题训练（建议收藏！！！）

代码解决：

咱们还可以不修改输入树的结构，使用前序遍历，代码如下：

struct TreeNode* mergeTrees(struct TreeNode* t1, struct TreeNode* t2) 
{
        if (t1 == NULL) 
             return t2;
        if (t2 == NULL) 
           return t1;
        // 重新定义新的节点，不修改原有两个树的结构
        struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        root->val = t1->val + t2->val;
        root->left = mergeTrees(t1->left, t2->left);
        root->right = mergeTrees(t1->right, t2->right);
        return root;
}

测试结果：

最大二叉树

题目来源：Leetcode654.最大二叉树

题目描述：

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。

1.递归地在最大值 左边 的 子数组前缀上 构建左子树。

2.递归地在最大值 右边 的 子数组后缀上 构建右子树。

3.返回 nums 构建的 最大二叉树 。

解题思路：

1、以左闭右开为区间递归构造二叉树，区间内至少得有一个元素，

若left >= right则表示无节点，需返回NULL

2、找到当前区间中最大的元素，记录下标maxValueIndex

3、以[left, maxIndex) 和 [maxIndex + 1, right)为区间构造左右子树

代码解决：

struct TreeNode* traversal(int* nums, int left, int right) 
{
    //若左边界大于右边界，返回NULL
    if(left >= right)
        return NULL;
    //找出数组中最大数坐标
    int maxIndex = left;
    int i;
    for(i = left + 1; i < right; i++) 
    {
        if(nums[i] > nums[maxIndex])
            maxIndex = i;
    }
    //开辟结点
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    //将结点的值设为最大数组数组元素
    node->val = nums[maxIndex];
    node->left=NULL;
    node->right=NULL;
    //递归定义左孩子结点和右孩子结点
    node->left = traversal(nums, left, maxIndex);
    node->right = traversal(nums, maxIndex + 1, right);
    return node;
}
struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize)
{
    return traversal(nums, 0, numsSize);
}

总结：

费尽千辛万苦，咱们链式二叉树已经圆满结束了，希望本篇文章能对你有所帮助。

以下是测试所用的代码：

头文件.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QNode;
typedef struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}Que;
void QueueInit(Que* pq);
void QueueDestroy(Que* pq);
void QueuePush(Que* pq, QDataType x);
void QueuePop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);

源文件1（Queue.c）

#include "Queue.h"
void QueueInit(Que* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
void QueueDestroy(Que* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
void QueuePush(Que* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->data = x;
  newnode->next = NULL;
  if (pq->tail == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
  pq->size++;
}
void QueuePop(Que* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
  pq->size--;
}
QDataType QueueFront(Que* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
QDataType QueueBack(Que* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
bool QueueEmpty(Que* pq)
{
  assert(pq);
  return pq->head == NULL;
}
int QueueSize(Que* pq)
{
  assert(pq);
  return pq->size;
}

源文件2（BinaryTree.c）

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef struct BinaryTreeNode
{
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
  int val;
}BTNode;
#include"Queue.h"
//开辟节点
BTNode* BuyNode(int x)
{
  BTNode* node = (BTNode*)malloc(sizeof(BTNode));
  if (node == NULL)
  {
    printf("malloc fail");
    exit(-1);
  }
  node->val = x;
  node->left = NULL;
  node->right = NULL;
}
//前序遍历
void PrevOrder(BTNode* root)
{
  if (root == NULL)
  {
    return;
    }
  printf("%d ", root->val);
  PrevOrder(root->left);
  PrevOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  PrevOrder(root->left);
  printf("%d ", root->val);
  PrevOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  PrevOrder(root->left);
  PrevOrder(root->right);
  printf("%d ", root->val);
}
//层序遍历
void LevelOrder(BTNode* root)
{
  Que q;
  QueueInit(&q);//初始化队列
  if (root)
    QueuePush(&q, root);
  //队列不为空。循环继续
  while (!QueueEmpty(&q))
  {
    //获取队头元素
    BTNode* front = QueueFront(&q);
    printf("%d ", front->val);
    //出队元素的左孩子入队列
    if (front->left)
      QueuePush(&q, front->left);
    //出队元素的右孩子入队列
    if (front->right)
      QueuePush(&q, front->right);
    QueuePop(&q);
  }
  printf("\n");
    //销毁队列
  QueueDestroy(&q);
}
//树节点的个数
int BinaryTreeSize(BTNode* root)
{
  //节点个数=左子树的节点个数+右子树的节点个数+1;
  return root == NULL ? 0 : 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 sumOfLeftLeaves(BTNode* root)
{
  //空树叶子无节点
  if (root == NULL)
  {
    return 0;
  }
  int sum = 0;
  //判断是否为左叶子节点
  if (root->left && root->left->left == NULL && root->left->right == NULL)
  {
    sum = root->left->val;
  }
  return sum + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
}
//树中第K层节点个数为：
int BinaryTreeKLeveSize(BTNode* root,int k)
{
  //空树或输入不合法
  if (k < 1 || root == NULL)
  {
    return 0;
  }
     //K=1为第一层
  if (k == 1)
  {
    return 1;
  }
  //第K层的节点个数=相对于两个孩子的第K-1层的节点个数之和
  return BinaryTreeKLeveSize(root->left, k - 1) + BinaryTreeKLeveSize(root->right, k - 1);
}
// 二叉树销毁
void TreeDestroy(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  TreeDestroy(root->left);
  TreeDestroy(root->right);
  free(root);
  //root = NULL;
}
// 二叉树查找值为x的结点
BTNode* TreeFind(BTNode* root, int x)
{
  //空树
  if (root == NULL)
    return NULL;
  //先判断根节点
  if (root->val == x)
    return root;
  //在左孩子中找
  BTNode* ret = NULL;
  ret = TreeFind(root->left, x);
  if (ret)
    return ret;
  //在右孩子中找
  ret = TreeFind(root->right, x);
  if (ret)
    return ret;
  //根节点和左右子树节点中均未找到
  return NULL;
}
// 判断二叉树是否是完全二叉树
int TreeComplete(BTNode* root)
{
  Que q;
  QueueInit(&q);//初始化队列
  if (root)
    QueuePush(&q, root);
  //当队列不为空时，继续
  while (!QueueEmpty(&q))
  {
    //读取队头元素
    BTNode* front = QueueFront(&q);
    //当读取到空指针时，停止入队操作
    if (front == NULL)
      break;
    //出队元素的左孩子入队列
    QueuePush(&q, front->left);
    //出队元素的右孩子入队列
    QueuePush(&q, front->right);
    QueuePop(&q);
  }
  // 已经遇到空节点，如果队列中后面的节点还有非空，就不是完全二叉树
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    //若队列中存在非空指针，则不是完全二叉树
    if (front != NULL)
    {
      //销毁队列
      QueueDestroy(&q);
      return false;
    }
  }
  QueueDestroy(&q);
  //若队列中全是空指针，则是完全二叉树
  return true;
}
//求树的深度或者高度
// 
//第一种写法：及其不推荐
//int TreeHeight(BTNode* root)
//{
//  if (root == NULL)
//    return 0;
//
//  return TreeHeight(root->left) > TreeHeight(root->right)
//    ? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
//}
//树的深度：左右子树高的那颗树高度在加1
int TreeHeight(BTNode* 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(BTNode* root)
//{
//  if (root == NULL)
//    return 0;
//
//  return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
//}
//求最大深度：
int getdepth(BTNode* node)
{
  if (node == NULL)
    return 0;
  int leftdepth = getdepth(node->left);       // 左
  int rightdepth = getdepth(node->right);     // 右
  int depth = 1 + max(leftdepth, rightdepth); // 中
  return depth;
}
int maxDepth(BTNode* root)
{
  return getdepth(root);
}
//求N叉树的最大深度
//int maxDepth(BTNode* root)
//{
//  if (root == NULL)
//    return 0;
//  int depth = 0;
//  for (int i = 0; i < root->numChildren; i++)
//  {
//    depth = fmax(depth, maxDepth(root->children[i]));
//  }
//  return depth + 1;
//}
//求最小深度
int getdepth2(BTNode* root)
{
  if (root == NULL)
    return 0;
  int leftdepth = getdepth2(root->left);//左
  int rightdepth = getdepth2(root->right);//右
  //当左子树为空，右子树不为空，则此时并不是最低点
  if (root->left == NULL && root->right != NULL)
  {
    return 1 + rightdepth;
  }
  //当左子树不为空，右子树为空，则此时并不是最低点
  if (root->left != NULL && root->right == NULL)
  {
    return 1 + leftdepth;
  }
  //都不为空：
  int result = 1 + min(leftdepth, rightdepth);
  return result;
}
//int minDepth(struct TreeNode* root)
//{
//  return getdepth2(root);
//}
//精简版本：
int minDepth(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  //左子树为空，右子树不为空
  if (root->left == NULL && root->right != NULL)
  {
    return 1 + minDepth(root->right);
  }
  //左子树不为空，右子树为空
  if (root->left != NULL && root->right == NULL)
  {
    return 1 + minDepth(root->left);
  }
  //都不为空：
  return min(minDepth(root->left), minDepth(root->right)) + 1;
}
//路径总和（是否存在路径和为目标值的路径，存在返回true,不存在返回false)
bool hasPathSum(BTNode* root, int targetSum)
{
  //空树时，不存在
  if (root == NULL)
  {
    return false;
  }
  targetSum = targetSum - root->val;
  //左右节点均为空时，且targetSum为0时，满足条件
  if (root->left == NULL && root->right == NULL && targetSum == 0)
  {
    return true;
  }
  //
  return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
}
//求树最左下角的值：
void dfs(BTNode* root, int* max_depth, int depth, int* value)
{
  if (root == NULL)
  {
    return;
  }
  if (*max_depth < depth)
  {
    *value = root->val;
    *max_depth = depth;
  }
  /* 保证深度最深的第一个点是左子树节点 */
  dfs(root->left, max_depth, depth + 1, value);
  dfs(root->right, max_depth, depth + 1, value);
}
int findBottomLeftValue(BTNode* root)
{
  if (root->right == NULL && root->left == NULL)
  {
    return root->val;
  }
  int value = 0;
  /* 记录最大深度 */
  int max_depth = 0;
  dfs(root, &max_depth, 0, &value);
  return value;
}
//翻转二叉树
BTNode* invertTree(BTNode* root)
{
  if (root == NULL)//根为空，直接返回
    return NULL;
  BTNode* left = invertTree(root->left);//翻转左子树
  BTNode* right = invertTree(root->right);//翻转右子树
  //左右子树位置交换
  root->left = right;
  root->right = left;
  return root;
}
//判断二叉树是否是平衡二叉树
bool isBalanced(BTNode* root)
{
  if (root == NULL)//空树是平衡二叉树
    return true;
  int leftDepth = TreeHeight(root->left);//求左子树的深度
  int rightDepth = TreeHeight(root->right);//求右子树的深度
  //左右子树高度差的绝对值不超过1 && 其左子树是平衡二叉树 && 其右子树是平衡二叉树
  return abs(leftDepth - rightDepth) < 2 && isBalanced(root->left) && isBalanced(root->right);
}
//单值二叉树
bool isUnivalTree(BTNode* root)
{
  //空树符合情况，返回true
  if (root == NULL)
  {
    return true;
  }
  //首先满足左子树不为空的条件下，判断左子树的值是否与根相同
  if (root->left && root->left->val != root->val)
  {
    return false;
  }
  //首先满足右子树不为空的条件下，判断左子树的值是否与根相同
  if (root->right && root->right->val != root->val)
  {
    return false;
  }
  return isUnivalTree(root->left) && isUnivalTree(root->right);
}
//相同的树
bool isSameTree(BTNode* p,BTNode* 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);
}
//对称二叉树：
bool isSameTree2(BTNode* p, BTNode* q)
{
  //都为空
  if (p == NULL && q == NULL)
  {
    return true;
  }
  //其中一个为空
  if (p == NULL || q == NULL)
  {
    return false;
  }
  //都不为空
  if (p->val != q->val)
  {
    return false;
  }
  return isSameTree2(p->left, q->right) && isSameTree2(p->right, q->left);
}
bool isSymmetric(BTNode* root)
{
  if (root == NULL)
  {
    return true;
  }
  return isSameTree2(root->left, root->right);
}
//二叉树的前序遍历（接口型）
//为防止开辟空间浪费，先求一下树的节点个数
int TreeSize(BTNode* root)
{
  return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void preorder(BTNode* root, int* a, int* pi)
{
  if (root == NULL)
  {
    return;
  }
  a[(*pi)++] = root->val;
  preorder(root->left, a, pi);
  preorder(root->right, a, pi);
}
int* preorderTraversal(BTNode* root, int* returnSize)
{
  int n = TreeSize(root);
  int* a = (int*)malloc(sizeof(int) * n);
  int j = 0;
  preorder(root, a, &j);
  *returnSize = n;
  return a;
}
//另一颗树的子树
bool isSubtree(BTNode* root, BTNode* subRoot)
{
  if (root == NULL)
  {
    return false;
  }
  if (root->val == subRoot->val)
  {
    if (isSameTree(root, subRoot))
    {
      return true;
    }
  }
  return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
//二叉树遍历：（KY11牛客网）
//#include <stdio.h>
//#include<stdlib.h>
//
//typedef struct BinaryTreeNode
//{
//  struct BinaryTreeNode* left;
//  struct BinaryTreeNode* right;
//  int val;
//}BTNode;
//
//BTNode* GreateTree(char* str, int* pi)
//{
//  if (str[*pi] == '#')
//  {
//    (*pi)++;
//    return NULL;
//  }
//
//  BTNode* root = (BTNode*)malloc(sizeof(BTNode));
//  root->val = str[*pi];
//  (*pi)++;
//
//  root->left = GreateTree(str, pi);
//  root->right = GreateTree(str, pi);
//
//  return root;
//}
//
//void Inorder(BTNode* root)
//{
//  if (root == NULL)
//  {
//    return;
//  }
//
//  Inorder(root->left);
//  printf("%c ", root->val);
//  Inorder(root->right);
//
//}
//int main()
//{
//  char str[100];
//  scanf("%s", str);
//
//  int i = 0;
//  BTNode* root = GreateTree(str, &i);
//  Inorder(root);
//  return 0;
//}
//完全二叉树的节点个数
int countNodes(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  //拿到左子树的个数
  int lson = countNodes(root->left);
  //拿到右子树的个数
  int rson = countNodes(root->right);
  //在加上自己
  return 1 + lson + rson;
}
//合并二叉树：
BTNode* mergeTrees(BTNode* t1, BTNode* t2)
{
  if (t1 == NULL)
    return t2;
  if (t2 == NULL)
    return t1;
  // 重新定义新的节点，不修改原有两个树的结构
  BTNode* root = (BTNode*)malloc(sizeof(BTNode));
  if (root == NULL)
  {
    printf("malloc fail");
    exit(-1);
  }
  root->val = t1->val + t2->val;
  root->left = mergeTrees(t1->left, t2->left);
  root->right = mergeTrees(t1->right, t2->right);
  //打印结果：
  Que q;
  QueueInit(&q);//初始化队列
  if (root)
    QueuePush(&q, root);
  //队列不为空。循环继续
  while (!QueueEmpty(&q))
  {
    //获取队头元素
    BTNode* front = QueueFront(&q);
    printf("%d ", front->val);
    //出队元素的左孩子入队列
    if (front->left)
      QueuePush(&q, front->left);
    //出队元素的右孩子入队列
    if (front->right)
      QueuePush(&q, front->right);
    QueuePop(&q);
  }
  //销毁队列
  QueueDestroy(&q);
  return root;
}
//构建最大二叉树
//子函数
BTNode* traversal(int* nums, int left, int right)
{
  //若左边界大于右边界，返回NULL
  if (left >= right)
    return NULL;
  //找出数组中最大数坐标
  int maxIndex = left;
  int i;
  for (i = left + 1; i < right; i++)
  {
    if (nums[i] > nums[maxIndex])
      maxIndex = i;
  }
  //开辟结点
  BTNode* node = (BTNode*)malloc(sizeof(BTNode));
  if (node == NULL)
  {
    printf("malloc fail");
    exit(-1);
  }
  //将结点的值设为最大数组数组元素
  node->val = nums[maxIndex];
  node->left = NULL;
  node->right = NULL;
  //递归定义左孩子结点和右孩子结点
  node->left = traversal(nums, left, maxIndex);
  node->right = traversal(nums, maxIndex + 1, right);
  return node;
}
//构建二叉树
BTNode* constructMaximumBinaryTree(int* nums, int numsSize)
{   
  BTNode* node= traversal(nums, 0, numsSize);
  Que q;
  QueueInit(&q);//初始化队列
  if (node)
    QueuePush(&q, node);
  //队列不为空。循环继续
  while (!QueueEmpty(&q))
  {
    //获取队头元素
    BTNode* front = QueueFront(&q);
    printf("%d ", front->val);
    //出队元素的左孩子入队列
    if (front->left)
      QueuePush(&q, front->left);
    //出队元素的右孩子入队列
    if (front->right)
      QueuePush(&q, front->right);
    QueuePop(&q);
  }
  printf("\n");
  //销毁队列
  QueueDestroy(&q);
  return traversal(nums, 0, numsSize);
}
int main()
{
  //手动构建一颗二叉树
  BTNode* node1 = BuyNode(1);
  BTNode* node2 = BuyNode(2);
  BTNode* node3 = BuyNode(3);
  BTNode* node4 = BuyNode(4);
  BTNode* node5 = BuyNode(5);
  BTNode* node6 = BuyNode(6);
  BTNode* node7 = BuyNode(7);
  BTNode* node8 = BuyNode(8);
  BTNode* node9 = BuyNode(9);
  BTNode* node10 = BuyNode(10);
  BTNode* node11 = BuyNode(11);
  BTNode* node12 = BuyNode(12);
  node10->left = node11;
  node10->right = node12;
  node11->left = NULL;
  node11->right = NULL;
  node12->left = NULL;
  node12->right = NULL;
  //构造数组，方便构造二叉树
  int a[] = {1,2,3,25,4,5,6,7,8,9,19};
  //计算大小
  int nums = sizeof(a) / sizeof(a[0]);
  node1->left = node2;
  node2->left = node3;
  node3->left = node5;
  node3->right = node6;
  node2->right = node4;
  node1->right = node7;
  node7->left = node8;
  node7->right = node9;
  node9->left = node10;
  printf("翻转前（原树）：\n");
  printf("前序遍历：\n");
  PrevOrder(node1);
  printf("\n");
  printf("中序遍历：\n");
  InOrder(node1);
  printf("\n");
  printf("\n");
  printf("后序遍历：\n");
  PostOrder(node1);
  printf("\n");
  printf("\n");
  printf("层序遍历结果为：\n");
  LevelOrder(node1);
  printf("\n");
  int ret1 = BinaryTreeSize(node1);
  printf("树节点的总个数: %d：\n", ret1);
  int ret2 = BinaryTreeLeafSize(node1);
  printf("叶子节点个数为: %d：\n", ret2);
  int ret3 = BinaryTreeKLeveSize(node1, 3);
  printf("第3层节点个数为: %d：\n", ret3);
  int ret4 = sumOfLeftLeaves(node1);
  printf("左叶子之和为: %d：\n", ret4);
  printf("\n");
  printf("判断从3根节点开始是否为原树的子树：%d\n", isSubtree(node1, node3));
  printf("判断是否存在满足目标值(16)的路径：%d\n", hasPathSum(node1, 16));
  printf("树的高度为：%d\n", TreeHeight(node1));
  printf("树最大深度为：%d\n", maxDepth(node1));
  printf("树最左下角的值为：%d\n", findBottomLeftValue(node1));
  printf("是否为单值二叉树：%d\n", isUnivalTree(node1));
  printf("是否为完全二叉树：%d\n", TreeComplete(node1));
  printf("完全二叉树的节点个数为：%d\n", countNodes(node1));
  printf("是否为平衡二叉树：%d\n", isBalanced(node1));
  printf("将两个二叉树合并后：\n");
  mergeTrees(node1, node10);
  printf("\n");
  printf("\n");
  //翻转后：
  printf("翻转后：\n");
  invertTree(node1);
  printf("\n");
  printf("前序遍历：\n");
  PrevOrder(node1);
  printf("\n");
  printf("\n");
  printf("中序遍历：\n");
  InOrder(node1);
  printf("\n");
  printf("\n");
  printf("后序遍历：\n");
  PostOrder(node1);
  printf("\n");
  printf("\n");
  printf("层序遍历结果为：\n");
  LevelOrder(node1);
  printf("\n");
  int ret5=BinaryTreeSize(node1);
  printf("树节点的总个数: %d：\n",ret1);
  int ret6=BinaryTreeLeafSize(node1);
  printf("叶子节点个数为: %d：\n",ret2);
  int ret7=BinaryTreeKLeveSize(node1, 3);
  printf("第3层节点个数为: %d：\n",ret3);
  int ret8 = sumOfLeftLeaves(node1);
  printf("左叶子之和为: %d：\n", ret4);
  printf("判断从3根节点开始是否为原树的子树：%d\n", isSubtree(node1, node3));
  printf("判断是否存在满足目标值(16)的路径：%d\n", hasPathSum(node1, 16));
  printf("树的高度为：%d\n", TreeHeight(node1));
  printf("最大深度为：%d\n", maxDepth(node1));
  printf("最小深度为：%d\n", minDepth(node1));
  printf("树1最左下角的值为：%d\n",findBottomLeftValue(node1));
    printf("树2最左下角的值为%d\n",findBottomLeftValue(node10));
  printf("树1是否为单值二叉树：%d\n", isUnivalTree(node1));
    printf("树2是否为单值二叉树：%d\n", isUnivalTree(node10));
    printf("树1是否为完全二叉树：%d\n", TreeComplete(node1));
    printf("树2是否为完全二叉树：%d\n", TreeComplete(node10));
    printf("树1是否为平衡二叉树：%d\n", isBalanced(node1));
    printf("树2是否为平衡二叉树：%d\n", isBalanced(node10));
  printf("构建的最大二叉树为：\n");
  constructMaximumBinaryTree(a, nums);
  printf("将两个二叉树合并后：\n");
  mergeTrees(node1, node10);
  //销毁
  TreeDestroy(node1);
  node1 = NULL;
  return 0;
}


文章标签：
算法
小小unicorn
目录
相关文章
你的小笔记本YY
|
8月前
|
存储 C++ 容器
【C++＆数据结构】二叉树（结合C++）的经典oj例题 [ 盘点＆全面解析 ]（24）
【C++＆数据结构】二叉树（结合C++）的经典oj例题 [ 盘点＆全面解析 ]（24）
你的小笔记本YY
95 0
小小unicorn
|
存储 算法
链式二叉树的基本操作实现（建议收藏！！！）（2）
链式二叉树的基本操作实现（建议收藏！！！）
小小unicorn
109 0
屿小夏
|
存储
链式二叉树(二叉树看这一篇就够了)
链式二叉树(二叉树看这一篇就够了)
屿小夏
67 0
买个心动也用券
【LeetCode】——链式二叉树经典OJ题详解
在之前的文章讲解了二叉树的链式结构的实现以及前、中、后序的遍历。不知道大家看完后有没有理解和有所收获，今天基于那篇文章给大家分享讲解几道经典的题目，更便于大家的理解和深入。
买个心动也用券
51 1
BetterBench
|
5月前
|
Python
【Leetcode刷题Python】105. 从前序与中序遍历序列构造二叉树
LeetCode上105号问题"从前序与中序遍历序列构造二叉树"的Python实现，通过递归方法根据前序和中序遍历序列重建二叉树。
BetterBench
34 3
起飞的风筝
|
8月前
|
存储 算法
【链式二叉树】数据结构链式二叉树的（万字详解）
【链式二叉树】数据结构链式二叉树的（万字详解）
起飞的风筝
87 0
小小unicorn
|
存储
链式二叉树的基本操作和相关OJ题训练（建议收藏！！！）（2）
链式二叉树的基本操作和相关OJ题训练（建议收藏！！！）
小小unicorn
58 0
小小unicorn
|
存储
链式二叉树的基本操作和相关OJ题训练（建议收藏！！！）（1）
链式二叉树的基本操作和相关OJ题训练（建议收藏！！！）
小小unicorn
57 0
小小unicorn
链式二叉树的基本操作实现（建议收藏！！！）（1）
链式二叉树的基本操作实现（建议收藏！！！）
小小unicorn
62 0
小小unicorn
链式二叉树的基本操作实现（建议收藏！！！）（3）
链式二叉树的基本操作实现（建议收藏！！！）
小小unicorn
40 0