本文共 2337 字，大约阅读时间需要 7 分钟。

遍历二叉树（Traversing Binary Tree）

相关定义

遍历定义——指按某条搜索路线遍访每个结点且不重复（又称周游）。

遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。  

遍历方法——牢记一种约定，对每个结点的查看都是“先左后右” 。

遍历规则———

（1）二叉树由根、左子树、右子树构成，定义为D、 L、R

（2）D、 L、R的组合定义了六种可能的遍历方案：LDR,   LRD,   DLR,   DRL,   RDL,   RLD

（3）若限定先左后右，则有三种实现方案：DLR  先 (根)序遍历 、LDR   中 (根)序遍历、LRD 后(根)序遍历

注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。

例1：

口诀： DLR—先序遍历，即先根再左再右

            LDR—中序遍历，即先左再根再右

            LRD—后序遍历，即先左再右再根

先序遍历的结果是：A B D E C          中序遍历的结果是：D B E A C                后序遍历的结果是：D E B C A

 先序遍历：ABCDEFGH                    中序遍历：BDCEAFHG                     后序遍历：DECBHGFA

 例2：用二叉树表示算术表达式

遍历的算法实现：用递归形式格外简单！

//回忆1：二叉树二叉链表结点的定义：typedef struct node *tree_pointer;typedef struct node {        int data;        tree_pointer  left_child, right_child;} node;

//结点数据类型自定义typedef struct node{   int  data;    struct node lchild,*rchild；} NODE;NODE *root;

先序遍历算法：

DLR(NODE *root ){      if (root) //非空二叉树    {printf(“%d”,root->data); //访问DDLR(root->lchild); //递归遍历左子树DLR(root->rchild); //递归遍历右子树    }}

中序遍历算法：

LDR(NODE *root){ if(root !=NULL)  {  LDR(root->lchild);      printf(“%d”,root->data);      LDR(root->rchild);   } }

后序遍历算法：

LRD (NODE *root){if(root !=NULL)    {LRD(root->lchild);     LRD(root->rchild);     printf(“%d”,root->data);    } }

#include
   
    #include
    
     #include
     
      /*typedef struct BiTNode{int date;struct BiTNode* lchild,* rchild;}BiTNode,*BiTree;*///二叉链表示法struct BiTNode{	int date;	struct BiTNode* lchild, *rchild;}BiTNode, *BiTree;typedef struct BiTNode BiTNode;typedef struct BiTNode *BiTree;void preOrder(BiTNode* root){	if (root == NULL)	{		return;	}	printf("%d", root->data);	//遍历左子树	preOrder(root->lchild);	//遍历右子树	preOrder(root->rchild);}void inOrder(BiTNode* root){	if (root == NULL)	{		return;	}		//遍历左子树	inOrder(root->lchild);	printf("%d", root->data);	//遍历右子树	inOrder(root->rchild);}void postOrder(BiTNode* root){	//遍历左子树	postOrder(root->lchild);	//遍历右子树	postOrder(root->rchild);	printf("%d", root->data);}void main(){	BiTNode t1, t2, t3, t4, t5;	memset(&t1, 0, sizeof(BiTNode));	memset(&t2, 0, sizeof(BiTNode));	memset(&t3, 0, sizeof(BiTNode));	memset(&t4, 0, sizeof(BiTNode));	memset(&t5, 0, sizeof(BiTNode));	t1.data = 1;	t2.data = 2;	t3.data = 3;	t4.data = 4;	t5.data = 5;	//建立关系	t1.lchild = &t2;	t1.rchild = &t3;	t2.lchild = &t4;	t3.lchild = &t5;	//树的遍历	printf("preOrder\n");	preOrder(&t1);	printf("inOrder\n");	inOrder(&t1);	printf("postOrder\n");	postOrder(&t1);	return;}
     
    
   

转载地址：http://mzqkk.baihongyu.com/