第8周树和二叉树（上）第5讲-二叉树基本运算及其实现.pdf
创建创建二叉树二叉树CreateBTNode(*b,*str)：根据二叉树括号根据二叉树括号表示表示法字符串法字符串 str生成生成对应对应的二叉链存储结构的二叉链存储结构b。 销毁二叉链存储结构销毁二叉链存储结构DestroyBT(*b)：销毁二叉链销毁二叉链b并释放空间并释放空间。 查找查找节点节点FindNode(*b,x)：在二叉树在二叉树b中寻找中寻找data域值为域值为x的节点的节点， 并返回指向该节点的并返回指向该节点的指针指针。 （1）创建二叉树创建二叉树CreateBTNode(*b,*str) 由正确的二叉树括号表示串由正确的二叉树括号表示串二叉链存储结构二叉链存储结构 逻辑结构逻辑结构存储结构存储结构 映射映射 正确的二叉树括号表示串中只有正确的二叉树括号表示串中只有4类字符：类字符： 单个字符单个字符：节点的值：节点的值 (：表示：表示一一棵左子棵左子树的开始树的开始 )：表示一棵子树的结束：表示一棵子树的结束 ,：表示一棵右表示一棵右子子树的开始树的开始 算法设计：算法设计： L N R 先构造先构造根节点根节点N，再再构造构造左子树左子树L，最后，最后构造构造右右子树子树R 构造构造右右子树子树R时，找不到时，找不到N了，所以需要保存了，所以需要保存N 而节点是按最近原则匹配的，所以使用一个而节点是按最近原则匹配的，所以使用一个栈栈保存保存N L 若若ch=(：则将前面刚创建的节点作为双亲节点进栈，并置则将前面刚创建的节点作为双亲节点进栈，并置k=1，表示开始处表示开始处 理理左左孩子节点；孩子节点； 若若ch=)：表示栈顶节点的：表示栈顶节点的左、右左、右孩子节点处理完毕，退栈；孩子节点处理完毕，退栈； 若若ch=,：表示开始处理表示开始处理右右孩子节点，置孩子节点，置k=2； 其他情况（其他情况（节点值节点值）：）： 创建创建*p节点用于存放节点用于存放ch； 当当k=1时时，将将*p节点作为栈顶节点的左孩子节点；节点作为栈顶节点的左孩子节点； 当当k=2时时，将将*p节点作为栈顶节点的右孩子节点节点作为栈顶节点的右孩子节点。 用用ch扫描采用括号表示法表示二叉树的字符串：扫描采用括号表示法表示二叉树的字符串： 1 2 1 A ( B ( D ( , G ) ) , C ( E , F ) ) A B D C 根据括号表示法字符串构造二叉链根据括号表示法字符串构造二叉链的演示的演示 二叉链创建完毕二叉链创建完毕 B D G C E F A b k = 栈栈 2 void CreateBTNode(BTNode * int top=-1, k , j=0; char ch; b=NULL;/建立的建立的二二叉链初始叉链初始时为空时为空 ch=strj; while (ch!=0)/str未扫描完时循环未扫描完时循环 switch(ch) case (: top+; Sttop=p; k=1; break;/可能有左可能有左孩子孩子节点节点，进栈进栈 case ): top-; break; case ,: k=2; break;/后面为右孩子节点后面为右孩子节点 default:/遇到节点值遇到节点值 p=(BTNode *)malloc(sizeof(BTNode); p-data=ch; p-lchild=p-rchild=NULL; if (b=NULL)/p为二叉树的根节点为二叉树的根节点 b=p; else/已建立二叉树根节点已建立二叉树根节点 switch(k) case 1: Sttop-lchild=p; break; case 2: Sttop-rchild=p; break; j+; ch=strj;/继续扫描继续扫描str 设设f(b)销毁二叉链销毁二叉链b：大问题大问题。则则f(b- -lchild)销毁左子树销毁左子树， f(b- - rchild)销毁右子树：销毁右子树：两个小问题两个小问题。 （2）销毁二叉链）销毁二叉链DestroyBT(*b) N b b- -lchildb- -rchild f(b) ：大问题：大问题 f(b- -lchild) ：小问题：小问题f(b- -rchild) ：小问题：小问题 递归模型如下：递归模型如下： f(b) 不做任何事件不做任何事件若若b=NULL f(b) f(b-lchild)； f(b-rchild)； 其他情况其他情况 释放释放*b节点节点 对应的递归算法如下：对应的递归算法如下： 设设f(b，x)在二叉树在二叉树b中查找中查找值为值为x的的节点节点（唯一唯一）。找到找到后返后返 回其指针回其指针，否则返回否则返回NULL。 （3）查找节点查找节点FindNode(*b,x) N b b- -lchildb- -rchild f(b，x) ：大问题：大问题 f(b- -lchild，x) ：小问题：小问题f(b- -rchild，x) ：小问题：小问题 递归模型如下：递归模型如下： f(b,x) = NULL若若b=NULL f(b,x) = b若若b-data=x f(b,x) = p若若在左子树中找到了，即在左子树中找到了，即p=f(b-lchild,x)且且p!=NULL f(b,x) = f(b-rchild,x)其他其他情况情况 对应的递归算法如下：对应的递归算法如下： （4）找孩子节点找孩子节点LchildNode(p)和和RchildNode(p) 直接直接返回返回*p节点的左孩子节点或右孩子节点的指针节点的左孩子节点或右孩子节点的指针。 （5）求高度求高度BTNodeDepth(*b) f(b) = 0b=NULL f(b) = MAXf(b- -lchild),f(b- -rchild)+1 其他其他情况情况 求二叉树的高度的递归模型求二叉树的高度的递归模型f(b)如下：如下： N b b- -lchildb- -rchild f(b) ：大问题：大问题 f(b-rchild) ：小问题：小问题 f(b-lchild) ：小问题：小问题 int BTNodeDepth(BTNode *b) int lchilddep,rchilddep; if (b=NULL) return(0);/空树的高度为空树的高度为0 else lchilddep=BTNodeDepth(b-lchild); /求左子树的高度为求左子树的高度为lchilddep rchilddep=BTNodeDepth(b-rchild); /求右子树的高度为求右子树的高度为rchilddep return(lchilddeprchilddep)? (lchilddep+1):(rchilddep+1); 对应的递归算法如下：对应的递归算法如下： （6）输出二叉树输出二叉树DispBTNode(*b) 二叉树的二叉链二叉树的二叉链二叉树的括号表示二叉树的括号表示 逻辑结构逻辑结构存储结构存储结构 输出输出 void DispBTNode(BTNode *b) if (b!=NULL) printf(%c,b-data); if (b-lchild!=NULL | b-rchild!=NULL) printf(); DispBTNode(b-lchild);/递归处理左子树递归处理左子树 if (b-rchild!=NULL) printf(,); DispBTNode(b-rchild);/递归处理右子树递归处理右子树 printf(); 根节点根节点 （ 左子树左子树，右子树右子树） 括号表示括号表示 本讲完本讲完
