二叉树讲-基本运算及其实现.pptxVIP

?创建二叉树CreateBTNode(*b，*str)：根据二叉树括号表示法字符串str生成对应的二叉链存储结构b。?销毁二叉链存储结构DestroyBT(*b)：销毁二叉链b并释放空间。?查找结点FindNode(*b，x)：在二叉树b中寻找data域值为x的结点，并返回指向该结点的指针。7.4.1二叉树的基本运算概述归纳起来，二叉树有以下基本运算：7.4二叉树基本运算及其实现1/19

?找孩子结点LchildNode(p)和Rchild-Node(p)：分别求二叉树中结点*p的左孩子结点和右孩子结点。?求高度BTNodeDepth(*b)：求二叉树b的高度。若二叉树为空，则其高度为0；否则，其高度等于左子树与右子树中的最大高度加l。?输出二叉树DispBTNode(*b)：以括号表示法输出一棵二叉树。2/19

（1）创建二叉树CreateBTNode(*b，*str)7.4.2二叉树的基本运算算法实现由正确的二叉树括号表示串?二叉链存储结构逻辑结构存储结构映射正确的二叉树括号表示串中只有4类字符：单个字符：结点的值(：表示一棵左子树的开始)：表示一棵子树的结束，：表示一棵右子树的开始3/19

算法设计：LNR先构造根结点N，再构造左子树L，最后构造右子树R构造右子树R时，找不到N了，所以需要保存N而结点是按最近原则匹配的，所以使用一个栈保存NL4/19

①若ch=‘(’：则将前面刚创建的结点作为双亲结点进栈，并置k=1，表示开始处理左孩子结点；②若ch=‘)’：表示栈顶结点的左、右孩子结点处理完毕，退栈；③若ch=‘，’：表示开始处理右孩子结点，置k=2；④其他情况（结点值）：创建*p结点用于存放ch；当k=1时，将*p结点作为栈顶结点的左孩子结点；当k=2时，将*p结点作为栈顶结点的右孩子结点。用ch扫描采用括号表示法表示二叉树的字符串：5/19

121A(B(D(，G))，C(E，F))ABDC根据括号表示法字符串构造二叉链的演示二叉链创建完毕B∧∧D∧G∧C∧E∧∧F∧Abk=栈26/19

voidCreateBTNode(BTNode*b，char*str){//由str?二叉链bBTNode*St[MaxSize]，*p;inttop=-1，k，j=0;charch;b=NULL; //建立的二叉链初始时为空ch=str[j];while(ch!=\0) //str未扫描完时循环{switch(ch){ case(:top++;St[top]=p;k=1;break; //可能有左孩子结点，进栈 case):top--;break; case，:k=2;break; //后面为右孩子结点7/19

default: //遇到结点值p=(BTNode*)malloc(sizeof(BTNode)); p-data=ch;p-lchild=p-rchild=NULL; if(b==NULL) //p为二叉树的根结点 b=p; else //已建立二叉树根结点{switch(k){ case1:St[top]-lchild=p;break; case2:St[top]-rchild=p;break; }}}j++;ch=str[j]; //继续扫描str}}8/19

设f(b)销毁二叉链b：大问题。则f(b-lchild)销毁左子树，f(b-rchild)销毁右子树：两个小问题。（2）销毁二叉链DestroyBT(*b)：Nbb-lchildb-rchildf(b)：大问题f(b-lchild)：小问题f(b-rchild)：小问题递归模型如下：f(b)≡不做任何事件