对于二叉树:
的几种遍历方式
1、先序遍历：先序遍历是先输出根节点，再输出左子树，最后输出右子树。上图的先序遍历结果就是：ABCDEF
2、中序遍历：中序遍历是先输出左子树，再输出根节点，最后输出右子树。上图的中序遍历结果就是：CBDAEF
3、后序遍历：后序遍历是先输出左子树，再输出右子树，最后输出根节点。上图的后序遍历结果就是：CDBFEA
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | #include <stdio.h>#include <stdlib.h>typedef char TelemType;typedef struct TNode{ TelemType data; struct TNode *lchild,*rchild;} BitNode;//声明BitNode* createTree(void);void preOrderTraverse(BitNode *);void inOrderTraverse(BitNode *);void lastOrderTraverse(BitNode *);int main(int agrc,char *argv[]){ BitNode *root=NULL; root=createTree(); printf("\n先序遍历二叉树:"); preOrderTraverse(root); printf("\n中序遍历二叉树:"); inOrderTraverse(root); printf("\n后序遍历二叉树:"); lastOrderTraverse(root); return 0;}//创建二叉树BitNode* createTree(void){ BitNode *b; TelemType ch; scanf("%c",&ch); if(ch=='#'){ b=NULL; }else{ b=(BitNode *)malloc(sizeof(BitNode)); b->data=ch; b->lchild=createTree(); b->rchild=createTree(); } return b;}//先序遍历void preOrderTraverse(BitNode *root){ if(root){ printf("%c",root->data); preOrderTraverse(root->lchild); preOrderTraverse(root->rchild); }}//中序遍历void inOrderTraverse(BitNode *root){ if(root){ inOrderTraverse(root->lchild); printf("%c",root->data); inOrderTraverse(root->rchild); }}//后序遍历void lastOrderTraverse(BitNode *root){ if(root){ lastOrderTraverse(root->lchild); lastOrderTraverse(root->rchild); printf("%c",root->data); }} |
结果:
