数据结构——二叉树的构建及遍历操作

二叉树的构建

常量的预定义 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int ElemType; 二叉树的定义以及创建 typedef struct BiTNode {/* 树结点定义 */ ElemType data;/* 结点数据 */ struct BiTNode *lchild,*rchild;//左右孩子指针 } BiTNode,*BiTree; Status CreateBiTree(BinTree &T) { // 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树， // 构造二叉链表表示的二叉树T。 char ch; scanf("%c",&ch); if (ch=='#') T = NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR; T->data=ch; // 生成根结点 CreateBiTree(T->lchild);// 构造左子树 CreateBiTree(T->rchild);// 构造右子树 } return OK; } // CreateBiTree

二叉树的遍历

1. 先序遍历 遍历过程为： ① 访问根结点； ② 先序遍历其左子树； ③ 先序遍历其右子树。 例子：

A（B D F E ）（C G H I） 先序遍历=> A B D F E C G H I

代码如下：

void PreorderTraversal( BiTree BT ) { if( BT ) { /* 此处假设对BT结点的访问就是打印数据 */ printf("%d ", BT->Data );/* 假设数据为整型 */ PreorderTraversal( BT->lchild );//递归先序遍历左子树 PreorderTraversal( BT->rchild );//递归先序遍历右子树 } }

2. 中序遍历 遍历过程为： ① 中序遍历其左子树； ② 访问根结点； ③ 中序遍历其右子树。 例子：

（D B E F） A （G H C I） 中序遍历=> D B E F A G H C I

代码如下：

void InorderTraversal( BiTree BT ) { if( BT ) { InorderTraversal( BT->lchild ); /* 此处假设对BT结点的访问就是打印数据 */ printf("%d ", BT->Data); /* 假设数据为整型 */ InorderTraversal( BT->rchlid ); } }

3. 后序遍历 遍历过程为： ① 后序遍历其左子树； ② 后序遍历其右子树； ③ 访问根结点。

（D E F B ）（ H G I C） A 后序遍历=> D E F B H G I C A

代码如下：

void PostorderTraversal( BiTree BT ) { if( BT ) { PostorderTraversal( BT->lchild ); PostorderTraversal( BT->rchlid ); printf("%d ", BT->Data); } }

总结

先序、中序和后序遍历过程：遍历过程中经过结点的路线一样，只是访问各结点的时机不同。