二叉树的三种遍历(双链表实现)以及递归思想的个人理解--C语言-创新互联

文章目录

• 二叉树
• 实现一个数组的二叉树插入遍历
• 创建一个二叉树双链表
• 插入结点
• 三种遍历
• • 前序遍历
  • 中序遍历
  • 后序遍历
  • 递归思想

在海拉尔等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供做网站、成都网站建设 网站设计制作按需网站建设,公司网站建设,企业网站建设,高端网站设计,成都营销网站建设,外贸网站制作,海拉尔网站建设费用合理。二叉树

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。所以实现二叉树的遍历用双链表比较简单。

实现一个数组的二叉树插入遍历

data_type arr[] = {35,45,23,44,33,65,13,54};

创建一个二叉树双链表

根据二叉树的特点，我们定义一个包含左右孩子和本身数据的结构体作为根结点

typedef int data_type;

typedef struct treeNode
{struct treeNode *lchild;
	struct treeNode *rchild;
	data_type data;
}tree;

写一个申请根节点的函数，返回申请到的空间的首地址

tree *createTree(data_type item)
{tree *pRoot = NULL;
	pRoot = (tree *)malloc(sizeof(tree));
	if(pRoot == NULL)
	{return NULL;
	}
	memset(pRoot,0,sizeof(tree));
	pRoot->data = item;

	return pRoot;
}

插入结点

插入结点时，我们要先判断插入的值和根结点值谁更大，比根结点大我们将他插入到左孩子中，否则插入到右孩子中

int insertTree(tree *pRoot,data_type item)
{tree *pNew = NULL;
	pNew = (tree *)malloc(sizeof(tree));
	if(pNew == NULL)
	{return -1;
	}
	memset(pNew,0,sizeof(tree));
	pNew->data = item;
	while(1)
	{		if(pNew->data< pRoot->data)//插入左孩子处
		{	if(pRoot->lchild != NULL)
			{		pRoot = pRoot->lchild;
			}
			else
			{		pRoot->lchild = pNew;
				return 0;
			}
		}
		else
		{	if(pRoot->rchild != NULL)//插入右孩子处
			{		pRoot = pRoot->rchild;
			}
			else
			{		pRoot->rchild = pNew;
				return 0;
			}
		}
	}
}

三种遍历

二叉树的遍历分为以下三种：

• 先序遍历：遍历顺序规则为【根左右】

• 中序遍历：遍历顺序规则为【左根右】

• 后序遍历：遍历顺序规则为【左右根】

利用递归思想，实现二叉树的遍历。会在末尾讲解二叉树的递归

前序遍历

//前序遍历
int preOrder(tree *pRoot)
{if(pRoot == NULL)
	{return -1;
	}
	//先访问根结点
	printf("%d ",pRoot->data);
	//访问左子树
	preOrder(pRoot->lchild);
	//访问右子树
	preOrder(pRoot->rchild);
}

中序遍历

//中序遍历
int inOrder(tree *pRoot)
{if(pRoot == NULL)
	{return -1;
	}
	inOrder(pRoot->lchild);
	printf("%d ",pRoot->data);
	inOrder(pRoot->rchild);
}

后序遍历

//后序遍历
int postOrder(tree *pRoot)
{if(pRoot == NULL)
	{return -1;
	}
	postOrder(pRoot->lchild);
	postOrder(pRoot->rchild);
	printf("%d ",pRoot->data);
}

递归思想

拿我们的前序遍历来讲解

if(pRoot == NULL)
	{return -1;
	}
	//先访问根结点
	printf("%d ",pRoot->data); // 1
	//访问左子树
	preOrder(pRoot->lchild); // 2
	//访问右子树
	preOrder(pRoot->rchild); // 3

接下来用一张自己画的图来详细说明

以上是我对递归思想的理解，如有错误请指正！

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文名称：二叉树的三种遍历(双链表实现)以及递归思想的个人理解--C语言-创新互联
网页路径：http://www.cdkjz.cn/article/dhcojc.html