二叉树的遍历（C语言实现）

时间：2025-04-19 07:35:52

二叉树的结构

typedef struct TreeNode {
	char data;//数据 
	struct TreeNode *left;//左孩子 
	struct TreeNode *right;//右孩子 
}TreeNode, *BinTree;

二叉树的创建

//先序遍历初始化二叉树 
BinTree Create(BinTree T) { //传入的是拷贝的指针，对这个拷贝的指针进行了一系列处理，如果不想返回，则需用二重指针 
	char ch;
	scanf("%c", &ch);
	if (ch == '#')
	T = NULL;
	else {
		//传递的是指针，还没有开辟二叉树的存储空间 
		T = (BinTree)malloc(sizeof(TreeNode));//开辟空间 
		T->data = ch;//赋值 
		T->left = Create(T->left);//继续递归，将左儿子的空间开辟，赋值 
		T->right = Create(T->right);//继续递归，将右儿子的空间开辟，赋值	
	}
	return T; 
}
  • 主函数传递了一个自定义结构类型的指针，我们需要在函数内开辟二叉树的存储空间，再将此地址返回给外面的指针。
  • 先输入数据，根据数据判断是否开辟空间
  • 开辟空间，赋值
  • 利用递归思想将左儿子传入，继续开辟空间
  • 利用递归思想将右儿子传入，继续开辟空间
  • 如果不想返回地址，需要使用二重地址，或者指针的引用。此时我们函数内部的是拷贝过的指针，与外面的不一样。所以如果想直接对实参进行改变，需要传递指针的指针，即二重指针。 

前序遍历

void PreOrder (BinTree T){
	if (T!=NULL) { //不为空 
		printf("%c", T->data);
		PreOrder(T->left);
		PreOrder(T->right);
	}
}

中序遍历

void MidOrder (BinTree T){
	if (T!=NULL) { //不为空 
		printf("%c", T->data);
		MidOrder(T->left);
		MidOrder(T->right);
	}
}

后序遍历 

void BackOrder (BinTree T){
	if (T!=NULL) { //不为空 
		printf("%c", T->data);
		BackOrder(T->left);
		BackOrder(T->right);
	}
}

源代码

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstdlib>
using namespace std;

typedef struct TreeNode {
	char data;//数据 
	struct TreeNode* left;//左孩子 
	struct TreeNode* right;//右孩子 
}TreeNode, * BinTree;

//先序遍历初始化二叉树 
BinTree Create(BinTree T) { //传入的是拷贝的指针，对这个拷贝的指针进行了一系列处理，如果不想返回，则需用二重指针 
	char ch;
	cin >> ch;
	if (ch == '#')
		T = NULL;
	else {
		//传递的是指针，还没有开辟二叉树的存储空间 
		T = (BinTree)malloc(sizeof(TreeNode));//开辟空间 
		T->data = ch;//赋值 
		T->left = Create(T->left);//继续递归，将左儿子的空间开辟，赋值 
		T->right = Create(T->right);//继续递归，将右儿子的空间开辟，赋值	
	}
	return T;
}

void PreOrder(BinTree T) {
	if (T != NULL) { //不为空 
		printf("%c", T->data);
		PreOrder(T->left);
		PreOrder(T->right);
	}
}

void MidOrder(BinTree T) {
	if (T != NULL) { //不为空 
		printf("%c", T->data);
		MidOrder(T->left);
		MidOrder(T->right);
	}
}

void BackOrder(BinTree T) {
	if (T != NULL) { //不为空 
		printf("%c", T->data);
		BackOrder(T->left);
		BackOrder(T->right);
	}
}


int main() {
	BinTree T = NULL;//定义二叉树类型的指针 
	T = Create(T);//返回被开辟的空间地址 

	printf("前序遍历\n");
	PreOrder(T);
	printf("\n");

	printf("中序遍历\n");
	MidOrder(T);
	printf("\n");

	printf("后序遍历\n");
	BackOrder(T);
	printf("\n");


	return 0;
}

/*

ABD##E##CF##G##

*/

码字不易，给个鼓励行不~

相关文章