首页 > 代码库 > 二叉树深度、平衡、相等、求遍历

二叉树深度、平衡、相等、求遍历

#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;} 

二叉树深度、平衡、相等、求遍历