数据结构与算法-ch5tree.ppt

while (top!=-1 flag==1) { b=St[top]; //取出当前的栈顶元素 if (b-rchild==p) { printf(%c ,b-data); //访问*b结点 top--;p=b; //p指向则被访问的结点 } else { b=b-rchild; //b指向右孩子结点 flag=0; //设置未被访问的标记 } } //end of while (top!=-1 flag==1) } while (top!=-1); } b的右孩子不存在或已访问过 从上述过程可知，栈中保存的是当前结点*b的所有祖先结点（均未访问过）。 例如，书中例子求一个结点的所有祖先结点。 5.5.1 二叉树的基本运算概述 （Basic operations of binary tree) 5.5.2 二叉树的基本运算算法实现 (Algorithm implementation of basic operations) 5.5 二叉树的基本运算及其实现 (Algorithm implementation and basic operations of binary tree) 归纳起来,二叉树有以下基本运算： (1)创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str生成对应的链式存储结构。 (2)查找结点FindNode(*b,x)：在二叉树b中寻找data域值为x的结点,并返回指向该结点的指针。 (3)找孩子结点LchildNode(p)和RchildNode(p)：分别求二叉树中结点*p的左孩子结点和右孩子结点。 5.5.1 二叉树的基本运算概述 （Basic operations of binary tree) (4)求高度BTNodeDepth(*b)：求二叉树b的高度。若二叉树为空,则其高度为0；否则,其高度等于左子树与右子树中的最大高度加l。 (5)输出二叉树DispBTNode(*b)：以括号表示法输出一棵二叉树。 (1) 创建二叉树CreateBTNode(*b,*str) 用ch扫描采用括号表示法表示二叉树的字符串。分以下几种情况： ① 若ch=(：则将前面刚创建的结点作为双亲结点进栈,并置k=1,表示其后创建的结点将作为这个结点的左孩子结点； ② 若ch=)：表示栈中结点的左右孩子结点处理完毕,退栈； ③ 若ch=,：表示其后创建的结点为右孩子结点； 5.5.2 二叉树的基本运算算法实现 (Algorithm implementation of basic operations) ④ 其他情况,表示要创建一个结点,并根据k值建立它与栈中结点之间的联系, 当k=1时,表示这个结点作为栈中结点的左孩子结点,当k=2时,表示这个结点作为栈中结点的右孩子结点。如此循环直到str处理完毕。 算法中使用一个栈St保存双亲结点,top为其栈指针,k指定其后处理的结点是双亲结点(保存在栈中)的左孩子结点(k=1)还是右孩子结点(k=2)。 void CreateBTNode(BTNode * b,char *str) { BTNode *St[MaxSize],*p=NULL; int top=-1,k,j=0; char ch; 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; /*为孩子结点右结点*/ default:p=(BTNode *)malloc(sizeof(BTNode)); p-data=ch;p-lchild=p-rc