题目1009：二叉搜索树

如果序列相同则输出YES，否则输出NO

样例输入：

2
567432
543267
576342
0

样例输出：

YES
NO

来源：

2010年浙江大学计算机及软件工程研究生机试真题

AC代码：

//前序遍历序列和中序遍历序列能唯一确定一个二叉树
//本题关键在于数的构建和遍历

#include
              
               
#include
               
                 #define N 20 struct Node { //二叉树节点结构体 char id; Node *lchild; Node *rchild; }; Node *nodes[N]; char bst[N], s[N]; //接受输入的字符串 char in1[N], pre1[N], in2[N], pre2[N]; //存放构建好的二叉树的中序和前序遍历序列 int k; //遍历增量 void build(Node *no, Node *root) { //二叉树的构建 if(no->id > root->id) { if(root->rchild==NULL) root->rchild = no; else build(no,root->rchild); } if(no->id < root->id) { if(root->lchild==NULL) root->lchild = no; else build(no,root->lchild); } } void inOrder(Node *root, char in[]) { //中序遍历 if(root->lchild != NULL) inOrder(root->lchild,in); in[k++] = root->id; //将遍历结果存放到数组，方便后面的序列比较 if(root->rchild != NULL) inOrder(root->rchild,in); } void preOrder(Node *root, char pre[]) { //前序遍历 pre[k++] = root->id; if(root->lchild != NULL) preOrder(root->lchild,pre); if(root->rchild != NULL) preOrder(root->rchild,pre); } int main() { //freopen("in.txt","r",stdin); int n, i; while(scanf("%d",&n)!=EOF && n) { scanf("%s",bst); int len = strlen(bst); for(i=0; i
                
                 id = bst[i]; nodes[i]->lchild = NULL; //节点左右孩子初始化为空 nodes[i]->rchild = NULL; } for(i=1; i
                 
                  id = s[i]; nodes[i]->lchild = NULL; nodes[i]->rchild = NULL; } for(i=1; i
                  
                   
 
                   
 
                   
 
                  
                 
                
               
              

<script type="text/java script">

<script type="text/java script">BAIDU_CLB_fillSlot("771048");

点击复制链接 与好友分享! 回本站首页

<script> function copyToClipBoard(){ var clipBoardContent=document.title + '\r\n' + document.location; clipBoardContent+='\r\n'; window.clipboardData.setData("Text",clipBoardContent); alert("恭喜您！复制成功"); }

分享到： 更多

<script type="text/java script" id="bdshare_js" data="type=tools&uid=12732"> <script type="text/java script" id="bdshell_js"> <script type="text/java script"> var bds_config = {'snsKey':{'tsina':'2386826374','tqq':'5e544a8fdea646c5a5f3967871346eb8'}}; document.getElementById("bdshell_js").src = "http://bdimg.share.baidu.com/static/js/shell_v2.js cdnversion=" + Math.ceil(new Date()/3600000)

您对本文章有什么意见或着疑问吗？请到 论坛讨论您的关注和建议是我们前行的参考和动力

上一篇： 最全的IO操作知识总结

下一篇： 九度oj 1385 重建二叉树

相关文章

<script type="text/java script">BAIDU_CLB_fillSlot("182716");

<script type="text/java script">BAIDU_CLB_fillSlot("517916");

图文推荐

<script type="text/java script">BAIDU_CLB_fillSlot("771057");