二叉树基本 *** 作（16个）

本代码采用三个文件编写，分别是头文件，函数的文件，和主文件，除了后三个代码用c++编写（用c语言太麻烦了），其余全是c语言，目前就是只有一个清除树代码运行有错误，当时找了好久没有找出哪个地方出错，若找到后续会更新改正，欢迎在讨论区交流。

 头文件：

#pragma once
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef  char TElemType;
typedef struct BinNode  //定义二叉树结点：二叉链表结构 (5分)
{
	int data;
	struct BinNode* Ichild, * Rchild;
}BinNode;
typedef struct BinNode* BinTree;


void CreateBinTree(BinTree &bt);//创建二叉树
void PreOrderBinTree(BinTree &bt);//先序遍历
void InOrderBinTree(BinTree &bt);//中序遍历
void PostOrderBinTree(BinTree &bt);//后序遍历
BinNode* FindNode(BinTree bt, TElemType x);//查找值为F的结点
int Size(BinTree bt);//求结点个数
int Height(BinTree bt);//求树的高度
BinNode* Parent(BinTree bt, BinNode* p);//查找二叉树中某个结点p的父节点
BinNode* LeftChild(BinNode* p);//查找结点p的左孩子结点　
BinNode* RightChild(BinNode* p);//查找结点p的右孩子结点
BinNode* Copy(BinTree bt);//用bt拷贝newbt树
void ClearBinTree(BinTree &bt);// 清除树
void LevelOrder(BinTree bt);//层次遍历
void PreorderTraverse(BinTree bt);//先序非递归遍历
void InorderTraverse(BinTree bt);//非递归中序遍历

函数文件：

注意：*&bt：bt离着*，&谁近他就是什么类型，所以这里是&引用型（别名），再加上*这里就表示引用型指针，想到与传入指针得本身，可以对指针的指向和值都进行改变。

#include "touwen.h"//传入 函数 *&p是传入指针p本身 ，可以对指针的指向做更改，如p++,也可以更改指针指向的值

//#法线序创建二叉树
void CreateBinTree(BinTree &bt) {
	char ch;
	cin >> ch;
	if (ch != '#'){
		bt = (BinTree)malloc(sizeof(BinTree));
		bt->data = ch;
		CreateBinTree(bt->Ichild);//这里就对bt指针改变了，所以需要用*&的形式
		CreateBinTree(bt->Rchild);
	}
	else {
		bt = NULL;
	}

}
//先序遍历
void PreOrderBinTree(BinTree &bt) //先序遍历访问二叉树
{
	if (bt!= NULL)
	{
		putchar(bt->data);//在屏幕上显示字符, 若直接用cout<data, 则输出的字符的ASCII码.
		printf(" ");
		PreOrderBinTree(bt->Ichild);
		PreOrderBinTree(bt->Rchild);
	}
	else
	{
		return;
	}
}
//中序遍历
void InOrderBinTree(BinTree& bt) //先序遍历访问二叉树
{
	if (bt != NULL)
	{
		InOrderBinTree(bt->Ichild);
		putchar(bt->data);//在屏幕上显示字符, 若直接用cout<data, 则输出的字符的ASCII码.
		printf(" ");
		InOrderBinTree(bt->Rchild);
	}
	else
	{
		;
	}
}//后序遍历
void PostOrderBinTree(BinTree& bt) //先序遍历访问二叉树
{
	if (bt != NULL)
	{
		
		PostOrderBinTree(bt->Ichild);
		PostOrderBinTree(bt->Rchild);
		putchar(bt->data);//在屏幕上显示字符, 若直接用cout<data, 则输出的字符的ASCII码.
		printf(" ");
	}
	else
	{
		;
	}
}
//查找在二叉树中查找值为x的结点
BinNode* FindNode(BinTree bt, TElemType x) {
	BinTree temp;
	temp = bt;
	
	if (bt != NULL)
	{ 
		if (temp->data == x) {
			return bt;
		}
		FindNode(temp->Ichild,x);//先看左子树
		if(!temp)FindNode(temp->Rchild,x);//左子树为空，才可以进入右子树，若左子树不为空，跳过这一步，返回temp指针。
	}
	else
	{
		return NULL;
	}
}
//求结点个数
int Size(BinTree bt) {
	if (bt == NULL) {
		return 0;
	}
	else {
		return Size(bt->Ichild)+ Size(bt->Rchild)+1;
	}
}
//求树的高度
int Height(BinTree bt) {
	int m = 0, n = 0;
	if (bt == NULL) {
		return 0;
	}
	else {
		m = Height(bt->Ichild);
		n = Height(bt->Rchild);
		if (m > n) {
			return (m + 1);
		}
		else {
			return (n + 1);
		}
	}
}
//查找二叉树中某个结点p的父节点
BinNode* Parent(BinTree bt, BinNode* p) {
	if (bt == NULL || bt == p || p == NULL) {
		return NULL;//T==p说明p是头结点，头节点没有父节点
	}
	if (bt->Ichild == p || bt->Rchild == p) {
		return bt;
	}
	BinTree temp = Parent(bt->Ichild, p);
	if (temp != NULL) {
		return temp;
	}
	else {
		return Parent(bt->Rchild, p);
	}
}
//查找结点p的左孩子结点　
BinNode* LeftChild(BinNode* p) {
	if (p == NULL||p->Ichild==NULL) {
		return NULL;
	}
	else {
		return p->Ichild;
	}
}
//查找结点p的右孩子结点
BinNode* RightChild(BinNode* p) {
	if (p == NULL || p->Rchild == NULL) {
		return NULL;
	}
	else {
		return p->Rchild;
	}
}
//用bt拷贝newbt树
BinNode * Copy(BinTree bt) {
	if (bt == NULL) {
		return NULL;
	}
	else {
		BinTree newbt = (BinTree)malloc(sizeof(BinNode ));
		BinTree newIchild = NULL;
		BinTree newRchild = NULL;
		newIchild = Copy(bt->Ichild);
		newRchild = Copy(bt->Rchild);
		newbt->data = bt->data;
		newbt->Ichild = newIchild;
		newbt->Rchild = newRchild;
		return newbt;
	}
}
//清空二叉树，其实就是后序遍历删除
void ClearBinTree(BinTree &bt) {
	if (bt != NULL) {
		ClearBinTree(bt->Ichild);
		ClearBinTree(bt->Rchild);
		free(bt);
		bt = NULL;
	}
	
}
//层次遍历
queue qu;
void LevelOrder(BinTree bt) {
	qu.push(bt);
	cout << "层次遍历为：";
	while(!qu.empty()) {
		printf("%c ", qu.front()->data);
		if (qu.front()->Ichild != NULL) {
			qu.push(qu.front()->Ichild);
		}
		if (qu.front()->Rchild != NULL) {
			qu.push(qu.front()->Rchild);
		}
		qu.pop();
	}
}
stack sta;
//先序非递归遍历
void PreorderTraverse(BinTree bt) {
	cout << "先序遍历结果为：";
	while (bt || !sta.empty()) {
		if (bt) {
			printf("%c ", bt->data);
			sta.push(bt);
			bt = bt->Ichild;
		}
		else {
			bt = sta.top()->Rchild;
			sta.pop();
		}
	}
	return;
}
//非递归种序遍历
void InorderTraverse(BinTree bt) {
	cout << "中序遍历结果为：";
	while (bt || !sta.empty()) {
		if (bt) {
			sta.push(bt);
			bt = bt->Ichild;
		}
		else {
			printf("%c ", sta.top()->data);
			bt = sta.top()->Rchild;
			sta.pop();
		}
	}
	return ;
}

mian文件：

这个文件我把功能都分别注释掉了，想运行哪一个可以把注释去掉就可以，我这里利用的时DEF###B##作为输入案例，大家也可以使用别的数据进行测试，但要保证时是用正确的#法建立二叉树的格式输入

#include "touwen.h"
int main() {
	BinTree T = NULL;
	printf("按先序遍历输入二叉树结点：");
	CreateBinTree(T);//DEF###B##(课本用例子)
	PreOrderBinTree(T);//先序
	
	//InOrderBinTree(T);//中序
	
	//PostOrderBinTree(T);//后续

	/*char x = 'F';//查找值为x的结点
	BinTree p = FindNode(T, x);
	printf("查找值为F的结点值为：%c\n", p->data);*/

	//int a = Size(T);//结点个数
	//printf("二叉树结点个数为：%d\n", a);
	
	//int a = Height(T);//树的高度
	//printf("二叉树的高度为：%d\n", a);

     /* char x = 'F';//查找值为x的结点
	BinTree p = FindNode(T, x);
	printf("查找值为F的结点值为：%c\n", p->data);
	 p = Parent(T, p);//查找二叉树中某个结点p的父节点,和查找x值结点搭配使用测试
	printf("查找值为F的父结点值为：%c", p->data);*/

	/*char x = 'E';
	BinTree p = FindNode(T, x);
	printf("查找值为F的结点值为：%c\n", p->data);
	p = LeftChild(p);//查找结点p的左孩子结点　
	printf("查找值为E的左孩子值为：%c", p->data);*/

	/*char x = 'D';
	BinTree p = FindNode(T, x);
	printf("查找值为D的结点值为：%c\n", p->data);
	p = RightChild(p);//查找结点p的左孩子结点　
	printf("查找值为D的右孩子值为：%c", p->data);*/

	//BinTree temp = Copy(T);
	//PreOrderBinTree(temp);//先序

	//ClearBinTree(T);//清空二叉树
	//PreOrderBinTree(T);

	//LevelOrder(T);//层次遍历

	//PreorderTraverse(T);//非递归先序遍历

	//InorderTraverse(T);//非递归中序遍历


	return 0;
}

不懂得可以在讨论区交流！