数据机构教学笔记-第六章树和二叉树

D：D是具有相同特性的数据元素的集。R：D为空集，则称空树；否则当n>1时，其余结点可分为m(m>0)个互不相交的有 ,T,中每一棵子集本身又是一棵符合本定义的树，称为根root的子Root(T);Value(T,cur_e);Parent(T,cur_e);LeftChild(T,cur_e);RightSibling(T,cur_e);TreeEmpty(T);TreeDepth(T);TraverseTree(T,：InitTree(&T);CreateTree(&T,definition);Assign(T,cur_e,value);InsertChild(&T,&p,i,c);Desroy (&ClarTree(&T);D p,i);和子 之间为有向关子树之间是否存 系 第一个数据元素 根结点(无前驱最后一个据元素(无后继 森林：是m（m≥0）棵互相交的树的集合任何一棵非树是一Tree=其 root被称为根点，F被称为子树森二叉树或为空树；或是由一个根结点加上两分别称为左子树和右子树 Root(T);Value(T,e);Parent(T,LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());：InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);DeleteChild(T,p,LR);性质1：在二叉树的第i2i-1个结点(i≥1)必存在关系式：n0=n2+1满二叉树：指的是深度为k且含有2k-1个结点的二4n对二叉树中任意一个为i的结点：否则， 的结点为其双亲结点若2i+1>n，则该结点无右孩子结点，一、二叉树的顺序表#defineMAX_TREE_SIZE100 emTypeSqBiTree[MAX_TREE_SIZE];//0号单元根结SqBiTreekk个结点的单支树（树中不存在度为2）却需要长度为2k-1的一维数组。二、二叉树的链式表1.typedefstruct{emTypestructBiTNode*lchild,*rchild;BiTNode,*BiTree;typedefstruct{emTypestructTriTNode*lchild,*rchild;structTriTNode*parent;}TriTNode,typedefstruct{emTypeint*parent;charLRTag;}BPTNodetypedefstruct{intnum_node;//结点数目}BPTree（1）根结点根结点。voidPreorder(BiTreeT,void(*visit)(emType&if(T)visit(T->data);//结Preorder(T->lchild,visit)Preorder(T->rchild,visit);}}BiTNode*GoFarLeft(BiTreeT,Stack*S){if(!T)returnNULL;while(T->lchild{Push(S,T=T-}return}voidInorder_I(BiTreeT,void(*visit)(emType&{StacktGoFarLeft(T,S);while(t){visit(t->data);ift=GoFarLeft(t->rchild,elseif!StackEmpty(St=elset=}}voidCountLeaf(BiTreeT,int&count){if(T{if((!T->lchild)&&(!T->rchild))CountLeaf(T->lchild,count);CountLeaf(T->rchild,count);}}intDepth(BiTreeT){if(!T)depthval=0;{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+(depthLeft>}return}3、二叉树(后序遍历BiTNode*GetTreeNode(emTypeitem,BiTNode*lptr,BiTNode*rptr){if(!(T=T->data=T->lchild=T->rchild=NULL;returnT;}BiTNode*CopyTree(BiTNode{if(!T)returnNULL;if(T->lchild)newlptr=CopyTree(T-elsenewlptr=NULL;if(T->rchild)newrptr=CopyTree(T-elsenewrptr=newnode=GetTreeNode(T->data,newlptr,newrptr);returnnewnode;}4、建立二叉树的结StatusCreateBiTree(BiTree&T)（一个字符）if(ch=='')T=elseif(!(T=(BiTNode*)malloc(sizeof(BiTNode))))T->data=ch;//生成根结点CreateBiTree(T->lchild)CreateBiTree(T->rchild)}return}//-×+abc/d例如:已知表达式(a+b)×c–voidCrtExptree(BiTree&T,charexp[])//非空表达式树，其结构为二叉链表InitStack(S);Push(S,＇#＇);p=exp;ch=while(!(GetTop(S)==＇#＇&&ch==＇#＇))if(!IN(chOPCrtNode(t,ch{switch(ch){case＇(＇:Push(S,ch);break;case＇)＇:{Pop(S,while(c!=＇(＇break;}defult:{while(!Gettop(S,c)&&({CrtSubtree(t,c);Pop(S,c);if(ch!=＇#＇)Push(S,ch);}//}//}//if(ch!=＇#＇){p++;ch=}//Pop(PTR,}//voidCrtNode(BiTree&T,charch)T=(BiTNode*)malloc(sizeof(BiTNode));T->data=T->lchild=T->rchild=NULLPush(PTR,T);}voidCrtSubtree(Bitree&T,charc)^T,T=(BiTNode*)malloc(sizeof(BiTNode));T->data=c;Pop(PTR,rc);T->rchild=rc;Pop(PTR,lc);T->lchild=Push(PTR,}例如:已知表达式的先缀表示式:×abc/d中缀表示式:ab×cd/＇abc＇右子树是＇d/e＇1.包含“线索”的结构，称作“线索链表”；typedefenum{Link,Thread}typedefstructBiThrNode{emTypestructBiThrNode*lchild,*rchild;PointerThrLTag,RTag;}BiThrNode,for(p=firstNode(T);p;p=Su))StatusInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(emType{p=T->lchild;//p指向根结点while(p!=T){//空树或遍历结束时while(p->LTag==Link)p=p-if(!Visit(p->data))returnERROR;//其左子树为空的结while(p->RTag==Thread&&p->rchild!=T)p=p->rchild;Visit(p->data);//后继结}pp->rchild;p}return}//StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT)if(!(Thrt(BiThrTree)malloc(sizeof(BiThrNode))exit(OVERFLOW);Thrt->LTag=Link;Thrt->RTag=Thread;//建头结点Thrt->rchildThrt;if(!T)Thrt->lchildThrt;elseThrt->lchild=T;pre=InThreading(T);pre->rchildThrt;pre->RTagThread;Thrt->rchild=}return}//voidInThreading(BiThrTreep){if(p){InThreading(p->lchild)if(!p->lchild)p->LTagThread;p->lchildpre;ifpre->rchild)pre->RTagThread;pre->rchildp;prep;prepInThreading(p->rchild);}}//#defineMAX_TREE_SIZEtypedefstructPTNode{Elemdata;intparent;}typedefstructPTNodeintr,n;}typedefstructCTNode{intchild;structCTNode}typedef{ElemChildPtrfirstchild;}typedefstructCTBoxintn,r;}三、树的二叉链表(孩子-兄弟）表示typedefstructElemstructCSNode*firstchild,}CSNode,设森林F=(T1,T2,⋯,TnT1=(root，t11,t12,⋯,二叉树B=(LBT,Node(root),RBT若F=Φ，则B=Φ;由ROOT(T1)对应得到由(t11,t12,⋯,t1m)对应得到(T2,T3,⋯,Tn)对应得到若B=Φ,则F=Node(root)ROOT(T1);由LBT对应得到(t11,t12,⋯，t1m);由RBT对应得到(T2,T3,⋯,Tn)先根(次序)遍历若森林不空，则森林中第一棵树的根结点;树的遍历和二叉树遍历的对应关系？intTreeDepth(CSTreeT)if(!T)return0;elseh1=TreeDepth(T->firstchild);h2=TreeDepth(T->nextsibling);return(max(h1+1,h2));}}//voidAllPath(BitreeT,Stack&S){if(T)Push(S,T->dataif(!T->Left&&!T->Right)PrintStack(S);else{AllPath(T->Left,S);AllPath(T->Right,S}}}//voidOutPath(BitreeT,Stack&S)while(!T)Push(s,T->dataif(!T-lchild)Printstack(s);elseOutPath(T->lchild,s);T=T-}//}//voidCreatTree(CSTree&TT=for(scanf(&fa,&ch);ch!=＇＇;scanf(&fa,&ch);){p=GetTreeNode(ch);if(fa==＇＇)T={while(s->data!=fa){DeQueue(Q,s);GetHead(Q,s);}if(!(s->firs