数据结构二叉树创建及例题(上)

今天就带领大家来到树的世界,树无论是在考试上还是实际学习方面都是比较重点的,大家在这块知识要花时间搞懂.

文章目录

前言

一、树的二叉链表定义

二、二叉树三种遍历方式(递归方式)

1.先序遍历方式(根左右)

2.中序遍历方式(左根右)

3.后序遍历方式(左右根)

三、二叉树的层次遍历方式(采用数组模拟队列)

四、已知一颗二叉树的先序遍历序列和中序遍历分别存在两个一维数组中试编写算法建立该二叉树的二叉链表

五、已知一颗二叉树的后序遍历序列和中序遍历分别存在两个一维数组中试编写算法建立该二叉树的二叉链表

六、已知一颗二叉树的层序遍历序列和中序遍历分别存在两个一维数组中试编写算法建立该二叉树的二叉链表

七、二叉树的基本操作

1.求一颗二叉树的节点个数

2.求一棵二叉树的叶子节点个数

3.求一棵二叉树中度为1的节点个数

4.查找二叉树中值为x的节点,若存在则返回存储位置,不存在则返回空值

5.求一棵二叉树的高度

6.求一棵二叉树中值为x的节点作为根节点的子树的深度.

7.交换一棵二叉树的左右子树

8.判断两棵树是否相似(长得一样)

9.判断一棵树是否为完全二叉树

10.设计算法利用叶子节点中的的空指针域将所有的叶子节点,链接成一个带头节点的双链表

11.一个包含二元运算的算数表达式以二叉链表形式存在在二叉树T中,设计算法求解算数表达式

12.求一棵二叉树的最大宽度

八、总代码与测试结果

前言

树这块的内容比较多,包括树的一些基本的定义以及一些计算,后面还有完全二叉树,排序二叉树,平衡二叉树,这些树可能在定义上不一样但思想都是一样的,平衡二叉树在考试中主要考的是操作,代码实现的话实际上是比较困难的,但在面试时可能会考到,再后面树以及森林等等,后续都会讲到.这节主要是树的基本操作.

一、树的二叉链表定义

typedef char Elemtype;
//树的数据结构二叉链表
typedef struct BiTNode {
	Elemtype data;
	struct BiTNode* lchild;
	struct BiTNode* rchild;
}BiTNode,*BiTree;

二、二叉树三种遍历方式(递归方式)

1.先序遍历方式(根左右)

//二叉树的先序遍历(根左右)
void preorderTraverse(BiTree T) {
	if (T != NULL) {
		printf("%c ", T->data);//先访问根节点
		preorderTraverse(T->lchild);//遍历左子树
		preorderTraverse(T->rchild);//遍历右子树
	}
}

2.中序遍历方式(左根右)

//二叉树的中序遍历(左根右)
void inorderTraverse(BiTree T) {
	if (T != NULL) {
		inorderTraverse(T->lchild);
		printf("%c ", T->data);
		inorderTraverse(T->rchild);
	}
}

3.后序遍历方式(左右根)

//二叉树的后序遍历(左右根)
void postorderTraverse(BiTree T) {
	if (T != NULL) {
		postorderTraverse(T->lchild);
		postorderTraverse(T->rchild);
		printf("%c ", T->data);
	}
}

三、二叉树的层次遍历方式(采用数组模拟队列)

//二叉树的层次遍历算法
void levelTraverse(BiTree T) {//使用数组模拟队列注意分配长度
	BiTNode* Queue[80] = {NULL};//这里就分配了40注意
	int front = 0;
	int rear = 0;
	if (T != NULL) {
		Queue[++rear] = T;//根节点入队
	}
	while (front != rear) {
		BiTNode* p = Queue[++front];
		printf("%c ", p->data);
		if (p!=NULL && p->lchild != NULL) {
			Queue[++rear] = p->lchild;
		}
		if (p != NULL && p->rchild != NULL) {
			Queue[++rear] = p->rchild;
		}
	}
}

层次遍历序列为:ABCDEFG

算法思想:首先创建一个队列,将根节点先入队列,如果队列不为空循环操作

1.出队

2.有孩子将孩子入队

直到队列为空,遍历完成.

四、已知一颗二叉树的先序遍历序列和中序遍历分别存在两个一维数组中试编写算法建立该二叉树的二叉链表

这题也是建立二叉树的基本算法,自命题考试的时候容易考.

//已知一颗二叉树的先序遍历序列和中序遍历分别存在两个一维数组中试编写算法建立该二叉树的二叉链表
BiTNode* creatBitree1(char pre[], char in[], int l1, int h1, int l2, int h2) {
	//l代表第一个元素的位置,h代表最后一个元素的位置
	if (l1 > h1) {
		return NULL;
	}
	BiTNode* pNode = (BiTNode*)malloc(sizeof(BiTNode));
	assert(pNode);
	pNode->data = pre[l1];//在中序遍历中寻找根节点所在位置
	int p = l2;
	while (p <= h2) {
		if (in[p] == pre[l1]) {
			break;
		}
		p++;
	}
	//p为在数组中下标a减下标b表示a到b中有几个元素算a不算b
	pNode->lchild = creatBitree1(pre, in, l1 + 1, l1 + p - l2, l2, p - 1);
	pNode->rchild = creatBitree1(pre, in, l1 + p - l2 + 1, h1, p + 1, h2);
	return pNode;
}

算法思想:使用先序和中序序列构建二叉树,首先我们知道先序序列的第一个节点是跟节点,获得根节点后在中序遍历序列中找到根节点所在位置,那么就能确定左孩子和右孩子序列这样我们在根据先序遍历序列就又能递归的将树建立起来.

五、已知一颗二叉树的后序遍历序列和中序遍历分别存在两个一维数组中试编写算法建立该二叉树的二叉链表

//已知一颗二叉树的后序遍历序列和中序遍历分别存在两个一维数组中试编写算法建立该二叉树的二叉链表
BiTNode* creatBitree2(char post[], char in[], int l1, int h1, int l2, int h2) {
	if (l1 > h1) {
		return NULL;
	}
	BiTNode* pNode = (BiTNode*)malloc(sizeof(BiTNode));
	assert(pNode);
	pNode->data = post[h1];
	int p = l2;
	while (l2 <= h2) {
		if (in[p] == post[h1]) {
			break;
		}
		p++;
	}
	pNode->lchild = creatBitree2(post, in, l1, l1 + p - l2 - 1, l2, p - 1);
	pNode->rchild = creatBitree2(post, in, l1 + p - l2, h1 - 1, p + 1, h2);
	return pNode;
}

还是根据上图数据.

算法思想;使用后续遍历与中序遍历构建二叉树,首先我们知道后续遍历的最后的一个节点为根节点,这样我们在中序遍历中找到根节点所在位置,那么左子树右子树序列就知道了,再根据后续遍历的最后一个节点为根节点,就能够递归的建立二叉树了.