DS博客作业05--树

╰+哭是因爲堅強的太久メ 2021-11-29 05:28 201阅读 0赞

# 1.本周学习总结 #

### 1、思维导图 ###

![1475599-20190524225849117-799792744.png][]

### 2、对树结构的认识和学习体会 ###

通过这次对树的学习，这是第一次学习非线性结构的数据结构，之前都是学线性的，感觉有点不习惯，做题之后
    感觉线性和非线性的区别也就是遍历的方法不一样，以前线性结构遍历都是用循环，到了非线性结构遍历则都是
    用递归。树结构我觉得就分为两种多叉树和二叉树，二叉树结构体都是用左右孩子，而多叉树结构体都是孩子和
    兄弟，二叉树有三种遍历方式，先序遍历、中序遍历、后序遍历，通过这三种遍历来解决二叉树的问题。

## 2.PTA实验作业 ##

### 2.1.题目1：7-4 jmu-ds-二叉树叶子结点带权路径长度和 ###

### 2.1.1设计思路 ###

定义一个全局变量wpl存放叶子带权长度和
    输入str字符串;
    根据字符串建立一个根为bt的树;
    递归先序遍历树bt
        if(左右节点都为空)   //为叶子
               wpl += h* (b->data-'0')   //h为当前节点的高度

### 2.1.2代码截图 ###

![1475599-20190524230237047-378135418.png][]  
![1475599-20190524230249287-1614364376.png][]

### 2.1.3本题PTA提交列表说明 ###

![1475599-20190524230302991-939279644.png][]

Q1:部分错误，字符串的结束标志判断错误  
A1:在建树函数中刚开始第一个if中写的是i>MaxSize才返回空，正确应该是i>=MaxSize  
Q2:树的高度初始化错误  
A2:刚开始树的高度初始化为1，结果得不到正确的答案，初始高度设为零就正确了

### 2.2.题目2：7-5 jmu-ds-输出二叉树每层节点 ###

### 2.2.1设计思路 ###

输入字符串str
    根据str建立根为bt的二叉树
    LevelOrder函数层次便利二叉树
          if(根节点不为空)  将根节点入队
          while(队列不为空)
          {
                取队头元素p
                输出p->data
                出队
                将队头元素的左右孩子入队
          }

### 2.2.2代码截图 ###

![1475599-20190524230117331-570058516.png][]  
![1475599-20190524230136626-778411917.png][]  
![1475599-20190524230147641-1194933530.png][]

### 2.2.3本题PTA提交列表说明 ###

![1475599-20190524230204836-899810886.png][]

Q1:两次错误都是因为格式问题，没有控制好什么时候输出回车和层数  
A1:最后才发现输出回车的规律，新建一个节点q，刚开始让q等于根节点，当每次出队的节点等于q时就要输出回车  
并且输出回车时要让q等于现在的队尾节点

### 2.2.题目3：6-3 求二叉树高度 ###

### 2.2.1设计思路 ###

递归后序遍历二叉树
    if(节点为空)  return 0;
    leftHigh=GetHeight(BT->Left);         //leftHigh为左子树的高度
    rightHigh=GetHeight(BT->Right);    //rightHigh为右子树的高度
    比较leftHigh和rightHigh大小
           较大的数加一并作为返回值

这个算法从数的最底层开始算数的高度，最底层为0然后一级一级向上返回，每次返回的时候数值都加一

### 2.2.2代码截图 ###

![1475599-20190524230328883-758920238.png][]

### 2.2.3本题PTA提交列表说明 ###

![1475599-20190524230344757-442721909.png][]

Q1:多次编译错误  
A1:这些编译错误都是因为在编译器写代码的时候没有用题目给的结构体，定义的左右孩子名称不一样，  
虽然自己在编译器上可以运行，提交上去就是编译错误

# 3、阅读代码 #

## 3.1 题目 ##

## 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 ##

## 3.2 解题思路 ##

同样用到的是用到层次遍历的问题，不过这边没用到队列而是用到了vector这一c++中的容器，不过用法是跟队列相同的  
循环的顺序从队列不为空到vector不为空，每次将最有边的结点存入一个vector数组中，最后vector数组作为返回值并输出

## 3.3 代码截图 ##

![1475599-20190524231243265-421927110.png][]

## 3.4 学习体会 ##

学习到了vector的使用。从此代码中知道，在层次遍历二叉树的过程中，不仅可以用队列，还可以用vector数组，也多了解了c++STL容器中的一个类，  
感觉vector可能比栈和队列用的更广泛，而且vector可以解决数组浪费空间这一问题。

转载于:https://www.cnblogs.com/porphyra/p/10889729.html

[1475599-20190524225849117-799792744.png]: /images/20211129/7e68eb45cef84dac99e13d10bedb76d7.png
[1475599-20190524230237047-378135418.png]: /images/20211129/713dacf267d9453a9878e6ff998b147f.png
[1475599-20190524230249287-1614364376.png]: /images/20211129/723507f5b5394218a6f616f672c6e57d.png
[1475599-20190524230302991-939279644.png]: /images/20211129/7c6071b686ea4aecbaa7e7548c2b28c3.png
[1475599-20190524230117331-570058516.png]: /images/20211129/40310d8f6281420aac3569787a1c4162.png
[1475599-20190524230136626-778411917.png]: /images/20211129/d78ff4a2f0e74f51975afd3cfc421530.png
[1475599-20190524230147641-1194933530.png]: /images/20211129/d3c9dc1420934edb9744b1875ffc38f0.png
[1475599-20190524230204836-899810886.png]: /images/20211129/9138fc10d45b4959acad4123199ec84f.png
[1475599-20190524230328883-758920238.png]: /images/20211129/6fba85aa3ed14a7494e13b9855e79b81.png
[1475599-20190524230344757-442721909.png]: /images/20211129/14984d4c2d3941928dee9da89afa6809.png
[1475599-20190524231243265-421927110.png]: /images/20211129/d862bb0a12e84a95858dca0f8157c018.png