二叉树习题(1.从叶节点按中序遍历逆序输出2.判断是否同构)-创新互联
做题之前要了解的是:二叉树的括号表示法和中序遍历的顺序。
分享名称:二叉树习题(1.从叶节点按中序遍历逆序输出2.判断是否同构)-创新互联
链接地址:http://pwwzsj.com/article/dgsodj.html
括号表示法:括号外的是父结点,括号内“,”号左侧为左子树“,”右侧为右子树。例如a(b(c(d,e)),f(g,h(i,j))),变为树如图:
10年积累的做网站、网站建设经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先做网站设计后付款的网站建设流程,更有土默特右旗免费网站建设让你可以放心的选择与我们合作。中序遍历:就是依次遍历:左子树--->根结点--->右子树。
第一题: 一、题目二、思路:首先设置树的结点,因为要逆序所以我额外设置了父指针,指向父结点。
typedef struct Node
{
char data;
Node *left;
Node *right;
Node *parents;
}BTNode;
因为是按照括号形式输入,所以要写一个函数,来通过该输入方式创建二叉树:
//由括号表示法创建二叉树
void CreateBTree(BTNode *&root, char str[])
{
int i=0, flag;
BTNode *p=NULL, *temp=NULL;
stackS;
while( str[i]!='\0')
{
switch( str[i] )
{
case '(':flag=1; S.push(p); break;//表示其后创建的为左儿子
case ')':S.pop( );break;//栈顶元素的左右儿子处理完了, 出栈
case ',':flag=2;break;//其后创建的为右儿子
default:
p=new Node;
p->data=str[i]; p->left=p->right=NULL;
if( root==NULL ) //如果当前每根,说明是第一个结点,设为根
{
root=p;
p->parents = NULL;
}
else //有根节点了,就把栈顶元素放到对应的子树上
{
temp=S.top();
p->parents = temp; //设置p的父结点
switch( flag )
{
case 1:temp->left=p; break;
case 2:temp->right=p; break;
}
}
}
i++;
}
}
题目要求按照中序遍历的顺序来输出:
//中序遍历二叉树
void InOrder(BTNode *root)
{
//cout<< "进来了1"<< endl ;
if(root)
{
//cout<< "进来了2"<< endl ;
InOrder(root->left);
if(root->left == NULL && root->right == NULL)
{
//cout<< "进来了3"<< endl ;
BTNode *p = root;
while(p != NULL)
{
//cout<< "进来了4"<< endl ;
cout<< p->data<< ' ';
p = p->parents;
}
cout<< endl;
}
InOrder(root->right);
}
}
三、所有代码: #include#includeusing namespace std;
typedef struct Node
{
char data;
Node *left;
Node *right;
Node *parents;
}BTNode;
//由括号表示法创建二叉树
void CreateBTree(BTNode *&root, char str[])
{
int i=0, flag;
BTNode *p=NULL, *temp=NULL;
stackS;
while( str[i]!='\0')
{
switch( str[i] )
{
case '(':flag=1; S.push(p); break;//表示其后创建的为左儿子
case ')':S.pop( );break;//栈顶元素的左右儿子处理完了, 出栈
case ',':flag=2;break;//其后创建的为右儿子
default:
p=new Node;
p->data=str[i]; p->left=p->right=NULL;
if( root==NULL ) //如果当前每根,说明是第一个结点,设为根
{
root=p;
p->parents = NULL;
}
else //有根节点了,就把栈顶元素放到对应的子树上
{
temp=S.top();
p->parents = temp; //设置p的父结点
switch( flag )
{
case 1:temp->left=p; break;
case 2:temp->right=p; break;
}
}
}
i++;
}
}
//中序遍历二叉树
void InOrder(BTNode *root)
{
//cout<< "进来了1"<< endl ;
if(root)
{
//cout<< "进来了2"<< endl ;
InOrder(root->left);
if(root->left == NULL && root->right == NULL)
{
//cout<< "进来了3"<< endl ;
BTNode *p = root;
while(p != NULL)
{
//cout<< "进来了4"<< endl ;
cout<< p->data<< ' ';
p = p->parents;
}
cout<< endl;
}
InOrder(root->right);
}
}
int main()
{
char str1[2000];
BTNode *root1=NULL;
cin>>str1;
//判断一棵二叉树是否为相似同构
root1=NULL;
CreateBTree(root1, str1);
InOrder(root1);
return 0;
}
//a(b(c(d,e)),f(g,h(i,j)))
第二题:
一、题目描述二、思路该题不需要父指针,去掉即可,创建二叉树的方式与上一题一样。主要是如何判断同构。
先设计个函数,用来判断两个树是否同构。
//判断两二叉树是否相似
int Like(BTNode *p1, BTNode *p2)
{
if(p1==NULL && p2==NULL)
return 1;
else if( p1==NULL || p2==NULL) //有一个先结束了,说明不同构
return 0;
else return Like(p1->left, p2->left)&Like(p1->right, p2->right); //左子树的左侧和右子树的左侧比,右侧和右侧比
}
再设计个函数,用上一个函数判断两个子树即可。
//判断一棵树是否对称同构
int SymmTree(BTNode *root)
{
if( root==NULL)//当树为空时
return 1;
else
return Like(root->left, root->right); //判断一棵树的两个子树
}
三、答案: #include#includeusing namespace std;
typedef struct Node
{
char data;
Node *left;
Node *right;
}BTNode;
//由括号表示法创建二叉树
void CreateBTree(BTNode *&root, char str[])
{
int i=0, flag;
BTNode *p=NULL, *temp=NULL;
stackS;
while( str[i]!='\0')
{
switch( str[i] )
{
case '(':flag=1; S.push(p); break;//表示其后创建的为左儿子
case ')':S.pop( );break;//栈顶元素的左右儿子处理完了, 出栈
case ',':flag=2;break;//其后创建的为右儿子
default:
p=new Node;
p->data=str[i]; p->left=p->right=NULL;
if( root==NULL ) //如果当前每根,说明是第一个结点,设为根
root=p;
else //有根节点了,就把栈顶元素放到对应的子树上
{
temp=S.top();
switch( flag )
{
case 1:temp->left=p; break;
case 2:temp->right=p; break;
}
}
}
i++;
}
}
//判断两二叉树是否相似
int Like(BTNode *p1, BTNode *p2)
{
if(p1==NULL && p2==NULL)
return 1;
else if( p1==NULL || p2==NULL) //有一个先结束了,说明不同构
return 0;
else return Like(p1->left, p2->left)&Like(p1->right, p2->right); //左子树的左侧和右子树的左侧比,右侧和右侧比
}
//判断一棵树是否对称同构
int SymmTree(BTNode *root)
{
if( root==NULL)//当树为空时
return 1;
else
return Like(root->left, root->right); //判断一棵树的两个子树
}
int main()
{
char str1[2000];
BTNode *root1=NULL;
cin>>str1;
//判断一棵二叉树是否为相似同构
root1=NULL;
CreateBTree(root1, str1);
if( SymmTree(root1) )
cout<<"true"<
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
分享名称:二叉树习题(1.从叶节点按中序遍历逆序输出2.判断是否同构)-创新互联
链接地址:http://pwwzsj.com/article/dgsodj.html