资源描述：
《数据结构参考算法(6)new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构参考算法（6）一、树和二叉树的定义树的定义：树中n(n>=0)个结点的有穷集T,且在T上定义了一个关系R:(1)仅的一个根结点；(2)其余结点可分为m(m>=0)个互不相交的有限集T1,...Tm,Ti子树。二、二叉树的定义：二叉树或空,或由根和两棵互不相交的左子树和右子树组成.二、存储结构二叉树的存储结构：typedefstructbitnode{datatypedatastructbitnode*lchild,*rchild;//二叉树的左、右孩子}Bnode,*Btree树的二叉链结构：typedefstructbitnode{datatyped
2、atastructbitnode*lchild;//左孩子,第一个孩子structbitnode*rnib;//右兄弟，下一个兄弟}Bnode,*Btree三、涉及的有关算法1．栈的基本运算（1）push(S,x):x入栈（在n+1处插入x）（2）pop(S,x):栈顶元素x出队（3）gettop(S,x):取栈顶元素（4）initstack(S):初始化栈（设置一个空栈）（5）stackemety(S):判栈空否2．队列的基本运算（1）enqueue(Q,x):x入队（在队尾处插入x）（2）delqueue(Q，x):队首元素x出队（3）getfront(Q
3、,x):取队首元素（4）initqueue(Q):初始化队列（设置一个空队列）（5）queueemety(Q):判队列Q空否四、算法设计6.1已知一棵完全二叉树存于顺序存储结构a[1]..a[n]中,a[1]..a[n]含结点值。编一算法建立二叉链存储结构.方法一:借助队列实现voidalg6_1(Bnode*bt,datatypea[]){initqueue(Q);//置空队列bt=(Bnode*)malloc(sizeof(Bnode));//生成头结点，bt:头指针bt->data=a[1];enqueue(Q,bt);//根结点入队for（i=1;i<
4、=n/2;i++）//依二叉树性质5{delqueue(Q,q);//队首元素q出队列p=(Bnode*)malloc(sizeof(Bnode));//生成一个新结点p->data=a[2*i];q->lchild=p;//建立左子树enqueue(Q,p);//左孩子入队if(2*i+1<=n){delqueue(Q,q);p=(Bnode*)malloc(sizeof(Bnode));//生成一个新结点p->data=a[2*i+1];q->rchild=p;//建立右子树enqueue(Q,p);//右孩子入队}}}//alg6_1方法二:用递归算法实
5、现voidcreate(Bnode*bt,inti,datatpa[]){bt=(Bnode*)malloc(sizeof(Bnode));//生成一个新结点bt->lchile=bt->rchile=NULL;if(2*i<=n)create(bt->lchild,2*i,a[]);if(2*i+1<=n)create(bt->rchild,2*i+1,a[]);}6.2以二叉链表作为存储结构,编一算法判别给定二叉树是否为完全二叉树.intalg6_2(Bnode*bt){b=1;initqueue(Q);//初始化队列enqueue(Q,bt);//根结点
6、入队while(getfront(Q)!=NULL)//当队首元素列不空时{delqueue(Q,bt);//队首结点出队enqueue(Q,bt->lchild);//左孩子入队enqueue(Q,bt->rchild);//右孩子入队}//依二叉树性质5可知，若队首元素已为空，则队中所有的元素应该都是空，否则，该树就不是一个完全二叉树while(!empty(Q)){delqueue(Q,bt);if(bt)b=0;}return(b);}//alg6_26.3已知一棵以二叉链为存储结构的二叉树,编写按求每一结点所在的层次的算法.voidalg6_3(Bn
7、ode*bt){initqueue(Q);//初始化队列enqueue(Q,(bt,1));//根及所在层1（bt,1）入队while(!empty(Q))//当队列不空时{delqueue(Q,(f,level));//队首元素（f,level）出队列printf(f->data,level);//按层次访问每一结点,并输出它所在的层次level++;if(f->lchild!=NULL)enqueue（Q,(f->child,level)）;//左孩子及层数入队if(f->rchild!=NULL)enqueue（Q,(f->rchild,level)）;
8、//右孩子及所在层入队}}//alg6
