第四次作业4-树和二叉树

1.学习总结

1.1树结构思维导图

1.2 树结构学习体会

学不会,学不会,哪里都是问题,告辞。

2.PTA实验作业

2.1

7-1 还原二叉树(25 分)

7-8 jmu-ds-二叉树叶子结点带权路径长度和(25 分)

6-4 jmu-ds-表达式树(25 分)

2.2 设计思路(伪代码或流程图)

7-1 还原二叉树(25 分)

bt*findTree(char*a,char*b,int length)
先序遍历确定头结点,中序遍历确定叶节点和其双亲节点
{
if (is empty tree)
return null;
开辟一个bt结构的内存空间,分配给T
将b的值赋给T的data
for(i!=length)
{
寻找同一值
当在数组a里找到data的值时
break
}
分别递归访问T的左右子树
return T
}

int GetHeight(bt *T)
{
if(T==NULL)
return 0

else
{
递归访问左右子树
访问到叶子时返回,同时选出最长的一条路径
}
}

7-8 jmu-ds-二叉树叶子结点带权路径长度和(25 分)

BTree CreateBTree(int i)
{
设定BTree变量BT
if(i>str.size()-1)return NULL;
if(是'#',是空节点)return NULL;
为BT开辟一个空间
BT->data=str[i];
BT的lc应该是第2*i的元素
rc应该是第2*i+1的元素
return BT;

}

void GetWpl(BTree BT,int &wpl,int h)

{
定义h表示深度
先判断是否是叶子节点
if(BT->Left==NULL&&BT->Right==NULL)
{
wpl=深度*当前data的值
深度归零
}
h++
若是空节点,return
非空非叶
递归访问其左右子树
GetWpl(BT->Left,wpl,h);
GetWpl(BT->Right,wpl,h);
}

6-4 jmu-ds-表达式树(25 分)

void InitExpTree(BTree &T,string str)
{
    定义栈shu保存树的节点
    定义栈ch保存字符
    ch底为'#'
    while(str[i])
    {
        if(是数字)
        {
            数字是叶子节点,创造叶子节点,i++ 
        }
        else
        {
            分为三种情况
            if(栈顶<字符串)
            {
                入栈,i++; 
            } 
            else if(=)
            {
                是左括号,直接出栈即可 
            } 
            else
            {
                将ch的第一个出栈,shu的前两个出栈
                并将两个节点存为其右、左子树
                将双亲节点压回shu栈  
            }
        } 
    }
    while(ch.top()!='#')
    {
        重复>时的操作 
    } 
}

2.3 代码截图

7-1 还原二叉树(25 分)

7-8 jmu-ds-二叉树叶子结点带权路径长度和(25 分)

6-4 jmu-ds-表达式树(25 分)

2.4 PTA提交列表说明。

7-1 还原二叉树(25 分)

一开始跳了函数题来做这个,结果死活建不起来树。学习了一个以后,先序遍历可以确定根节点的位置,中序遍历可以确定两个子结点的双亲结点。返回高度是比较简单的部分。

7-8 jmu-ds-二叉树叶子结点带权路径长度和(25 分)

一开始用int 类型返回wpl的值,结果一直无法调用。整个过程十分痛苦,后经广哥点拨,设了一个全局变量。

6-4 jmu-ds-表达式树(25 分)

一开始用数循环次数的方法,排除了建树函数的错误。但计算值的函数老是溢出,经过多番排查之后,问题出在我忘记把确定左右子树的双亲结点重新入栈了。

除法的时候,一开始用return,但是会返回值,后来看了广哥的代码,用了exit(虽然在编译器里无法编译)

3.截图本周题目集的PTA最后排名

分数:2

4. 阅读代码(必做)

用递归的方法,同时确定两个树的孩子节点是否相同。

5. 代码Git提交记录截图

原文地址:https://www.cnblogs.com/3nodisnoable/p/8990374.html