使用C语言程序实现树的遍历（算法）. 先排序，中排序和后排序

遍历树是树的重要操作. 所谓遍历是指对树中所有节点的系统访问，即树中的每个节点只能访问一次. 树的三个最重要的遍历方法称为前遍历，中阶遍历和后遍历. 当以这三种方式遍历树时，如果按照访问节点的顺序排列节点，则可以分别获得树中所有节点的先序列表，中间序列表和后序列表. 相应的节点顺序称为节点的前顺序，中顺序和后顺序.

在数据结构中，

可以访问二叉树的所有节点

序言跟随“扎根”

中间顺序遵循“左根右”

子序列遵循“左右根”

根: 根节点

左: 左孩子

正确: 正确的孩子

例如: 一棵二叉树:

A

/ \

BC

/ \

D E

预订访问顺序为: ABDEC（根必须是第一个）

中阶访问顺序为: DBEAC（root必须在中间）

后续访问顺序为: DEBCA（根必须在结尾）

#include

#include

#define STACK_MAX_SIZE 30

#define QUEUE_MAX_SIZE 30

#ifndef elemType

typedef char elemType;

#endif

/ ************************************************** **** ************************** /

/ *以下是有关二叉树操作的11种简单算法* /

/ ************************************************** **** ************************** /

struct BTreeNode {

elemType数据;

struct BTreeNode *左;

struct BTreeNode *对；

};

/ * 1.初始化二叉树* /

void initBTree（结构BTreeNode * * bt）

{

* bt = NULL;

返回；

}

/ * 2.创建一个二叉树（基于a指向的二叉树的广义字符串）* /

void createBTree（结构BTreeNode * * bt，char * a）

{

struct BTreeNode * p;

struct BTreeNode * s [STACK_MAX_SIZE]; / *将s数组定义为堆栈，以存储根节点指针* /

int top = -1; / *将top定义为s堆栈的顶部指针. 初始值为-1，表示堆栈为空* /

int k; / *将k用作处理节点的左右子树，k = 1表示左子树，k = 2表示右子树* /

int i = 0; / *用i扫描存储在数组a中的二叉树广义表字符串，初始值为0 * /

* bt = NULL; / *将树的根指针设置为null，即从空树构建二叉树* /

/ *一次处理一个字符，直到扫描字符串的末尾* /

while（a [i]！=''）{

开关（a [i]）{

情况”:

休息； / *不处理空格* /

情况'（':

if（top == STACK_MAX_SIZE-1）{

printf（“堆栈空间太小！n”）；

退出（1）;

}

顶部++;

s [top] = p;

k = 1;

休息；

情况'）':

if（top == -1）{

printf（“二叉树广义表字符串错误！n”）；

退出（1）;

}

top-;

休息；

情况'，':

k = 2;

休息；

默认值:

p = malloc（sizeof（struct BTreeNode））;

p->数据= a [i];

p->左= p->右= NULL;

如果（* bt == NULL）{

* bt = p;

}其他{

如果（k == 1）{

s [top]->左= p;

}其他{

s [top]-> right = p;

}

}

}

i ++; / *修改i的值以扫描下一个字符* /

}

返回；

}

/ * 3.检查二叉树是否为空，如果为空，则返回1，否则返回0 * /

int emptyBTree（结构BTreeNode * bt）

{

if（bt == NULL）{

返回1；

}其他{

返回0；

}

}

/ * 4.查找二叉树的深度* /

int BTreeDepth（结构BTreeNode * bt）

{

if（bt == NULL）{

返回0； / *对于空树，返回0以结束递归* /

}其他{

int dep1 = BTreeDepth（bt->左）; / *计算左子树的深度* /

int dep2 = BTreeDepth（bt->向右）; / *计算右子树的深度* /

if（dep1> dep2）{

返回dep1 +1;

}其他{

返回dep2 +1;

}

}

}

/ * 5.从二叉树中找到值为x的节点（如果存在），返回元素存储位置，否则返回空值* /

elemType * findBTree（结构BTreeNode * bt，elemType x）

{

if（bt == NULL）{

返回NULL;

}其他{

if（bt-> data == x）{

返回＆（bt->数据）;

} else {/ *分别递归搜索左和右子树* /

elemType * p;

if（p = findBTree（bt-> left，x））{

返回p;

}

if（p = findBTree（bt-> right，x））{

返回p;

}

返回NULL;

}

}

}

/ * 6.输出二叉树（预遍历）* /

void printBTree（结构BTreeNode * bt）

{

/ *当树为空时结束递归，否则执行以下操作* /

if（bt！= NULL）{

printf（“％c”，bt->数据）； / *输出根节点的值* /

如果（bt->左！= NULL || bt->右！= NULL）{

printf（“（”）;

printBTree（bt->左）;

如果（bt->对！= NULL）{

printf（“，”）;

}

printBTree（bt->右）；

printf（“）”）;

}

}

返回；

}

/ * 7.清除二叉树使其成为空树* /

void clearBTree（结构BTreeNode * * bt）

{

if（* bt！= NULL）{

clearBTree（＆（（（** bt）-> left））;

clearBTree（＆（（（* bt）-> right））;

免费（* bt）;

* bt = NULL;

}

返回；

}

/ * 8.预习遍历* /

void preOrder（结构BTreeNode * bt）

{

if（bt！= NULL）{

printf（“％c”二叉树的遍历算法c实现，bt->数据）； / *访问根节点* /

preOrder（bt->左）； / *以预定顺序遍历左侧子树* /

preOrder（bt->右）； / *以预定顺序遍历右侧子树* /

}

返回；

}

/ * 9.中阶遍历* /

void inOrder（结构BTreeNode * bt）

{

if（bt！= NULL）{

inOrder（bt->左）； / *以中间顺序遍历左侧子树* /

printf（“％c”，bt->数据）； / *访问根节点* /

inOrder（bt->右）； / *以中间顺序遍历右侧子树* /

}

返回；

}

/ * 10.后遍历* /

void postOrder（结构BTreeNode * bt）

{

if（bt！= NULL）{

postOrder（bt->左）; / *以后顺序遍历左侧子树* /

postOrder（bt->右）； / *顺序后遍历右边的子树* /

printf（“％c”，bt->数据）； / *访问根节点* /

}

返回；

}

/ * 11.逐层遍历* /

void levelOrder（结构BTreeNode * bt）

{

struct BTreeNode * p;

struct BTreeNode * q [QUEUE_MAX_SIZE];

int前= 0，后= 0；

/ *将根指针放入团队中* /

if（bt！= NULL）{

后方=（后方+ 1）％QUEUE_MAX_SIZE;

q [rear] = bt;

}

同时（前！=后）{/ *队列不为空* /

front =（front + 1）％QUEUE_MAX_SIZE; / *使团队负责人的指针指向团队负责人的元素* /

p = q [front];

printf（“％c”，p->数据）；

/ *如果节点中有一个左子节点，则左子节点指针将进入团队* /

if（p-> left！= NULL）{

后方=（后方+ 1）％QUEUE_MAX_SIZE;

q [后方] = p->左；

}

/ *如果节点中有一个正确的子节点二叉树的遍历算法c实现，则该正确的子节点指针将进入团队* /

if（p-> right！= NULL）{

后方=（后方+ 1）％QUEUE_MAX_SIZE;

q [后方] = p->正确；

}

}

返回；

}

/ ************************************************** **** ************************** /

/ *

int main（int argc，char * argv []）

{

struct BTreeNode * bt; / *指向二叉树根节点的指针* /

char * b; / *用于存储在二叉树通用表中的字符串* /

elemType x，* px;

initBTree（＆bt）;

printf（“输入二叉树通用表的字符串: n”）；

/ * scanf（“％s”，b）; * /

b =“ a（b（c），d（e（f，g），h（，i））））”;

createBTree（＆bt，b）;

如果（bt！= NULL）

printf（“％c”，bt->数据）；

printf（“以广义表形式的输出: n”）；

printBTree（bt）; / *以广义表的形式输出二叉树* /

printf（“ n”）;

printf（“ Preorder: ”）; / *预习遍历* /

preOrder（bt）;

printf（“ n”）;

printf（“中间顺序: ”）； / *中阶遍历* /

inOrder（bt）;

printf（“ n”）;

printf（“邮购: ”）; / *后遍历* /

postOrder（bt）;

printf（“ n”）;

printf（“按层: ”）； / *逐层遍历* /

levelOrder（bt）;

printf（“ n”）;

/ *从二叉树中找到一个元素节点* /

printf（“输入要查找的字符: n”）；

scanf（“％c”，＆x）; / *格式字符串中的空格会跳过空格字符* /

px = findBTree（bt，x）;

如果（px）{

printf（“查找成功: ％cn”，* px）；

}其他{

printf（“找不到！n”）；

}

printf（“二叉树的深度为: ”）；

printf（“％dn”，BTreeDepth（bt））;

clearBTree（＆bt）;

返回0；

}

* /

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-182604-1.html