二叉树近年原文.ppt

先序遍历二叉树算法是:

若二叉树为空，则遍历结束；

否则

访问根结点(D)；

先序遍历左子树(L)；

先序遍历右子树(R)。后序遍历二叉树算法是:若二叉树为空，则遍历结束；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根结点(D)。中序遍历二叉树算法：

若二叉树为空，则遍历结束；

否则:

中序遍历左子树(L)；

访问根结点(D)；

中序遍历右子树(R)。中序遍历中序遍历序列：BDACvoidInOrder(BiTreebt){if(bt==NULL)return;InOrder(bt-lchild);Visit(bt-data);InOrder(bt-rchild);}ADBC后序遍历后序遍历序列：DBCAvoidPostOrder(BiTreebt){if(bt==NULL)return;PostOrder(bt-lchild);PostOrder(bt-rchild);Visit(bt-data);}ADBC-+/a*b-efcd先序遍历：中序遍历：后序遍历：层次遍历：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef1、画出和下列已知序列对应的二叉树1）先序序列GFKDAIEBCHJ中序序列DIAEKFCJHBG2）后序序列CFEGDBJLKIHA中序序列CBEFDGAJIKLH2、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为。3、某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则前序序列是。4、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是。5、画出一棵二叉树：该二叉树中每个结点均用一个字符表示，若一个结点的左子树或右子树为空，用#表示，现前序遍历二叉树，访问的结点的序列为ABD#G###CE#H##F##。41．对于前序遍历与中序遍历结果相同的二叉树为（1）;对于前序遍历和后序遍历结果相同的二叉树为（2）。A一般二叉树B只有根结点的二叉树C根结点无左孩子的二叉树D根结点无右孩子的二叉树E所有结点只有左子树的二叉树F所有结点只有右子树的二叉树42．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树43．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同B．完全相同C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同6-3-2二叉树遍历的非递归实现先序遍历的非递归算法intNRPreOrder(BiTreebt){BiTreestack[MAXNODE],p;inttop;if(bt==NULL)return1;top=-1;p=bt;while(!(p==NULLtop==-1)){while(p!=NULL){Visit(p-data);if(topMAXNODE-1){top++;stack[top]=p;}elsereturn0;p=p-lchild;}if(top==-1)return1;else{p=stack[top];top--;p=p-rchild;}}}在二叉树的先序、中序或后序遍历得到的线性序列中，两个相邻的结点满足前驱与后继的线性关系。