一.學習總結(jié)(2分)

1.1樹結(jié)構(gòu)思維導圖

1.2 樹結(jié)構(gòu)學習體會

樹的前中后序遞歸操作的訪問路徑都如下圖

樹的層次遍歷的路徑則如下圖

操作{
進隊第一個節(jié)點，
while(隊不空）
{
訪問該節(jié)點，
if(BT->lchild！=NULL）進隊。
if(BT->rchild！=NULL）進隊。
}
}
三序遍歷的非遞歸（先序為例）：
操作：{
進棧樹的根節(jié)點；
while(棧不空）{
訪問之
if(BT->rchild！=NULL）進棧。
if(BT->lchild！=NULL）進棧。
}
}
前序中序建樹過程：
前：ABCEFD
中：BCEFAD
前序的第一個A：說明它是根節(jié)點
左前樹： BCEF 左中：BCEF
右前樹： D 右中：D
重復找左右樹。
結(jié)果如下圖

哈夫曼樹
如1357建樹：

細心觀察會發(fā)現(xiàn)其wpl與非葉子節(jié)點的和是相等的
數(shù)學證明：設(shè) a b c d e 幾個節(jié)點建立哈夫曼樹（假設(shè)每一個節(jié)點都比后加進來的節(jié)點大）
a+b為第一個非根節(jié)點 則a+b+c為第二個依次類推
會發(fā)現(xiàn)非葉子節(jié)點的和是e+2d+3c+4b+4a
而wpl也恰好是這個值
并非偶然這可以從哈夫曼樹的結(jié)構(gòu)來考慮因為每遞加一層已經(jīng)建立過的節(jié)點就加1比方說哈夫曼樹有三層那么最下面一層的和會在第二層次中被加也會在第一層被加也就是被
了兩次與wpl構(gòu)造數(shù)的算法完全一致。于是可運用貪心算法快速得到wpl。
樹是一種非線性結(jié)構(gòu)
樹形結(jié)構(gòu)不但本身很有用，還反映了許多計算過程的抽象結(jié)構(gòu)；
樹形結(jié)構(gòu)的結(jié)點形成一種層次結(jié)構(gòu)；
遞歸則是它的重點，但遞歸這種操作理解起來的難度真的很大，因此要多看看別人的代碼來學習。

二.PTA實驗作業(yè)（4分）

2.1 題目1：修理牧場

1 設(shè)計思路（偽代碼或流程圖）

定義一個隊列可以讓進隊元素按從大到小排列
for(i=0;i<N;I++){
依次輸入每一個數(shù)
并且入隊
}
while(隊不空）{
出隊兩個元素ab
并讓total=a+b；
再進隊兩個元素。
}
輸出結(jié)果

2.代碼截圖

3.PTA提交列表說明

2.1 題目2：朋友圈

1 設(shè)計思路（偽代碼或流程圖）

//定義三個數(shù)組一個是保留每一個每一個數(shù)對應的根節(jié)點一個保留所有根節(jié)點
//最后一個保留每一個根對應的孩子數(shù)
初始化樹中的每個節(jié)點數(shù)值為-1
先輸入孩子數(shù)和朋友圈數(shù)n,m
for(int i=0;i<m;i++){
輸入每個朋友圈中人的個數(shù)
并且保留它們的根節(jié)點
并且記錄每個下標對應的根節(jié)點
當這個根是其它根的孩子則將這個朋友圈的其他人的根都轉(zhuǎn)成這個跟
}
遍歷保留每個節(jié)點根的數(shù)組記錄總數(shù)在最后一個數(shù)組中
遍歷取最大值

2.代碼截圖

3.PTA提交列表說明

2.1 題目3：表達式樹

1 設(shè)計思路（偽代碼或流程圖）

//觀察表達式樹會發(fā)現(xiàn)數(shù)字字符的左孩子右孩子都是空的用于后面的表達式樹的運算
//創(chuàng)建兩個棧一個是樹節(jié)點的保存類型一個是字符保存棧
for(int i=0;str[i];i++){
if（字符是數(shù)字）創(chuàng)建樹節(jié)點并且入棧
else
{
if(字符棧棧頂優(yōu)先級小于str[i]){
則進棧字符棧
}
else if(字符棧棧頂優(yōu)先級大于str[i]){
出棧并且從節(jié)點棧中拿出兩個;
構(gòu)樹并且放回節(jié)點棧中
}
else{
直接出棧
}
}
計算表達式
{
if(BT->rchild==NULL&&BT->lchild==NULL)
return BT->data-'0'
else{
a=計算遍歷右樹
b=計算遍歷左樹
switch()
{
case '+':return a+b;
case  '-':return a-b
case '*':returna*b
case '/':return a/b
}
}

2.代碼截圖

3.PTA提交列表說明

3.3 我的總分：230

四. 閱讀代碼（必做，1分）

5-27 家譜處理 (30分)

#include <stdio.h>
#include<stdlib.h>
#include<string.h>
/* 評測結(jié)果 時間  結(jié)果  得分  題目  編譯器     用時（ms）  內(nèi)存（MB）  用戶
2016-08-30 10:31    全部正確    25  5-27    gcc     1   1   569985011
測試點結(jié)果 測試點   結(jié)果  得分/滿分   用時（ms）  內(nèi)存（MB）
測試點1    答案正確    18/18   1   1
測試點2    答案正確    2/2     1   1
測試點3    答案正確    5/5     1   1
測試點4    答案正確    5/5     1   1
查看代碼*/
typedef struct node *Node;
struct node {char Name[11];int space;int  Parant;
};Node Tree;
int n;int Scan(char*);
int Trace(int);
int judgeParent(int,int);//父子
int judgeSibling(int,int);//兄弟
int judgeAncestor(int,int);//祖先
void work();
int Index(char*);int main() {int m;scanf("%d%d",&n,&m);Tree=(Node)malloc(sizeof(struct node)*n);getchar();//清除緩存for(int i=0; i<n; i++) {Tree[i].space=Scan(Tree[i].Name);Tree[i].Parant=i;}Tree[0].Parant=-1;for(int i=0; i<m; i++) {work();getchar();}return 0;
}
int judgeParent(int x,int y) {if(Tree[x].Parant==x)Tree[x].Parant=Trace(x);return Tree[x].Parant==y;
}
int judgeSibling(int x,int y) {if(Tree[x].Parant==x)Tree[x].Parant=Trace(x);if(Tree[y].Parant==y)Tree[y].Parant=Trace(y);return Tree[x].Parant==Tree[y].Parant;
}
int judgeAncestor(int x,int y) {while(x!=-1) {if(judgeParent(x,y))return 1;else x=Tree[x].Parant;}return 0;
}void work() {char StrX[11],StrY[11],relation[11];scanf("%s%*s%*s%s%*s%s",StrX,relation,StrY);
//  printf("%s - %s - %s\n",StrX,relation,StrY);int X=Index(StrX);int Y=Index(StrY);
//  printf("%d   -    %d",X,Y);int result;switch(relation[0]) {case 'c':result=judgeParent(X,Y);break;case 'p':result=judgeParent(Y,X);break;case 's':result=judgeSibling(X,Y);break;case 'd':result=judgeAncestor(X,Y);break;case 'a':result=judgeAncestor(Y,X);break;default:result=-1;break;}if(result==1)printf("True\n");else if(!result)printf("False\n");
//  else printf("ERROR:系統(tǒng)不能識別所指定關(guān)系！\n");
}int Index(char*a) {for(int i=0; i<n; i++) {
//      printf("*");if(strcmp(Tree[i].Name,a)==0)return i;}
//  printf("ERROR:所給人名不存在！\n");return -1;
}int Trace(int child) { //往前遍歷第一個比他縮進少的就是他的父親for(int i=child-1; i>=0; i--) {if(Tree[i].space<Tree[child].space) {
//      printf("%d's parent is %d'",child,i);return i;}}return -1;//如果沒有，那么他就是亞當夏娃了。
}int Scan(char*p) {char c;int space=0;while((c=getchar())==' ')space++;//記錄字符串前面的空格數(shù)量do {*p++=c;} while((c=getchar())!='\n');*p='\0';return space;
}

這一題我一開始的想法就是先建立一個樹家譜關(guān)系樹，確實建立成功勒，但是后面的各個關(guān)系的處理判斷我就不會了.

這個輸入方式就可以忽略沒用的信息
然后就是從數(shù)組去尋找這兩個名字的位置后轉(zhuǎn)換為各個小問題的處理，
這種處理方式真的很容易非常巧妙還有就是它有保留家譜中每個人的信息是用數(shù)組處理的

五. 代碼Git提交記錄截圖

轉(zhuǎn)載于:https://www.cnblogs.com/m208231833/p/8994142.html

總結(jié)

以上是生活随笔為你收集整理的博客作业04--树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。