目录
单值二叉树
相同的树
另一棵树的子树
二叉树的前序遍历
二叉树的构造及遍历
给大家推荐一款刷题，找工作的好网站——牛客网
牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网
单值二叉树
思路：根节点跟左子树比较，若相等则继续比，一值比到左子树为空，比完之后再跟右子树比较
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; //一个为空，一个不为空，则false
if(p->val!=q->val)
return false;//不相等，fasle
return isSameTree(p->left,q->left)&&isSameTree(q->right,p->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(q->right,p->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(root==NULL)
return false;
if(isSameTree(root,subRoot))
return true;
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}
二叉树的前序遍历
思路：1.先统计出该二叉树节点的个数
2.创建一个新的数组，数组大小为二叉树总结点大小
3.进行前序遍历根，左，右
int TreeSize(struct TreeNode* root)
{
if(root==NULL)
return 0;
return TreeSize(root->left)+TreeSize(root->right)+1;
} //统计个数
void preorder(struct TreeNode* root,int *a,int *pi)
{
if(root==NULL)
return;
a[*pi]=root->val;
(*pi)++;
preorder(root->left,a,pi);
preorder(root->right,a,pi);
}//遍历
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* preorderTraversal(struct TreeNode* root, int* returnSize){
int n=TreeSize(root);
int *a=(int*)malloc(sizeof(int)*n);
int i=0;
preorder(root,a,&i);
*returnSize=n;
return a;
}
二叉树的构造及遍历
二叉树遍历_牛客题霸_牛客网 (nowcoder.com)
1.建立一个数组，给数组输入数据，#代表NULL
2.构建一个二叉树，把数组的值输按前序遍历输入到二叉树中，当遇到#时，代表该节点为空
3.将前序遍历好的二叉树，进行中序遍历
#include
#include
typedef char Datatypedef;
typedef struct BinaryTreeNode
{
Datatypedef data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}TreeNode;//定义二叉树
TreeNode* CreateTree(char* arr, int* pi)
{
if (arr[*pi] == '#')
{
(*pi)++;
return NULL;
}
TreeNode* tmp = (TreeNode*)malloc(sizeof(TreeNode));
tmp->data = arr[*pi];
(*pi)++;
tmp->left = CreateTree(arr, pi);
tmp->right = CreateTree(arr, pi);
return tmp;
}//创建二叉树，并把数组的值赋值给二叉树，按前序遍历赋值
void InorDer(TreeNode* tmp)
{
if (tmp == NULL)
return;
InorDer(tmp->left);
printf("%c ", tmp->data);
InorDer(tmp->right);
}//前序遍历换为中序遍历
int main()
{
char arr[100];
scanf("%s", arr);
int i = 0;
TreeNode* root = CreateTree(arr, &i);
InorDer(root);
return 0;
}
推荐阅读
您阅读本篇文章共花了：
发表评论