nt.cpp

一个数字塔的小程序

//关于动态规划求解数字塔问题
//如题，把这个也顺便粘上来。
/*［思路］
构造一个特殊的二叉树。从最底层起，采用广度优先策略，依次计算每层每个节点的权值。
权值的计算采用如下方法：点A拥有B和C两个子节点。A＝A＋Max（B，C）。
计算完权值之后，在Max（B，C）处打上标记，以便输出最大路径。树的广度优先采用了一个队列。
*/
#include <stdlib.h>
#include <stdio.h>
//#include "stdafx.h"
int m=0;
typedef struct node
{
 int num;//此点的权值
 int temp;//计算到此点时的临时权值
 bool mark;
 struct node * leftfather;//父结点
 struct node * rightfather;
  //如果结点A的左子是B，那么B的右父就是A
 struct node * leftchild;//左子结
 struct node * rightchild;//右子结
}node,*link;
//二叉树的结构
typedef struct queue
{
 struct node * data;//指向一个二叉树节点
 struct queue * next;//指向队列下一点
}queue,*lq;
void initn(link &l)
{
 l=(link)malloc(sizeof(node));
 l->mark=false;
 l->leftchild=0;
 l->leftfather=0;
 l->num=0;
 l->rightchild=0;
 l->rightfather=0;
 l->temp=0;
}//初使化二叉树的一个节点
void initq(lq &q)
{
 q=(lq)malloc(sizeof(queue));
 q->data=0;
 q->next=0;
}//初使化队列的一个节点
void input(link &tree)
//用来输入数据并构造数字塔的函数
{
 int i,j,t;
 link l1=tree,l2;
 lq Q,q1,q2,qt;
 initq(Q);
 Q->data=l1;
 q1=Q;q2=Q;
 Q->next=0;
 printf("请输入数字塔的层数");
 scanf("%d",&m);
 if(m>0)
 {
     for(i=1;i<=m;i++)
     {
      for(j=1;j<=i;j++)
      {
       printf("请输入第%d层第%d个数字！",i,j);
       scanf("%d",&t);
       l1=q1->data;//当前节点是队列首
       if(j==1)
       {
        initn(l2);
        l1->leftchild=l2;
        //如果当前输入的是此层最左节点
        //那么为当前节点的左子新建一节点
       }
       else
       {
        l1->leftchild=l1->leftfather->leftchild->rightchild;
        //否则，当前节点的左子为当前节点左兄的右子
       }
       initn(l2);
       l1->rightchild=l2;
    //构造当前节点的右子
       l1->leftchild->rightfather=l1;
       l1->rightchild->leftfather=l1;
    //子节点的父的对应
       initq(qt);
       q2->next=qt;
                q2->next->data=l1->leftchild;
       q2=q2->next;
       //将当前节点的左子放入队列尾
       if(j==i)
       {
        initq(qt);
        q2->next=qt;
        q2->next->data=l1->rightchild;
        q2=q2->next;
        //如果当前节点是此层的最后一个节点
        //那么把当前节点的右子放入队列尾
       }
       l1->num=t;
       l1->temp=t;
       //Q=q1->next;
       //free(q1);
       q1=q1->next;
      }
     }
    
     printf("您输入的数字塔如下图:\n");
     Q->data=tree;q1=Q;q2=Q;
     for(i=1;i<=m;i++)
     {
      for(j=1;j<=i;j++)
      {
       l1=q1->data;
       printf("%5d,",l1->num);
       initq(qt);
       q2->next=qt;
                q2->next->data=l1->leftchild;
       q2=q2->next;
       if(j==i)
       {
        initq(qt);
        q2->next=qt;
        q2->next->data=l1->rightchild;
        q2=q2->next;
        //如果当前节点是此层的最后一个节点
        //那么把当前节点的右子放入队列尾
       }
       q1=q1->next;
      }
      printf("\n");
     }//二叉树的显示
    }
    else
        printf("您输入的数字塔层数错误！\n");     
}
void path(link &tree)
{
 int i,j;
 link l1,l2;
 for(l1=tree;l1->leftchild->leftchild!=0;l1=l1->leftchild);
 //将l1定到最左叶节点
 for(i=m-1;i>0;i--)
 {
  for(j=1,l1=l1->rightfather;j<=i;l1=l2,j++)
  {
   l1->temp += l1->leftchild->temp > l1->rightchild->temp ?
    l1->leftchild->temp : l1->rightchild->temp;
   //当前节点的权值为它子节点中较大的与自己相加
   if(l1->leftchild->temp > l1->rightchild->temp)
   {
    l1->leftchild->mark=true;
    l1->rightchild->mark=false;
   }
   else
   {
    l1->rightchild->mark=true;
    l1->leftchild->mark=false;
   }//为较大的子节点做标记
   if(l1->rightfather!=NULL)
   {
                l2=l1->rightfather->rightchild;
   }
   else
   {
    l2=l1;
   }
  }//赋值
  //l1=l1->leftfather;
  for(;l1->leftfather!=NULL;l1=l1->leftfather->leftchild);
  //定位到上一层最左点
 }
 printf("最大权值路径为:%d",l1->num);
 for(l1=tree;l1->leftchild->leftchild!=0;l1=l2)
 {
  if(l1->leftchild->mark==true)
  {
   l2=l1->leftchild;
   printf("左");
  }
  else
  {
   l2=l1->rightchild;
   printf("右");
  }
  printf("->%d",l2->num);
 }
 printf("\n路径上的总权值为:%d\n",tree->temp);
}

void main(int)
{
	link tree;
	initn(tree);
	input(tree);
	if(m>0)
		path(tree);

	system("pause");
}