最近在中国大学mooc上学习了数据结构课程，这周温习了二叉树相关的知识，现在将和二叉树三种遍历方法的原理以及C++实现基本的操作进行总结。二叉树的元素遍历主要有3种方式：前序遍历（根左右），中序遍历（左根右），后序遍历（左右根），三种遍历方式的主要区别在于访问根节点的顺序不一样。
一、三种遍历的基本实现C++实现
BinTree.h头文件实现：
#ifndef _BINTREE_H #define _BINTREE_H #include<stdlib.h> #include<stdio.h> //节点存储的数据类型 typedef int ElementType; //二叉树节点的基本定义 typedef struct TreeNode* BinTree; typedef BinTree Position; struct TreeNode { //节点存储的数据 ElementType Data; BinTree Left; //左边子树 BinTree Right; //右边子树 }; //遍历算法--递归实现 void PreOrderTraversal(BinTree BT); void InOrderTraversal(BinTree BT); void PostOrderTraversal(BinTree BT); #endif BinTree.cpp文件实现： #include"BinTree.h" //创建一个空的二叉树 BinTree CreateBinTree() { BinTree tree = NULL; return tree; } //二叉树的先序遍历 //根 - 左 - 右 //递归实现 void PreOrderTraversal(BinTree BT) { //如果该节点不为空 if(BT) { printf("%d", BT->Data); //先访问根节点 PreOrderTraversal(BT->Left); //循环遍历左子树 PreOrderTraversal(BT->Right); //循环遍历右子树 } } //二叉树的先序遍历 //左 - 根 - 右 //递归实现 void InOrderTraversal(BinTree BT) { if(BT) { InOrderTraversal(BT->Left); //先循环遍历左子树 printf("%d", BT->Data); //访问根节点 InOrderTraversal(BT->Right); //循环遍历右子树 } } //二叉树的后序遍历 //左 - 右 - 根 //递归实现 void PostOrderTraversal(BinTree BT) { if(BT) { PostOrderTraversal(BT->Left); //先循环遍历左子树 PostOrderTraversal(BT->Right); //循环遍历右子树 printf("%d", BT->Data); //访问根节点 } }
注意：三种遍历方式的主要区别在于访问根节点的顺序不同。
二、二叉树遍历的相关应用
//输出二叉树的中的根节点 void PreOrderPrintLeaves(BinTree BT) { //树非空 if(BT) { //左右节点都是NULL，则是叶子节点 if(!BT->Left && !BT->Right) printf("%d", BT->Data); PreOrderPrintLeaves(BT->Left); PreOrderPrintLeaves(BT->Right); } } //输出二叉树的高度 int PostOrderGetHeight(BinTree BT) { int HL, HR, MaxH; if(BT) { HL = PostOrderGetHeight(BT->Left); //左树的深度 HR = PostOrderGetHeight(BT->Right); //右树的深度 MaxH = (HL>HR)?HL:HR; //左右子树较大的深度 //这里的加1至关重要 -- 没有加则所有的深度都是0 return (MaxH+1); //返回树的深度 } else //空树 return 0; }
