1200字范文 > C语言二叉树的创建与遍历

C语言二叉树的创建与遍历

时间：2018-08-17 01:29:34

相关推荐

C语言二叉树的创建与遍历

二叉树的创建与遍历

文章目录

二叉树的创建与遍历前言一、二叉树的结构二、二叉树创建和三种遍历1.2.前序遍历3.中序遍历4.后序遍历5.测试代码总结

前言

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。以下是对链式存储结构的二叉树的创建与先序、中序、后序遍历操作。

一、二叉树的结构

typedef struct Node {//定义Node节点char data;//data数据域struct Node* Lchild;//左孩子struct Noed* Rchild;//右孩子}Node;

二、二叉树创建和三种遍历

1.

代码如下（示例）：

void creatTree(Node** tree,char* data,int* index)//创建树，这里使用二级指针是因为当tree创建其左右孩子时需要使用到二级指针指向他们的数据域以及指针域{char temp;//temp用于保存data里面的数据temp = data[*index];//index是为了方便对全局变量的操作*index += 1;//*index改变索引值if (temp == '#')//如果temp值为#{*tree = NULL;//tree指向NULL}else{*tree = (Node*)malloc(sizeof(Node));//如果不等于#，则对其开辟空间保存(*tree)->data = temp;/*data数据域进行赋值*/creatTree(&((*tree)->Lchild),data,index);//创建树的左孩子，这里传入变量tree的指向的Lchild并且对其进行取地址符creatTree(&((*tree)->Rchild),data,index);//如上使用遍历的方法进行创建}}

2.前序遍历

代码如下（示例）：

void printf_preTree(Node* tree)//前序遍历，先是根，然后是左孩子，最后是右孩子{if (tree == NULL)//如果指向NULL则直接返回{return;}else{printf("%c->",tree->data);//先打印根的dataprintf_preTree(tree->Lchild);//再使用遍历的方法对Lchild进行打印printf_preTree(tree->Rchild);//如上打印Rchild}}

3.中序遍历

代码如下（示例）：

void printf_ioTree(Node* tree)//中序遍历，先是左孩子，然后就是根，再然后就是右孩子{if (tree == NULL){return -1;}else{printf_preTree(tree->Lchild);//先找到最左的孩子printf("%c->", tree->data);//然后打印dataprintf_preTree(tree->Rchild);//再去打印根的孩子，最后会回到右孩子打印}}

4.后序遍历

代码如下（示例）：

void printf_lastTree(Node* tree)//尾序打印，先打印左孩子，再右孩子，最后就是根{if (tree == NULL){return -1;}else{printf_lastTree(tree->Lchild);//找到左边的孩子printf_lastTree(tree->Rchild);//找到右边的孩子printf("%c->", tree->data);//打印右边的孩子}}

5.测试代码

代码如下（示例）：

#include<stdio.h>#include<stdlib.h>typedef struct Node {//定义Node节点char data;//data数据域struct Node* Lchild;//左孩子struct Noed* Rchild;//右孩子}Node;void creatTree(Node** tree,char* data,int* index)//创建树，这里使用二级指针是因为当tree创建其左右孩子时需要使用到二级指针指向他们的数据域以及指针域{char temp;//temp用于保存data里面的数据temp = data[*index];//index是为了方便对全局变量的操作*index += 1;//*index改变索引值if (temp == '#')//如果temp值为#{*tree = NULL;//tree指向NULL}else{*tree = (Node*)malloc(sizeof(Node));//如果不等于#，则对其开辟空间保存(*tree)->data = temp;/*data数据域进行赋值*/creatTree(&((*tree)->Lchild),data,index);//创建树的左孩子，这里传入变量tree的指向的Lchild并且对其进行取地址符creatTree(&((*tree)->Rchild),data,index);//如上使用遍历的方法进行创建}}void printf_preTree(Node* tree)//前序遍历，先是根，然后是左孩子，最后是右孩子{if (tree == NULL)//如果指向NULL则直接返回{return;}else{printf("%c->",tree->data);//先打印根的dataprintf_preTree(tree->Lchild);//再使用遍历的方法对Lchild进行打印printf_preTree(tree->Rchild);//如上打印Rchild}}void printf_ioTree(Node* tree)//中序遍历，先是左孩子，然后就是根，再然后就是右孩子{if (tree == NULL){return -1;}else{printf_preTree(tree->Lchild);//先找到最左的孩子printf("%c->", tree->data);//然后打印dataprintf_preTree(tree->Rchild);//再去打印根的孩子，最后会回到右孩子打印}}void printf_lastTree(Node* tree)//尾序打印，先打印左孩子，再右孩子，最后就是根{if (tree == NULL){return -1;}else{printf_lastTree(tree->Lchild);//找到左边的孩子printf_lastTree(tree->Rchild);//找到右边的孩子printf("%c->", tree->data);//打印右边的孩子}}void main(void){Node* tree;int index = 0;char data[] = "AB##C##";creatTree(&tree,data,&index);printf_preTree(tree);printf("\n");printf_ioTree(tree);printf("\n");printf_lastTree(tree);printf("\n");return 0;}