当前位置：首页 > news >正文

链式二叉树经典题目梳理

news 2026/3/26 17:49:45

1、单值二叉树

2、判断两棵树是不是相同的树

3、判断一棵树是不是轴对称的树

4、前序（中序、后序）遍历一个二叉树，将树中的值放入一个给定的数组中

5、给定两棵二叉树，判断第二棵是不是第一棵的子树

6、给定一个字符数组，用数组中的每个元素构建一个二叉树，若为空格，则用#表示，在树中为NULL，最后中序遍历，输出树中的所有元素

———————————————————————————————————————————单值二叉树
//bool isUnivalTree(struct TreeNode* root) {
// if (root == NULL)
// {
// 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);
//}

———————————————————————————————————————————
//判断两棵树是不是相同的树
//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);
//
//}

———————————————————————————————————————————
//判断一棵树是不是轴对称的树
//bool _isSymmetric(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 _isSymmetric(p->left, q->right) && _isSymmetric(p->right, q->left);
//}
//bool isSymmetric(struct TreeNode* root) {
// return _isSymmetric(root->left, root->right);
//}

———————————————————————————————————————————
//前序遍历一个二叉树，将每个数放入一个数组中，并让使用者的主函数里关于二叉树大小的局部变量改变
//int TreeSize(struct TreeNode* root)
//{
// return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
//}
//
//void preorder(struct TreeNode* 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(struct TreeNode* root, int* returnSize) {
// //这里的int* returnSize是为了收到数组的个数，而采用整型指针的原因是为了修改实参
// //这里的returnSize是输出型参数
// *returnSize = TreeSize(root);
// int* a = (int*)malloc(sizeof(int) * (*returnSize));
// int i = 0;
// preorder(root, a, &i);
//
// return a;
//}

———————————————————————————————————————————
//给你两颗二叉树，判断第二棵是不是第一棵的子树
//bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
// //找到这棵树的所有子树
// if (root == NULL)
// {
// return false;
// }
// if (root->val == subRoot->val && isSameTree(root, subRoot))
// {
// return true;
// }
// return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
// //这样就拿到了这棵树的所有节点
//
//}———————————————————————————————————————————

构建并中序打印二叉树

#include <stdio.h>

#include <stdlib.h>

typedef struct BinTreeNode

{

struct BinTreeNode* left;

struct BinTreeNode* right;

char val;

}BTNode;

BTNode* createtree(char*a, int* pi)

{

if(a[*pi] == '#')