本章解答只给出算法描述,1~10题略 算法中二叉树的二叉存储结构描述如下: typedef struct BTNode datatype data struct BTNode *lchild.rchild I BTNode BiTree; 1对于下图所示二叉树,试给出: (1)它的顺序存储结构示意图 (2)它的二叉链表存储结构示意图 (3)它的三叉链表存储结构示意。 2证明:在结点数多于1的哈夫曼树中不存在度为1的结 3证明:若哈夫曼树中有n个叶结点,则树中共有2n-1 个结点 4证明:由二叉树的前序序列和中序序列可以唯一地确定 棵二叉树 5已知一棵度为m的树中有n1个度为1的结点,n2个度 为2的结点,……,nm个度为m的结点,问该树中共有多少个 叶子结点?有多少个非终端结点? (1题图) 6设高度为h的二叉树上只有度为0和度为2的结点,问 该二叉树的结点数可能达到的最大值和最小值。 7求表达式(a+b*(c-d))-e/f的波兰式(前缀式)和逆波兰式(后缀式) 8画出和下列己知序列对应的二叉树 二叉树的先序次序访问序列为: GEKDAIEBCHU; 二叉树的中序访问次序为: DIAEKECUHBG 9画出和下列已知序列对应的二叉树: 二叉树的后序次序访问序列为: CEEGDBJLKIHA 叉树的中序访问次序为: CBEFDGAUIKLH 10画出和下列已知序列对应的二叉树: 二叉树的层次序列为: ABCDEEGHIJ; 二叉树的中序次序为: DBGEHJACIE。 给定一棵用二叉表示的二叉树,其根指针为root。试写出求二叉树结点的数目的算法(递归算法 或非递归算法) int count BiTree t if(t==NULL) return(O) return(count(t->lchild)+count(t->rchild)+1)本章解答只给出算法描述，1~10 题略。 算法中二叉树的二叉存储结构描述如下： typedef struct BTNode{ datatype data; struct BTNode *lchild,*rchild; }BTNode ,*BiTree; ⒈对于下图所示二叉树，试给出： ⑴它的顺序存储结构示意图； ⑵它的二叉链表存储结构示意图； ⑶它的三叉链表存储结构示意。 ⒉证明：在结点数多于 1 的哈夫曼树中不存在度为 1 的结 点。 ⒊证明：若哈夫曼树中有 n 个叶结点，则树中共有 2n－1 个结点。 ⒋证明：由二叉树的前序序列和中序序列可以唯一地确定 一棵二叉树。 ⒌已知一棵度为 m 的树中有 n1 个度为 1 的结点，n2 个度 为 2 的结点，……，nm 个度为 m 的结点，问该树中共有多少个 叶子结点？有多少个非终端结点？ ⒍设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，问 该二叉树的结点数可能达到的最大值和最小值。 ⒎求表达式（a＋b*（c－d））－e/f 的波兰式（前缀式）和逆波兰式（后缀式）。 ⒏画出和下列已知序列对应的二叉树： 二叉树的先序次序访问序列为：GFKDAIEBCHJ； 二叉树的中序访问次序为：DIAEKFCJHBG。 ⒐画出和下列已知序列对应的二叉树： 二叉树的后序次序访问序列为：CFEGDBJLKIHA； 二叉树的中序访问次序为：CBEFDGAJIKLH。 ⒑画出和下列已知序列对应的二叉树： 二叉树的层次序列为：ABCDEFGHIJ； 二叉树的中序次序为：DBGEHJACIF。 ⒒给定一棵用二叉表示的二叉树，其根指针为 root。试写出求二叉树结点的数目的算法（递归算法 或非递归算法）。 int count (BiTree t) { if (t= =NULL) return (0); else return (count(t->lchild)+count(t->rchild)+1); A D B G E H C F ( 1 题图)