初识二叉树

2024-01-25 04:36:01
开发
44

一.二叉树的介绍

1.二叉树是一种树状数据结构，由多个节点构成，每个节点最多有两个子节点，这两个节点称为左节点和右节点，一个节点的上一次称为它的父节点，下一层称为它的子节点，越往下走，节点越多，越往上走，节点越少，由下面一张图，你便容易清楚二叉树名字的得来。

2. 二叉树有以下特点：

1.一个有x层的二叉树，允许最多有2^(x)-1个节点。

2.第x层，最多有2^x个节点。

3.二叉树有一个根节点，是树的起始点，没有父节点。叶子节点是没有子节点的节点，它们位于树的末端。

3.二叉树又分为满二叉树和完全二叉树。

满二叉树：二叉树的每一层都是满的，即每个节点都有两个子节点（除了最后一层，可以有一个子节点），假如4层的二叉树，就有15个节点，下图示例。

完全二叉树：除了最后一层外，每一层的节点都是紧凑排列的，并且最后一层的节点从左到右依次填充。

二.二叉树的创建。

1.首先用一个结构体表示一个节点的数据、左子结点和右子节点。

struct tree{
	int data;//存放数据
	struct tree*lefttree;//左子节点 
	struct tree*righttree;//右子节点 
};

2.创建节点。

struct tree* creattreenode(int data)//返回结构体指针类型 
{
	struct tree* newtreenode=(struct tree*)malloc(sizeof(struct tree));//动态分配空间 
	newtreenode->data=data;
	newtreenode->lefttree=NULL;//此时新建的节点没有左子结点和右子节点，设置为空 
	newtreenode->righttree=NULL;
	return newtreenode;//返回新建的节点 
}

3.给节点插入对应的子节点。

void insert(struct tree*mytree,struct tree*mylefttree,struct tree*myrighttree) 
{
	mytree->lefttree=mylefttree;//将树的左右子节点与你想插入的左右子节点连接 
	mytree->righttree=myrighttree;
}

以这张图片为模板构建好二叉树，只需利用上述函数即可简单实现。

	struct tree*num0=creattreenode(0);//创建出对应节点 
	struct tree*num1=creattreenode(1);
	struct tree*num2=creattreenode(2);
	struct tree*num3=creattreenode(3);
	struct tree*num4=creattreenode(4);
	struct tree*num5=creattreenode(5);
	insert(num0,num1,num2);//插入操作 
	insert(num1,num3,num4);
	insert(num2,num5,NULL);

构建好后，便可以为遍历做好准备。

三.二叉树的遍历。

二叉树的遍历分为先序遍历、中序遍历和后序遍历。

以上面的二叉树为模板介绍三种遍历

提前写好打印函数。

void print(struct tree*treenode)
{
	printf("%d\t",treenode->data); 
}

1.先序遍历：按照根节点，左孩子树，右孩子树的顺序遍历。

void pre(struct tree*treenode)
{
	if(treenode!=NULL)//一定要不为空才进行遍历，不然会死循环 
	{
		print(treenode);//根开始 
		pre(treenode->lefttree);//左子节点 
		pre(treenode->righttree);//右子节点 
	}
}

运行结果

0       1       3       4       2       5

2.中序遍历：按照左孩子树，根节点，右孩子树的顺序遍历。

只需更换一下位置即可

void mid(struct tree*treenode)
{
	if(treenode!=NULL)//一定要不为空才进行遍历，不然会死循环 
	{
		mid(treenode->lefttree);//左子节点开始 
		print(treenode);
		mid(treenode->righttree);
	}
}

运行结果

3       1       4       0       5       2

3.后序遍历：按照左孩子树，右孩子树，根节点的顺序遍历。

原理一样

void last(struct tree*treenode)
{
	if(treenode!=NULL)//一定要不为空才进行遍历，不然会死循环 
	{
		last(treenode->lefttree);//左子节点开始 
		last(treenode->righttree);
		print(treenode);
	}
}

运行结果

3       4       1       5       2       0

对于三种遍历我是使用的递归的方式，如果不喜欢递归的话，可以使用栈去遍历二叉树。

1.栈实现先序遍历。

void prestack(struct tree*treenode)
{
	if(treenode==NULL)
	return;
	struct tree*stack[20];
	int stacksize=-1;
	struct tree*temp=treenode;
	while(stacksize!=-1||temp){//当栈全部输出，并且左右节点都为空，便会停止循环 
		while(temp){//按照根左右的先序遍历 
			print(temp);//打印走过的节点 
			stack[++stacksize]=temp;//将左子结点入栈 
			temp=temp->lefttree;
		}
		if(stacksize!=-1)//当左子节点无路可走，开始往右子节点遍历 
		{
			temp=stack[stacksize];//获取栈顶元素，用与输出 
			stacksize--;
			temp=temp->righttree;
		}
	}
}

运行结果

0       1       3       4       2       5

2.栈实现中序遍历

void midstack(struct tree*treenode)
{
	if(treenode==NULL)
	return;
	struct tree*stack[20];
	int stacksize=-1;
	struct tree*temp=treenode;
	while(stacksize!=-1||temp){
		while(temp){// 先到左子节点位置，把经过的位置入栈 
			stack[++stacksize]=temp;
			temp=temp->lefttree;
		}
		if(stacksize!=-1)//准备工作完成，出栈 
		{
			temp=stack[stacksize];
			stacksize--;
			print(temp);
			temp=temp->righttree;
		}
	}
}

运行结果

3       1       4       0       5       2

3.栈实现后序遍历

void laststack(struct tree*treenode)
{
	if(treenode==NULL)
	return;
	struct tree*stack[20];
	int stacksize=-1;
	struct tree*temp=treenode;
	struct tree*flag=NULL; //需要使用访问标记 
	while(temp){//先将左节点入队 
		stack[++stacksize]=temp;
		temp=temp->lefttree;
	}
	while(stacksize!=-1){
		temp=stack[stacksize--];
		if(temp->righttree==NULL||temp->righttree==flag)
		{
			print(temp);//被访问则打印当前节点 
			flag=temp;//改变标记位置 
		}
		else
		{//开始往右边访问 
			stack[++stacksize]=temp;
			temp=temp->righttree;
			while(temp){
				stack[++stacksize]=temp;
				temp=temp->lefttree;
			}
		}

	}
}

运行结果

3       4       1       5       2       0

最后附上全部代码

递归版

#include<stdio.h>
#include<stdlib.h>
struct tree{
	int data;//存放数据
	struct tree*lefttree;//左子节点 
	struct tree*righttree;//右子节点 
};
struct tree* creattreenode(int data)//返回结构体指针类型 
{
	struct tree* newtreenode=(struct tree*)malloc(sizeof(struct tree));//动态分配空间 
	newtreenode->data=data;
	newtreenode->lefttree=NULL;//此时新建的节点没有左子结点和右子节点，设置为空 
	newtreenode->righttree=NULL;
	return newtreenode;//返回新建的节点 
}
void insert(struct tree*mytree,struct tree*mylefttree,struct tree*myrighttree) 
{
	mytree->lefttree=mylefttree;//将树的左右子节点与你想插入的左右子节点连接 
	mytree->righttree=myrighttree;
}
void print(struct tree*treenode)
{
	printf("%d\t",treenode->data); 
}
void pre(struct tree*treenode)
{
	if(treenode!=NULL)//一定要不为空才进行遍历，不然会死循环 
	{
		print(treenode);//根开始 
		pre(treenode->lefttree);//左子节点 
		pre(treenode->righttree);//右子节点 
	}
}

void mid(struct tree*treenode)
{
	if(treenode!=NULL)//一定要不为空才进行遍历，不然会死循环 
	{
		mid(treenode->lefttree);//左子节点开始 
		print(treenode);
		mid(treenode->righttree);
	}
} 

void last(struct tree*treenode)
{
	if(treenode!=NULL)//一定要不为空才进行遍历，不然会死循环 
	{
		last(treenode->lefttree);//左子节点开始 
		last(treenode->righttree);
		print(treenode);
	}
} 
int main()
{
	struct tree*num0=creattreenode(0);//创建出对应节点 
	struct tree*num1=creattreenode(1);
	struct tree*num2=creattreenode(2);
	struct tree*num3=creattreenode(3);
	struct tree*num4=creattreenode(4);
	struct tree*num5=creattreenode(5);
	insert(num0,num1,num2);//插入操作 
	insert(num1,num3,num4);
	insert(num2,num5,NULL);
	pre(num0);
	printf("\n");
	mid(num0);
	printf("\n");
	last(num0);
	return 0;
}

栈版

#include<stdio.h>
#include<stdlib.h>
struct tree{
	int data;//存放数据
	struct tree*lefttree;//左子节点 
	struct tree*righttree;//右子节点 
};
struct tree* creattreenode(int data)//返回结构体指针类型 
{
	struct tree* newtreenode=(struct tree*)malloc(sizeof(struct tree));//动态分配空间 
	newtreenode->data=data;
	newtreenode->lefttree=NULL;//此时新建的节点没有左子结点和右子节点，设置为空 
	newtreenode->righttree=NULL;
	return newtreenode;//返回新建的节点 
}
void insert(struct tree*mytree,struct tree*mylefttree,struct tree*myrighttree) 
{
	mytree->lefttree=mylefttree;//将树的左右子节点与你想插入的左右子节点连接 
	mytree->righttree=myrighttree;
}
void print(struct tree*treenode)
{
	printf("%d\t",treenode->data); 
}
void prestack(struct tree*treenode)
{
	if(treenode==NULL)
	return;
	struct tree*stack[20];
	int stacksize=-1;
	struct tree*temp=treenode;
	while(stacksize!=-1||temp){//当栈全部输出，并且左右节点都为空，便会停止循环 
		while(temp){//按照根左右的先序遍历 
			print(temp);//打印走过的节点 
			stack[++stacksize]=temp;//将左子结点入栈 
			temp=temp->lefttree;
		}
		if(stacksize!=-1)//当左子节点无路可走，开始往右子节点遍历 
		{
			temp=stack[stacksize];//获取栈顶元素，用与输出 
			stacksize--;
			temp=temp->righttree;
		}
	}
}
void midstack(struct tree*treenode)
{
	if(treenode==NULL)
	return;
	struct tree*stack[20];
	int stacksize=-1;
	struct tree*temp=treenode;
	while(stacksize!=-1||temp){
		while(temp){// 先到左子节点位置，把经过的位置入栈 
			stack[++stacksize]=temp;
			temp=temp->lefttree;
		}
		if(stacksize!=-1)//准备工作完成，出栈 
		{
			temp=stack[stacksize];
			stacksize--;
			print(temp);
			temp=temp->righttree;
		}
	}
}
void laststack(struct tree*treenode)
{
	if(treenode==NULL)
	return;
	struct tree*stack[20];
	int stacksize=-1;
	struct tree*temp=treenode;
	struct tree*flag=NULL; //需要使用访问标记 
	while(temp){//先将左节点入队 
		stack[++stacksize]=temp;
		temp=temp->lefttree;
	}
	while(stacksize!=-1){
		temp=stack[stacksize--];
		if(temp->righttree==NULL||temp->righttree==flag)
		{
			print(temp);//被访问则打印当前节点 
			flag=temp;//改变标记位置 
		}
		else
		{//开始往右边访问 
			stack[++stacksize]=temp;
			temp=temp->righttree;
			while(temp){
				stack[++stacksize]=temp;
				temp=temp->lefttree;
			}
		}

	}
}
int main()
{
	struct tree*num0=creattreenode(0);//创建出对应节点 
	struct tree*num1=creattreenode(1);
	struct tree*num2=creattreenode(2);
	struct tree*num3=creattreenode(3);
	struct tree*num4=creattreenode(4);
	struct tree*num5=creattreenode(5);
	insert(num0,num1,num2);//插入操作 
	insert(num1,num3,num4);
	insert(num2,num5,NULL);
	prestack(num0);
	printf("\n");
	midstack(num0);
	printf("\n");
	laststack(num0);
	return 0;
}

先介绍这部分内容。

本篇完~

原文地址:https://blog.csdn.net/2301_80314483/article/details/135830829 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1750256159966760960.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部

初识二叉树

相关推荐

最近更新

热门阅读