菜鸟笔记
提升您的技术认知

二叉树的遍历-ag真人游戏

二叉树的遍历

二叉树的遍历有:前序/中序/后序的递归结构遍历:

1. 前序遍历(preorder traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(inorder traversal)——访问根结点的操作发生在遍历其左右子树之间。
3. 后序遍历(postorder traversal)——访问根结点的操作发生在遍历其左右子树之后。

以下面二叉树为例,进行先序,中序,后序遍历:

先序

分析:从根节点开始,先访问根,再访问左子树(左子树中先访问根节点,在访问左子树和右子 树),最后访问右子树(先访问根节点,在访问左子树和右子树)

访问顺序:

先访问树tree根1,再访问tree左子树l1:

访问l1根2,再访问其左子树ll2:

访问ll2根3,再访问其左子树:左子树为空,访问其右子树,右子树为空,返回上一个子树l1;

此时l1左子树访问完毕,访问l1右子树null,为空返回上一个树tree;

此时tree根和左子树访问完毕,访问tree右子树r1:

访问r1根4,再访问r1左子树rl1:

访问rl1根5,再访问rl1左子树和右子树null,返回上一个树r1;

此时,r1左子树rl1访问完毕,接着访问r1右子树rr1:

访问rr1根6,再访问rr1左右子树null,返回上一个树r1;

此时r1根和左右子树访问完毕,返回上一个树tree;

此时tree的根和左子树访问完毕,及整个树访问完毕。

图示:

 中序

分析:即先访问左子树,左子树访问完毕后再访问根节点,根节点访问完后,最后访问右子树。左子树和右子树中也是先访问左子树,再根,最后右子树

访问顺序:

从tree根开始,先访问其左子树l1:

左子树l1不为空,访问l1左子树ll2:

左子树ll2不为空,访问ll2左子树:

左子树为空,访问ll2根3,再访问ll2的右节点,右节点为空,返回子树l1;

子树l1的左子树访问完毕,访问l1的根2,再访问l1的右子树,为空,返回树tree;

tree的左子树访问完毕,访问tree根1,接着访问tree右子树r1:

右子树r1不为空,访问r1左子树rl1:

rl1不为空,访问rl1左子树,左子树为空,访问rl1根5,再访问其右子树:

右子树为空,返回上一个树r1;

r1左子树访问完毕,访问其根4,接着访问其右子树rr1:

rr1不为空,访问其左子树,左子树为空,访问rr1根6,再访问其右子树为空,返回r1;

此时tree的左子树,根,和右子树都访问完毕。

图示:

后序

分析:先访问左子树(左子树中也是左子树,右子树,根),再访问右子树(右子树中也是左子树,右子树,根),最后访问根节点。

访问顺序:

先访问tree,不为空,访问其左子树l1,l1不为空,访问其左子树ll2;

ll2不为空,访问其左子树,为空;访问其右子树,为空;访问其根3,返回上一个树l1;

l1左子树访问完毕,访问其右子树,为空;访问其根2,返回上一个树tree;

tree的左子树访问完毕,访问其右子树r1,r1不为空,访问其左子树rl1;

rl1不为空,访问其左子树,为空;访问其右子树,为空,访问其根5,返回上一个树r1;

r1左子树访问完毕,访问其右子树rr1,rr1不为空,访问其左子树;

rr1左子树为空,访问其右子树,为空,访问其根6,返回上一个树r1;

此时r1左子树右子树访问完毕,访问其根4,放回上一个树tree;

此时tree的左右子树访问完毕,访问其根1;整个树访问完毕。

图示:

不难发现,上述遍历时中途总会返回上一层树,已经用到了递归思想,这里我们手动实现一个简单的链式二叉树,完成我们的前序,中序,后序的遍历。

定义

定义每个节点由数据,左子树地址和右子树地址组成

typedef int btdatatype;
typedef struct binarytreenode
{
	btdatatype data;  //数据
	struct binarytreenode* left;   //左子树地址
	struct binarytreenode* right;  //右子树地址
}btnode;

 创建节点

将固定的数据放入创建的节点中,左右子树指针置空

btnode* buynode(btdatatype x)
{
	btnode* root = (btnode*)malloc(sizeof(btnode));
	root->data = x;
	root->left = null;
	root->right = null;
	return root;
}

创建二叉树 

手动创建节点,并将左右子树指针指向固定的位置,以上述二叉树为例:

//手动创建
btnode* creatbinarytree()
{
	btnode* node1 = buynode(1);
	btnode* node2 = buynode(2);
	btnode* node3 = buynode(3);
	btnode* node4 = buynode(4);
	btnode* node5 = buynode(5);
	btnode* node6 = buynode(6);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}

前序遍历

依照我们对前序遍历的顺序分析:根,左子树,右子树,编写前序代码:

// 二叉树前序遍历
void preorder(btnode* root)
{
	if (root==null)
	{
		return;
	}
	printf("%d ",root->data);
	preorder(root->left);
	preorder(root->right);
}

中序遍历

// 二叉树中序遍历
void inorder(btnode* root)
{
	if (root == null)
	{
		return;
	}
	inorder(root->left);
	printf("%d ", root->data);
	inorder(root->right);
}

 后序遍历

// 二叉树后序遍历
void postorder(btnode* root)
{
	if (root == null)
	{
		return;
	}
	postorder(root->left);
	postorder(root->right);
	printf("%d ", root->data);
}

求二叉树节点树

方法一:前序中序后序时添加一个计数变量(变量为全局或者静态,防止递归时计数重置)

缺点:重复调用时计数会累加,每次调用时须将count重新置0;

//定义全局或者静态变量
//多次调用会累加
int count = 0;
int btreesize(btnode* root)
{
	if (root == null)
		return;
	  count;
	btreesize(root->left);
	btreesize(root->right);
	return  count;
}

方法二:遍历 计数(遍历时将遍历地址传过去)

//遍历 计数
//将变量地址传过去,计数---思想最优
void btreesize(btnode* root,int* count)
{
	if (root == null)
		return;
	  (*count);
	btreesize(root->left,count);
	btreesize(root->right,count);
}

方法三:递归--分治思想

当根为空时,返回0,左子树节点个数 右子树节点个数 1(根节点本身)

//递归--分治思想--节点个数
int btreesize(btnode* root)
{
	return root == null ? 0 : btreesize(root->left)   btreesize(root->right)   1;
}

求二叉树叶子节点个数 

二叉树叶子节点数 = 左子树叶子节点数 右子树节点数

叶子节点:左子树和右子树为空的节点

//叶子节点个数
int btreeleafsize(btnode* root)
{
	if (root==null)
	{
		return 0;
	}
	if (root->left == null&&root->right==null)
	{
		return 1;
	}
	return btreeleafsize(root->left)   btreeleafsize(root->right);
}

第k层节点数 

 求tree的第三层节点数

即l1和r1的第二层节点数之和

即ll1、rl1和rr1第一层节点数之和

当k=1时,返回1即可

//第k层节点个数
int btreelevesize(btnode* root,int k)
{
	assert(k>=1);
	if (root==null)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return btreelevesize(root->left, k - 1)   btreelevesize(root->right, k - 1);

二叉树深度

二叉树的深度 = 左子树和右子树中最大深度度 1

需要比较左右子树高度,判断返回哪一个

//二叉树深度
int btreedepth(btnode* root)
{
	if (root==null)
	{
		return 0;
	}
	int leftdepth = btreedepth(root->left);
	int rightdepth = btreedepth(root->right);
	return leftdepth >rightdepth ? leftdepth   1 : rightdepth   1;
}

二叉树查找值为x的节点

判断根是否为要找的节点,是则返回节点地址

不是则进左子树中去找,找到返回节点地址,找不到返回空

再进右子树取找,找到返回节点地址,找不到返回空

// 二叉树查找值为x的节点
btnode* binarytreefind(btnode* root, btdatatype x)
{
	if (root==null)
	{
		return null;
	}
	if (root->data == x)
		return root;
	if (binarytreefind(root->left, x))
		return binarytreefind(root->left,x);
	if (binarytreefind(root->right, x))
		return binarytreefind(root->right, x);
	return null;
}
网站地图