【数据结构】二叉树
1.介绍二叉树与树的差别是,二叉树中任意节点的度不超过2。二叉树是一种有序树,即左右子树之间有顺序关系,规定为左前右后。 二叉树的表示:顺序表示,链式表示。顺序表示有致命的缺点:对二叉树的中间节点进行插入、删除操作时,必须相对应地调整数组中数据的位置。链式表示克服了这些缺点,所以一般采用链式表示存储二叉树。 二叉树的遍历分为前序(preorder)、中序(inorder)、后序(postorder)。访问根结点的顺序分别为前、中、后;比如,中序遍历先遍历根结点的左子树,再访问该根结点,最后遍历根结点右子树。遍历的程序有递归实现和非递归实现两种,递归实现的程序简洁优美: 2.问题2.1 POJ 2255题目大意:给出前序遍历、中序遍历,求后序遍历。 思路:对前序遍历DBACEGF、中序遍历ABCDEFG; (1)找出根结点D,则BAC(ABC)是D的左子树,EGF(EFG)是D的右子树。 (2)递归处理D的左子树、右子树。 参考网上的C++源代码,递归写得非常简洁。用到了<string>的两个库函数find( ),substr( ),find( )返回字符串第一次出现的下标, string substr (size_t pos = 0,size_t len = npos) const; 返回子串,pos指定开始位置,len表示子串的长度。 源代码:
#include <iostream> #include <string> using namespace std; struct node { char data; node *lchild,*rchild; }; /*create binary-tree*/ node * create(string pre,string in) { int pos; node *p=NULL; if(pre.length()>0) { p=new node; p->data=pre[0]; pos=in.find(p->data); p->lchild=create(pre.substr(1,pos),in.substr(0,pos)); p->rchild=create(pre.substr(pos+1),in.substr(pos+1)); } return p; } void postorder(node *ptr) { if(ptr) { postorder(ptr->lchild); postorder(ptr->rchild); printf("%c",ptr->data); } } int main() { string pre,in; while (cin>>pre>>in) { node *root; root=create(pre,in); postorder(root); printf("n"); } return 0; } 2.2 HDU 1710给出先序遍历与中序遍历,求后序遍历。 用C实现,在输入时贪图简便,将输入用一个循环 for(i=0;i<n;i++) 结果调试了好久,才发现错误。切记。 源代码:
#include "stdio.h" #include "stdlib.h" typedef struct node { int data; struct node *lchild,*rchild; }; int pre[1000],in[1000]; struct node *create(int pre_start,int in_start,int length) { int pos,temp; struct node *p=NULL; if(length>0) { p=(struct node *) malloc(sizeof(struct node)); p->data=pre[pre_start]; for(pos=in_start;pos<in_start+length;pos++) { if(in[pos]==p->data) break; } temp=pos-in_start; p->lchild=create(pre_start+1,in_start,temp); p->rchild=create(pre_start+temp+1,pos+1,length-temp-1); } return p; } void postorder(struct node *ptr,int root_flag) { if(ptr) { postorder(ptr->lchild,0); postorder(ptr->rchild,0); if(root_flag) printf("%dn",ptr->data); else printf("%d ",ptr->data); } } int main() { int i,n; while (~scanf("%d",&n)) { for(i=0;i<n;i++) scanf("%d",&pre[i]); for(i=0;i<n;i++) scanf("%d",&in[i]); postorder(create(0,n),1); } return 0; } 2.3 POJ 2499题目大意:二叉树根节点(1,1),节点(a,b)的左孩子为(a+b,b)、右孩子(a,a+b);给定(a,b),判断向左走、向右走的步数。 思路:对节点(a,b), (1)若a>b,则其为父节点(a-b,b)的左孩子节点; (2)若a<b,则其为父节点(a,b-a)的右孩子节点; (3)一直循环至根节点(1,1)。 优化:当a>b时,需要向左走a/b步,之后a<b;当a<b时,需向右走b/a步,之后a>b。需要注意的是,有可能a%b==0(或a%b==0),需要做一些处理。 源代码:
#include "stdio.h" int main() { int num_scenario,a,b; int count,l,r,temp; scanf("%d",&num_scenario); for(count=1;count<=num_scenario;count++) { l=r=0; scanf("%d%d",&a,&b); while (a!=1||b!=1) { if(a>b) { temp=(a-1)/b; a-=temp*b; l+=temp; } else { temp=(b-1)/a; b-=temp*a; r+=temp; } } printf("Scenario #%d:n%d %dnn",count,r); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |