网站开发代码h5,福州网站设计企业建站,为什么建设银行的网站打不开,宜兴做阿里巴巴网站二叉树的构建及遍历 本题目的要求是#xff1a; 输入一个数组#xff0c;里面存放了若干个字符#xff0c;#代表了空指针#xff0c;数组中的顺序是 是先序遍历#xff0c;然后要求你用中序输出 首先我们要做的就是构造结构体#xff1a;
typedef struct TreeNode
{char…二叉树的构建及遍历 本题目的要求是 输入一个数组里面存放了若干个字符#代表了空指针数组中的顺序是 是先序遍历然后要求你用中序输出 首先我们要做的就是构造结构体
typedef struct TreeNode
{char val;struct TreeNode* left;struct TreeNode* right;
}TreeNode;然后用先序遍历构造二叉树 当数组的首元素为#或者“\0”即二叉树没有根节点为空树直接接返回 然后我们开辟新节点的空间 然后进行先序遍历构造二叉树 首先将newnode的值置为数组首元素同时下标count 然后递归newnode的左子树根节点*countcount传的是地址所以记得解引用随后递归右子树根节点即可最后返回newnode就是二叉树的根节点
TreeNode* maketree(char*arr,int*count)
{if(arr[*count]#||arr[*count]\0){return NULL;}TreeNode* newnode (TreeNode*)malloc(sizeof(TreeNode));newnode-val arr[(*count)];newnode-left maketree(arr,count);(*count);newnode-right maketree(arr,count);return newnode;
}
最后写一个中序遍历的输出
void Inorder(TreeNode* root)
{if(rootNULL){return;}Inorder(root-left);printf(%c ,root-val);Inorder(root-right);
}完整代码如下
#include stdio.h
#includestdlib.h
typedef struct TreeNode
{char val;struct TreeNode* left;struct TreeNode* right;
}TreeNode;
TreeNode* maketree(char*arr,int*count)
{if(arr[*count]#||arr[*count]\0){return NULL;}TreeNode* newnode (TreeNode*)malloc(sizeof(TreeNode));newnode-val arr[(*count)];newnode-left maketree(arr,count);(*count);newnode-right maketree(arr,count);return newnode;
}
void Inorder(TreeNode* root)
{if(rootNULL){return;}Inorder(root-left);printf(%c ,root-val);Inorder(root-right);
}int main()
{char arr[101];scanf(%s,arr);int count 0;TreeNode* tree maketree(arr,count);Inorder(tree);return 0;
}判断一颗二叉树是否是平衡二叉树 本题很简单了 直接判断左子树和右子树的高度的绝对值是否小于等于1即可 同时左子树的子树和右子树的子树也要同时递归 调用求二叉树高度的函数
int height(struct TreeNode* root)
{if(rootNULL){return 0;}return fmax(height(root-left),height(root-right))1;
}
bool isBalanced(struct TreeNode* root)
{if(rootNULL){return true;}return fabs(height(root-left) - height(root-right)) 1 isBalanced(root-left) isBalanced(root-right);
}另一颗树的子树 本题就是判断一颗树的子树是否是另一棵树 所以我们首先要做的就是构造一个判断两棵树是否相等的函数 当两个树同时为空时也是相等的 当其中一个为空时肯定时不想同的 当root的值不等于subroot的值时肯定是不相等的
bool issame(struct TreeNode* root,struct TreeNode* subroot)
{if(rootNULLsubrootNULL)return true;if(rootNULL||subrootNULL)return false;if(root-valsubroot-val){if(issame(root-left,subroot-left)issame(root-right,subroot-right))return true;}return false;
}然后调用这个函数 当root和subroot相等时也符合题意
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{if(rootNULL)return false;if(issame(root,subRoot))return true;return isSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);
}对称二叉树 其实判断二叉树是否对称就是左边和右边比较对折重合 即 左子树和右子树相同左子树的左子树后右子树的右子树相同 我们直接调用上一题的判断树是否相同的函数 然后拿左子树和右子树比较即可 当左子树的根节点和右子树的根节点不相等时只返回false
bool issame(struct TreeNode* rootleft,struct TreeNode* rootright)
{if(rootleftNULLrootrightNULL)return true;if(rootleftNULL||rootrightNULL)return false;if(rootleft-valrootright-val){if(issame(rootleft-left,rootright-right)issame(rootleft-right,rootright-left))return true;}return false;
}
bool isSymmetric(struct TreeNode* root)
{if(root-leftNULLroot-rightNULL)return true;if(root-leftNULL||root-rightNULL)return false;if(root-left-valroot-right-val){if(issame(root-left,root-right))return true;}return false;
}检查两颗树是否相同
这不简简单单和之前的函数差不多使用递归就是了 同时为空返回true 有一个为空返回false 两个根节点的值不相等返回false
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{if(pNULLqNULL){return true;}if(pNULL||qNULL){return false;}if(p-val!q-val){return false;}return isSameTree(p-left,q-left)isSameTree(p-right,q-right);
}翻转二叉树 反转二叉树就是把左子树变成右子树右子树变成左子树 很简单直接先开辟空间存放然后赋于即可
struct TreeNode* invertTree(struct TreeNode* root)
{if (root NULL) {return NULL;}struct TreeNode* left invertTree(root-left);struct TreeNode* right invertTree(root-right);root-left right;root-right left;return root;
}二叉树最大深度 最大深度不就是高度吗就是层数啊 直接递归就是左子树和右子树中深度大的那一个1
int maxDepth(struct TreeNode* root)
{if(rootNULL)return 0;return fmax(maxDepth(root-left), maxDepth(root-right)) 1;
}单值二叉树 单值二叉树就是二叉树所有节点的值都相等 二叉树为空符合题意返回true 左子树和右子树为空符合题意只有一个节点返回true 当有一个不为空时不为空子树根节点和根节点不相等直接返回false 当两个子树都不为空时判断两个子树的根节点是否相等不相等直接返回false然后递归左子树和右子树的根节点
bool isUnivalTree(struct TreeNode* root)
{if(rootNULL)return true;if(root-leftNULLroot-rightNULL)return true;if(root-leftNULL||root-rightNULL){if(root-leftNULL){if(root-val!root-right-val)return false;}if(root-rightNULL){if(root-val!root-left-val)return false;}}if(root-left!NULLroot-right!NULL){if(root-val!root-left-val||root-val!root-right-val)return false;}return isUnivalTree(root-left)isUnivalTree(root-right);
}好了今天的分享到这里就结束了谢谢大家
