如何构建一个YTU 3025型号的二叉树？

本文共计612个文字，预计阅读时间需要3分钟。

pythonclass TreeNode: def __init__(self, x): self.val=x self.left=None self.right=None

def build_tree(preorder, inorder): if not preorder or not inorder: return None

root_val=preorder[0] root=TreeNode(root_val) root_index=inorder.index(root_val)

root.left=build_tree(preorder[1:1 + root_index], inorder[:root_index]) root.right=build_tree(preorder[1 + root_index:], inorder[root_index + 1:])

return root

def print_tree(root): if not root: return print(root.val, end=' ') print_tree(root.left) print_tree(root.right)

preorder=[3, 9, 20, 15, 7]inorder=[9, 3, 15, 20, 7]root=build_tree(preorder, inorder)print_tree(root)

3025: 创建二叉树

时间限制: 1 Sec 内存限制: 128 MB

提交:

3 解决: 3

题目描述

已知一颗二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，给出二叉树的树形表示（用括号法）。

输入

输出

输出带有括号与字母的用括号法表示的二叉树。

提示

首先根据中序序列和后序序列画出二叉树，然后用括号法表示之。

利用中序序列与后序序列构造二叉树，然后采用括号表示法输出！

AC代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Node
{
char data;
Node *lc;
Node *rc;
} Node;
Node *CreateBT2(char *post,char *in,int n)
{
Node *b;
int r,k;
char *p;
if(n<=0)return NULL;
r=*(post+n-1); //定位到当前区间最后一个地址，根节点
b=(Node*)malloc(sizeof(Node));
b->data=r; //开始创建
for(p=in; p<in+n; p++)
if(*p==r)break;
k=p-in; //定位根节点在中序遍历中的位置
b->lc=CreateBT2(post,in,k);
b->rc=CreateBT2(post+k,p+1,n-k-1);
return b;
}
void Print(Node *b)
{
if(b!=NULL)
{
printf("%c",b->data);
if(b->lc!=NULL||b->rc!=NULL)
{
printf("(");
Print(b->lc);
if(b->rc!=NULL)printf(",");
Print(b->rc);
printf(")");
}
}
}
int main()
{
int len;
Node *head;
char post[30]="cedbhjigfa",in[30]="cbedahgijf"; // 存储先序和中序遍历的序列
head=(Node*)malloc(sizeof(Node));
len=strlen(post);
head=CreateBT2(post,in,len); //构造二叉树
Print(head); //用括号表示法输出二叉树
return 0;
}