求二叉树的带权路径长度问题

    	二叉树是n(n>=0)个节点的有限集合:
    	1 或者为空二叉树,即n=0
    	2 或者由一个根结点和两个互不相交的的被称为根的左子树和根的右子树组成。其中左子树和右子树又分别是一个二叉树。

    	二叉树的带权路径长度为每个叶子结点的深度与权值之积的总和。

    先序遍历的时候需要采用递归调用来进行二叉树的遍历,把每个结点的深度作为递归函数的一个参数进行传递.具体步骤如下:
    若当前访问结点是叶结点,则总长度加上该结点的深度与权值之积
    若该结点是非叶结点,若左子树不为空,递归调用左子树,若右子树不为空,递归调用右子树,直至最后返回总长度

    typedef struct BiNode{
    	int weight;
    	struct BiTNode *lchild,rchild;
    }BiNode,*BiTree;

    int  Pre_Weight(BiTree root,int deep){
      static  int sum=0;
      if(root->lchild==NULL && root->rchild==NULL){
      	sum=sum+deep*root->weight;
       }
      if(root->lchild !=NULL){
    Pre_Weight(root->lchild,deep++);
       }
      if(root->rchild !=NULL){
      	Pre_Weight(root->rchild,deep++);
       }
      return sum;
    }

    层次遍历的时候需要使用队列进行遍历,并记录当前的层数,具体步骤如下:
    当遍历到叶结点时候,总长度加上该结点的深度与权值之积。
    当遍历到非叶结点的时候,把该结点的子树加入到队列,当某结点为该层最后一个结点的时候,层数加一,队列为空的时候就返回总长度

    typedef struct BiNode{
    	int weight;
    	struct BiTNode *lchild,rchild;
    }BiNode,*BiTree;

    #define MaxSize 10000 				  //队列长度是情况而定
    int sum_LevelOrder(BiTree root){
    	BiTree queue[MaxSize];  		  //声明队列
    	int end1,end2;					  //队列首和尾指针
    	end1=end2=0;					  //定义了结点首指针指向对头元素,尾指针指向队尾元素的后一位元素 [很重要]
    	int sum=0,deep=0;				  //定义了带权路径长度和深度
    	BiTree currentNode,newcurrentNode //currentNode指向当前访问层的最后一个结点,newcurrentNode指向下一层的最后一个结点
    	currentNode=root;
    	newcurrentNode=NULL;
    	queue[end2]=root;				 //初始时根结点入队
    	end2++; 						 //队尾指针加一
    	while(end1!=end2){				 //队列不为空
     BiTree t = queue[end1++];		 //先赋值再加一	
     if(t->lchild==NULL && t->rchild==NULL){
       sum+=deep*t->weight;
     }
     if(t->lchild != NULL){
      queue[end2++]=t->lchild;
      newlastcurrentNode=t->lchild;
     }
     if(t->rchild != NULL){
      queue[end2++] = t->rchild;
      newcurrentNode = t->rchild;
     }
     if(t==currentNode){         	//当遍历到当前层的最后一个结点的时候就更新层
     currentNode=lastcurrentNode;   //把下一层的结点赋值给当前层,达到换层的作用
     deep+=1;
     }
      }
      return sum;
    }

    1 递归先序遍历的时候需要设置static关键字,来保证整个程序执行期间,总长度一直存在
    2 层次遍历的时候要抓住当前层的最后一个结点和下一层的最后的一个结点,作为层次遍历改变的临界情况
    3 层次遍历的时候涉及到循环,需要注意队列的队尾,队首指针的定义,涉及临界条件.需要注意