燕山楠的Homework 3

数据结构

---

T1

设该树中度数为$0$的结点有$x_0$个，度数为$1$的结点有$x_1$个，以此类推。设总结点个数为$n$。
则有

$$n=x_0+x_1+x_2+x_3+x_4$$
$$n-1=x_1+2x_2+3x_3+4x_4$$
代入$x_1=4,x_2=3,x_3=2,x_4=1$，联立以上方程解得$x=14,n=25$
综上，该树的总结点个数为$25$。

T2

由于$2^{6-1}=32>8$，故第$6$层只可能是完全二叉树的最下两层。
若是倒数第二层，则该层有$32-8=24$个非叶子结点，最多对应$48$个倒数第一层的结点。由于树的前$6$层是满的，故树结点个数最多为$2^6-1+48=111$。
若是倒数第一层，由于树的前$5$层是满的，故树节点个数最少为$2^5-1+8=39$。
综上，该完全二叉树的结点个数最多为$111$，最少为$39$。

T3

设该树中度数为$0$的结点有$x_0$个，度数为$1$的结点有$x_1$个，度数为$2$的结点有$x_2$个。设总结点个数为$n$。
由二叉树性质得，$x_0=x_2+1$，故由$x_0=50$得$x_2=49$。
由$n=x_0+x_1+x_2=99+x_1$可得，该二叉树的总结点数至少为$99$。

T4

（1）由于$2^9-1<892<2^{10}-1$，故该树共有$10$层，树的高度为$10$。
（2）由于树的结点数为偶数个，且完全二叉树的单支节点数只可能为$0$或$1$，所以单支节点数为$1$。
（3）由二叉树性质，$x_0=x_2+1，x_0+x_1+x_2=n$。代入$x_1=1,n=892$解得$x_0=446$,故叶子结点数为$446$。
（4）由于层序编号中非叶子结点一定在叶子结点前面，由非叶子结点个数为$892-446=446$，故最小的叶子结点的层序编号为$446+1=447$。

T5

已知树的先序序列为$NLR$，中序序列为$LNR$，后序序列为$LRN$。
（1）由题，$NLR=LNR$，由于$N$不能为空（非空二叉树），故$L$一定为空，即该树的所有结点没有左子树。
（2）由题，$LNR=NRL$，当$L$为空时该式也成立。
综上，满足题目条件的非空二叉树中，所有结点都没有左子树。

T6

能。由于该树是完全二叉树，我们可以根据序列的长度得出树的结点个数，然后直接画出树的形态。最后依据序列里的元素填数，即可唯一确定这棵二叉树。

T7

由题意构造出的哈夫曼树如附图所示。
由图可得，编码0、00不可能对应字母；编码001对应当前字母；前缀为001的编码不可能对应字母；前缀为1、01或000的编码一定对应其他字母（但不一定恰好是1、01、000，因为这个哈夫曼树还可以自叶子节点向外扩展）。
综上，（1）编码0、00和前缀为001的编码不可能对应其他字母；（2）前缀为1、01或000的编码肯定对应其他字母。

T8（核心代码：$Search$函数）

本题代码为T8代码。核心代码为$Search$函数。
输入的是二叉树对应的括号序列。
ps：检测程序输出结果正确性的方法是，先人工写出树的后序序列，再倒过来。

import java.util.*;//Stack在util里，不在util.Scanner里...
public class hw4_4
{
    public static class Node
    {
        char w;
        Node ls,rs;
        public Node(){ls=rs=null;}
        public Node(char ww){w=ww;ls=rs=null;}
    }
    public static class BTree//养成在类名前加static的好习惯
    {
        Node R;//Root,树的根结点
        String ans;
        public BTree(String str)//函数功能：初始化+根据输入的括号序列建树
        {
            R=null;
            ans="";
            Stack<Node> st=new Stack<>();
            Node t=null;//变量初始化！
            int n=str.length();
            boolean flag=true;//标识当前栈顶元素左孩子是否已处理过/跳过
            for(int i=0;i<n;i++)
            {
                char ch=str.charAt(i);
                switch(ch)
                {
                    case '(':st.push(t);flag=true;break;
                    case ')':st.pop();flag=false;break;//考虑到某些点没有右孩子，故置false
                    case ',':flag=false;break;
                    default:
                        t=new Node(ch);
                        if(R==null) R=t;//特判无根节点的情况！！！
                        else if(flag) st.peek().ls=t;
                        else st.peek().rs=t;
                        break;
                }
            }
        }
        public void Search(Node t)
        /*函数功能：得到答案序列
          由于后序序列格式是LRN，所以题目所求的序列为NRL。
          根据要求，我们先处理根结点，再处理右子树，最后处理左子树即可。*/
        {
            if(t==null) return;
            ans+=t.w+" ";
            Search(t.rs);Search(t.ls);
        }
    }
    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        String str=in.nextLine();
        BTree T=new BTree(str);
        T.Search(T.R);
        System.out.println(T.ans);
    }
}

T9（核心代码：$Search$函数）

本题代码为T9代码。核心代码为$Search$函数。
输入的是二叉树对应的括号序列。
ps：本题与上一题相比只多了一行代码QAQ

import java.util.*;
public class hw4_9
{
    public static class Node
    {
        char w;
        Node ls,rs;
        public Node(){ls=rs=null;}
        public Node(char ww){w=ww;ls=rs=null;}
    }
    public static class BTree
    {
        Node R;
        String ans;
        public BTree(String str)//函数功能：初始化+根据输入的括号序列建树
        {
            R=null;
            ans="";
            Stack<Node> st=new Stack<>();
            Node t=null;
            int n=str.length();
            boolean flag=true;
            for(int i=0;i<n;i++)
            {
                char ch=str.charAt(i);
                switch(ch)
                {
                    case '(':st.push(t);flag=true;break;
                    case ')':st.pop();flag=false;break;
                    case ',':flag=false;break;
                    default:
                        t=new Node(ch);
                        if(R==null) R=t;
                        else if(flag) st.peek().ls=t;
                        else st.peek().rs=t;
                        break;
                }
            }
        }
        public void Search(Node t)
        /*函数功能：得到答案序列
          由于要求从右到左，我们先遍历右子树，再遍历左子树。
          注意只把叶子结点加入输出结果即可。*/
        {
            if(t==null) return;
            if(t.ls==null&&t.rs==null) //唯一多出的一行
                ans+=t.w+" ";
            Search(t.rs);Search(t.ls);
        }
    }
    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        String str=in.nextLine();
        BTree T=new BTree(str);
        T.Search(T.R);
        System.out.println(T.ans);
    }
}

T10（核心代码：$Search$函数）

本题代码为T10代码。核心代码为$Search$函数。
输入的是二叉树对应的括号序列。

import java.util.*;
public class hw4_10
{
    public static class BTree
    {
        char[] T=new char[1000];//用顺序结构存储二叉树（空间开大点以防数组越界）
        int ans;
        public BTree(String str)
        /*函数功能：初始化+根据括号序列用顺序结构存下树
          这里连Stack都删了。因为对任意编号为i的点，双亲为(int)i/2，左二子为2i，右儿子为2i+1，结点跳转很方便，不需要用Stack来记忆双亲是谁。*/
        {
            ans=0;
            Arrays.fill(T,'#');//先把T所有元素初始化为#，这样就很容易判断是否越界、是否有儿子了
            int Now=1,n=str.length();
            for(int i=0;i<n;i++)
            {
                char ch=str.charAt(i);
                switch(ch)
                {
                    case '(':Now*=2;break;//进左儿子
                    case ')':Now/=2;break;//回到双亲结点
                    case ',':Now++;break;//进右儿子
                    default:T[Now]=ch;break;
                }
            }
        }
        public void Search(int t)
         /*函数功能：遍历全树统计答案
          其实随便按哪个顺序遍历都行，这里用了先序遍历。
          遇到双分支结点时统计答案即可。*/
        {
            if(T[t]=='#') return;//是#就代表越界
            if(T[t*2]!='#'&&T[t*2+1]!='#') ans++;//不是#就代表存在左/右儿子
            Search(t*2);Search(t*2+1);
        }
    }
    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        String str=in.nextLine();
        BTree T=new BTree(str);
        T.Search(1);//顺序结构存储下，1（不是0！）为根节点
        System.out.println(T.ans);
    }
}

T11（核心代码：$getCode$和$calcWPL$函数）

本题代码为T11代码。核心代码为$getCode$（对应第二小问）和$calcWPL$（对应第三小问）函数。
第一行输入$str$字符串。
第二行输入$w$数组。

//ps：以后不要开什么全局变量和全局函数，加static加到醉。。。把这些变量和函数都塞进一个static类中就没事了。
import java.util.*;
public class hw4_11
{
    static final int N=1000;
    public static class Node
    {
        int ch,w;
        Node lc,rc;
        public Node(int chh,int ww){ch=chh;w=ww;lc=rc=null;}
        public int getw(){return w;}
    }
    public static class Tree//养成类名通通加static的好习惯
    {
        Node R;//哈夫曼树的根
        int n;
        String str;
        int[] w=new int[N];
        char[] path=new char[N];//存当前遍历点对应的哈夫曼编码
        String[] Code=new String[N];//存给定字符（叶子结点）对应的哈夫曼编码
        public Tree(String str1,int[] w1)
        //函数功能：初始化各变量+建哈夫曼树+用二叉链存储结构存树
        {
            str=str1;w=w1;n=str.length();
            PriorityQueue<Node> Q=new PriorityQueue<>((a,b)->a.w-b.w);//按每个字符的w值从小到大排序的优先队列
            for(int i=0;i<n;i++) Q.offer(new Node(i,w[i]));
            while(Q.size()>1)
            {
                Node p=Q.poll(),q=Q.poll();
                Node t=new Node(-1,p.w+q.w);
                t.lc=p;t.rc=q;
                Q.offer(t);
            }
            R=Q.poll();
        }
        public void getCode(Node t,int d)
        //函数功能：求得每个字符对应的哈夫曼编码
        {
            if(t==null) return;
            if(t.lc==null&&t.rc==null)//哈夫曼树中只有叶子结点才对应字符
            {
                Code[t.ch]="";//编码初始化为空串
                for(int i=1;i<=d;i++) Code[t.ch]+=path[i];
            }
            d++;
            path[d]='0';getCode(t.lc,d);
            path[d]='1';getCode(t.rc,d);
        }
        public void printCode()
        //函数功能：输出每个字符对应的哈夫曼编码
        {
            System.out.print("The answer of task (2):");
            for(int i=0;i<n;i++) System.out.print(str.charAt(i)+":"+Code[i]+" ");
            System.out.println();
        }
        public int calcWPL(Node t,int d)
        //函数功能：计算该哈夫曼树的带权路径长度
        {
            if(t==null) return 0;
            int sum=0;
            if(t.lc==null&&t.rc==null) sum=w[t.ch]*d;
            d++;
            return sum+calcWPL(t.lc,d)+calcWPL(t.rc,d);
        }
    }
    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        String str=in.nextLine();
        int n=str.length();
        int[] w=new int[N];
        for(int i=0;i<n;i++) w[i]=in.nextInt();
        //实现第一小问的语句如下
        Tree T=new Tree(str,w);
        //实现第二小问的语句如下
        T.getCode(T.R,0);
        T.printCode();
        //实现第三小问的语句如下
        System.out.println("The answer of task (3):"+T.calcWPL(T.R,0));
    }
}