6.5.1 常用的二叉树遍历算法 (1).pptx

6.5二叉树的遍历6.5.1常用的二叉树遍历算法二叉树的遍历是指按一定的次序访问树中的所有结点，使每个结点恰好被访问一次。其中遍历次序保证了二叉树上每个结点均被访问一次且仅有一次。二叉树常用的遍历有先序（根）遍历、中序（根）遍历、后序（根）遍历和层次遍历。所谓先序、中序、后序，区别在于访问根结点的顺序。6.5二叉树的遍历

若二叉树非空，则：①访问根结点；②先序遍历左子树；③先序遍历右子树。voidPreOrder(BTNode*bt){if(bt!=NULL){ printf(%c,bt-data); PreOrder(bt-lchild); PreOrder(bt-rchild);}}先序遍历序列的特点：其第一个元素值为二叉树中根结点值。1．先序遍历6.5二叉树的遍历

若二叉树非空，则：①中序遍历左子树；②访问根结点；③中序遍历右子树。voidInOrder(BTNode*bt){if(bt!=NULL){ InOrder(bt-lchild); printf(%c,bt-data); InOrder(bt-rchild);}}中序遍历序列的特点：若已知二叉树的根结点值，以该值为界，将中序遍历序列分为两部分，前半部分为左子树的中序遍历序列，后半部分为右子树的中序遍历序列。2．中序遍历6.5二叉树的遍历

若二叉树非空，则：①后序遍历左子树；②后序遍历右子树；③访问根结点。voidPostOrder(BTNode*bt){if(bt!=NULL){ PostOrder(bt-lchild); PostOrder(bt-rchild); printf(%c,bt-data);}}后序遍历序列的特点：最后一个元素值为二叉树中根结点值。3．后序遍历6.5二叉树的遍历

层次遍历是从根结点出发，按照从上向下，同一层从左向右的次序访问所有的结点。采用层次遍历得到的访问结点序列称为层次遍历序列。层次遍历序列的特点：其第一个元素值为二叉树中根结点值。4.层次遍历算法6.5二叉树的遍历

在层次遍历算法中采用一个循环队列qu来实现。层次遍历算法的实现过程：先将根结点进队，在队不空时循环：从队列中出队一个结点p，访问它；若它有左孩子结点，将左孩子结点进队；若它有右孩子结点，将右孩子结点进队。如此操作直到队空为止。6.5二叉树的遍历

voidLevelOrder(BTNode*bt){BTNode*p;BTNode*qu[MaxSize]; //定义循环队列,存放二叉链结点指针intfront,rear; //定义队头和队尾指针front=rear=0; //置队列为空队列rear++;qu[rear]=bt; //根结点指针进入队列while(front!=rear) //队列不为空循环{ front=(front+1)%MaxSize; p=qu[front]; //出队结点p printf(%c,p-data); //访问该结点 if(p-lchild!=NULL) //有左孩子时将其进队 {rear=(rear+1)%MaxSize; qu[rear]=p-lchild; } if(p-rchild!=NULL) //有右孩子时将其进队 {rear=(rear+1)%MaxSize; qu[rear]=p-rchild; }}}6.5二叉树的遍历