河北大学：《数据结构》课程教学资源（习题解答）第六章 二叉树

本章解答只给出算法描述,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 题图)

12请设计一个算法,要求该算法把二叉树的叶结点按从左至右的顺序链成一个单链表。二叉树按 1 child-rchi1d方式存储,链接时用叶结点的rchi1d域存放链指针。 void childLink (Bitree t, BiTree * L, BTNode * rear) if(t) if(>lchild==NULL & t->rchild==NULL) if (rear==NULL) reart rear->rchild=t reart childlink(t->lcild) childLink(t->rchild); return l); 13给定一棵用链表表示的二叉树,其根结点root。试写出求二叉树的深度的算法。 int high (BiTree t) if (t==NULL) return(O) hl=high(t->lchild); hrhigh(t->rchild) return(max(hl,hr)+1) 14给定一棵用链表表示的二叉树,其根指针为root。试写出求二叉树各结点的层数的算法。 void fun (BiTree t, int n)

} ⒓请设计一个算法，要求该算法把二叉树的叶结点按从左至右的顺序链成一个单链表。二叉树按 lchild-rchild 方式存储，链接时用叶结点的 rchild 域存放链指针。 void childLink(BiTree t, BiTree *L, BTNode *rear) { if (t) { if (t->lchild= =NULL && t->rchild= =NULL) if (rear= =NULL) { *L=t; rear=t; } else { rear->rchild=t; rear=t; } childLink(t->lcild); childLink(t->rchild); } return(L); } ⒔给定一棵用链表表示的二叉树，其根结点 root。试写出求二叉树的深度的算法。 int high(BiTree t) { if (t= =NULL) return(0); hl=high(t->lchild); hr=high(t->rchild); return(max(hl,hr)+1); } ⒕给定一棵用链表表示的二叉树，其根指针为 root。试写出求二叉树各结点的层数的算法。 void fun(BiTree t, int n) {

if(t==NULL) coudatalchild, n+1); fun(t->rchild, n+1) 15给定一棵用链表表示的二叉树,其根指针为root。试写出将二叉树中所有结点的左、右子树相互 交换的算法。 void process(BiTree t) if(t==NULL) s(t->lchild) s(t->rchild) t->lchildt->rchild return 16.一棵n个结点的完全二叉树以向量作为存储结构,试设计非递归算法对该完全二叉树进行前序遍历 void PreOrder( datatype data[n+1])/*0号单元未用* It stack nt to if (n0) while(t<=n) Visite(data tD stacktop]=t top++

if (t= =NULL) return; else { coutdatalchild,n+1); fun(t->rchild,n+1); } } ⒖给定一棵用链表表示的二叉树，其根指针为 root。试写出将二叉树中所有结点的左、右子树相互 交换的算法。 void process (BiTree t ) { if (t= =NULL) return; process(t->lchild); process(t->rchild); t->lchildt->rchild; return; } ⒗一棵n个结点的完全二叉树以向量作为存储结构，试设计非递归算法对该完全二叉树进行前序遍历。 void PreOrder (datatype data[n+1]) /*0 号单元未用*/ { int stack[n] ; int top; if (n0) { while (t<=n) { Visite(data[t]); stack[top]=t; top++;

if (topdata==x) while(! empty Stack(s) pop(s, q); coutdatalchild

t=t*2; } if (topdata= =x) { while (!Empty_Stack(s)) { pop(s,q); coutdatalchild;

if (! Empty Stack(s) pop(s, r); p=r->rchild else return 18己知一棵二叉树的后序遍历序列和中序遍历序列,写出可以唯一确定一棵二叉树的算法 void InPost(char in[ l, char post[], int il, int ir, int pl, int pr, BiTree*t) *t=new BinOde t->data=post[pr while (in[m]= postlprD) m++; *t->lchild=NULL in InPost(in, post, 1l, m-1,pl, pl+m-1-il,&(*t->lchild) (m==ir) *t->rchild=NULL In Post(in, post, m+1, ir, pr-ir+m, pr-1, &(*t->rchild)); 19在中序线索二叉树上插入一个结点p作为树中某结点q的左孩子,试给出实现上述要求的算法 算法略 20给出在中序线索二叉树上删除某结点p的左孩子结点的算法 算法略

} if (!Empty_Stack(s)) { pop(s,r); p=r->rchild; } else return; } } ⒙已知一棵二叉树的后序遍历序列和中序遍历序列，写出可以唯一确定一棵二叉树的算法。 void InPost(char in[ ], char post[ ], int il, int ir, int pl, int pr, BiTree *t) { *t=new BiTNode; *t->data=post[pr]; m=il; while (in[m]!= post[pr]) m++; if (m== il) *t->lchild=NULL; else InPost(in, post,il,m-1,pl,pl+m-1-il, &(*t->lchild)); if (m= =ir) *t->rchild=NULL; else InPost(in,post,m+1,ir,pr-ir+m,pr-1,&(*t->rchild)); } ⒚在中序线索二叉树上插入一个结点 p 作为树中某结点 q 的左孩子，试给出实现上述要求的算法。 算法略 ⒛给出在中序线索二叉树上删除某结点 p 的左孩子结点的算法。 算法略