首页 > 代码库 > 二叉树深度、平衡、相等、求遍历
二叉树深度、平衡、相等、求遍历
#include <iostream> #include <fstream> #include <string> using namespace std;struct TreeNode { struct TreeNode* left; struct TreeNode* right; char elem; }; //知道先序遍历和中序遍历 求后序遍历TreeNode* BinaryTreeFromOrderings(char* inorder, char* preorder, int length) { if(length <= 0||preorder==NULL||preorder==NULL)//递归终止条件 { return NULL; } TreeNode* node = new TreeNode;//Noice that [new] should be written out. node->elem = *preorder; //将根节点赋值给新节点 int rootIndex = 0; for(;rootIndex < length; rootIndex++)//找出中序遍历中的头结点 { if(inorder[rootIndex] == *preorder) break; } if (rootIndex>=length)//如果没有找到 { throw std::exception("invalid input"); } node->left = BinaryTreeFromOrderings(inorder, preorder +1, rootIndex);//左子树递归 node->right = BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));//右子树递归 std::cout<<node->elem; return node; } //递归求二叉树的深度int PostTreeDepth(TreeNode *root){ int max,leftheight,rightheight; if (root==NULL) { return 0; } else { leftheight=PostTreeDepth(root->left); rightheight=PostTreeDepth(root->right); max=leftheight>rightheight?leftheight:rightheight; return (max+1); }}//判断两个树是否相等bool isTwoTreesEuqal(TreeNode *tree1,TreeNode *tree2){ if (tree1==NULL&&tree2==NULL)//两个都空 相等 { return true; } if (tree1&&!tree2||!tree1&&tree2)//一个空一个非空 不等 { return false; } if (tree1&&tree2)//两个都非空 判断是否相等 { if (tree1->elem==tree2->elem) { if (isTwoTreesEuqal(tree1->left,tree2->left)) { return isTwoTreesEuqal(tree1->right,tree2->right); } else if (isTwoTreesEuqal(tree1->left,tree2->right)) { return isTwoTreesEuqal(tree1->right,tree2->left); } } } return false;}//判断二叉树是否是平衡二叉树bool isBalanced(TreeNode *root){ if (root==NULL) { return true; } int leftheight=PostTreeDepth(root->left); int rightheight=PostTreeDepth(root->right); if (abs(leftheight-rightheight)>1)//如果大于1的话直接返回假 否则继续递归判断 { return false; } else return isBalanced(root->left)&&isBalanced(root->right);}int main(int argc, char** argv){ char* pr="GDAFEMHZ"; char* in="ADEFGHMZ"; TreeNode *root1=BinaryTreeFromOrderings(in, pr, 8); cout<<endl; cout<<PostTreeDepth(root1)<<endl; char* pr2="DAFEMHZ"; char* in2="ADEFHMZ"; TreeNode *root2=BinaryTreeFromOrderings(in2, pr2,7); cout<<endl; cout<<PostTreeDepth(root1)<<endl; cout<<isTwoTreesEuqal(root1,root2)<<endl; cout<<isBalanced(root1)<<endl; return 0;}
二叉树深度、平衡、相等、求遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。