数据结构习题

2024-07-09 18:44| 来源: 网络整理| 查看: 265

前言

二叉树这两道题有点不太明白记录下来

正文题目一

设一颗二叉树各结点的值互不相同，其先序遍历序列和中序遍历序列分别存在两个一维数组A[1…n]和B[1…n]中，试编写算法建立该二叉树的二叉链表关键找到循环体：

根据先序序列确定树的根结点根据根结点在中序序列中划分出二叉树的左、右子树中包含哪些结点，然后根据左、右子树结点在先序序列中确定子树的根结点，即返回步骤1 //初始值l1=l2=1,h1=h2=n BiTree PreInCreate(int a[],int b[],int l1,int h1,int l2,int h2){ BiTNode *root=(BiTNode *)malloc(sizeof(BiTNode)); root->data=a[l1];//在先序序列中找到root for(int i=l1;b[i]!=root->data;i++);//找到root在中序序列中的位置 int llen=i-l2;//划分为左右部分（不含该root） int rlen=h2-i; if(len) //递归建立左右子树 root->lchild=PreInCreate(a,b,l1+1,l1+llen,l2,l2+llen-1);//先序和中序遍历中的左子树界限 else root->lchild=NULL; if(rlen) root->rchild=PreInCreate(a,b,h1-rlen+1,h1,h2-rlen+1,h2);//先序和中序遍历中的右子树界限 else root->rchild=NULL; return root; } 题目二

对于一颗满二叉树（所有结点值均不同）已知先序pre，求后序序列post 关键：满二叉树利用先序才能确定后续，其任意一个结点的左、右子树均含有相等的结点数，同时先序序列的第一个结点也是后序序列的最后一个结点每次递归，根结点从头（先序序列中的l1）移动到尾（后序序列中的h2），然后取中间位置half，划分为左右子树，将其从先序中移动到后序相应位置。左子树：pre[l1+1,l1+hlaf]转为post[l2,l2+half-1] 右子树：pre[l1+half+1,h1]转为post[l2+half,h2-1] 在这里插入图片描述

BiTree PreToPost(int pre[],int l1,int h1,int post[],int l2,int h2){ int half; if(h1>=l1){ post[h2]=pre[l1]; half=(h1-l1)/2;//取中间位置 PreToPost(pre,l1+1,l1+half,post,l2,l2+half-1);//转换左子树 PreToPost(pre,l1+half+1,h1,post,l2+half,h2-1);//转换右子树 } }

【本文地址】

公司简介

联系我们