二叉树的概念与链式存储实现

二叉树与堆

二叉树
- 一：二叉树的概念与性质
- 二：二叉树的存储结构
- - （1）链式存储
  - （2）顺序存储
- 三：二叉树的链式存储结构及实现
- - （1）二叉树链式存储结构
  - （2）二叉树链式存储前序遍历
  - （3）二叉树链式存储中序遍历
  - （4）二叉树链式存储后序遍历
  - （5）二叉树节点个数
  - （6）叶子节点个数
  - （7）树高
  - （8）第k层节点个数
  - （9）二叉树查找值为X的节点
  - （10）层序遍历（利用队列解决层序遍历）
  - （11）判断二叉树是否是完全二叉树
  - （12）二叉树销毁
- BinaryTree.c

二叉树

一：二叉树的概念与性质

概念：一棵二叉树是结点的一个有限集合，该集合：
1：或者为空；由一个根节点加上两棵别称为左子树和右子树的二叉树组成
2：二叉树不存在度大于2的结点；二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

性质：

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2的i次方减1个结点.
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2的h次方-1
对任何一棵二叉树, 如果度为0其叶结点个数为n0,度为2的分支节点结点个数为n2,则有n0=n2+1
若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2(n+1)
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

二：二叉树的存储结构

二叉树一般分为两种存储结构，一种是顺序结构，一种是链式结构。

（1）链式存储

概念：二叉树的链式存储结构是指用链表来表示一颗二叉树，即用链表来指示元素的逻辑关系；通常是在高阶数据结构红黑树等会使用该存储结构

（2）顺序存储

概念：顺序存储结构就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不会有空间浪费（例如：堆排序）

三：二叉树的链式存储结构及实现

（1）二叉树链式存储结构

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

BTNode* ByBTNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->_data = x;
	newnode->_left = newnode->_right = NULL;

	return newnode;
}

（2）二叉树链式存储前序遍历

// 二叉树前序遍历  根 左子树 右子树
void PreOrder(BTNode* root)
{
	//判断是否未NULL树
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->_data);
	//再递归访问左子树
	PreOrder(root->_left);
	//再递归访问右子树
	PreOrder(root->_right);
}

（3）二叉树链式存储中序遍历

// 二叉树中序遍历 左子树 根 右子树
void InOrder(BTNode* root)
{
	//判断是否未NULL树
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	//先递归访问左子树
	InOrder(root->_left);
	printf("%d ", root->_data);
	//再递归访问右子树
	InOrder(root->_right);

}

（4）二叉树链式存储后序遍历

//后序遍历 左子树 右子树 根
void PostOrder(BTNode* root)
{
	//先判断是否为空树
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	//先访问左子树
	PostOrder(root->_left);
	//再访问右子树
	PostOrder(root->_right);
	printf("%d ", root->_data);
}

（5）二叉树节点个数

//求二叉树节点个数
int TreeSize(BTNode* root)
{
	//1:如果为空则返回0
	//2：不为空则递归左子树和右子树
	return root == NULL ? 0 : TreeSize(root->_left) + TreeSize(root->_right) + 1;

}

（6）叶子节点个数

int TreeLeafSize(BTNode* root)
{
	//当节点为空时返回 0，此时为空树
	if (root == NULL)
	{
		return 0;
	}

	//节点的左子树与右子树同时为空是返回1，代表此时为叶子节点
	if (root->_left == NULL&&root->_right == NULL)
	{
		return 1;
	}

	//递归到叶子节点
	return TreeLeafSize(root->_left) + TreeLeafSize(root->_right);
}

（7）树高

int TreeHeight(BTNode* root)
{
	//根节点为空时为空树
	if (root == NULL)
	{
		return 0;
	}

	//1：用变量接收左右两边子树的高度
	//2：先递归完左子树高度
	//3：再递归右子树高度
	//最后比较左子树和右子树哪边大，再加根节点高度就为树的高度
	int leftheight = TreeHeight(root->_left);
	int rightheight = TreeHeight(root->_right);

	return leftheight > rightheight ? leftheight + 1 : rightheight + 1;

}

（8）第k层节点个数

int TreeKSize(BTNode* root, int k)
{
	
	if (root == NULL)
	{
		return 0;
	}

	//k==1时表示层数为1时
	if (k == 1)
	{
		return 1;
	}

	//逐层递归计算节点个数
	return TreeKSize(root->_left, k - 1) + TreeKSize(root->_right, k - 1);
}

（9）二叉树查找值为X的节点

BTNode* TreeFind(BTNode* root, BTDataType x)
{
	//该节点为空返回空
	if (root == NULL)
	{
		return NULL;
	}

	//节点值==x,返回root
	if (root->_data == x)
	{
		return root;
	}

	//找递归左子树是否存在，存在则返回ret1;
	BTNode* ret1 = TreeFind(root->_left, x);
	if (ret1)
	{
		return ret1;
	}

	//找递归右子树是否存在，存在则返回ret2
	BTNode* ret2 = TreeFind(root->_right, x);
	if (ret2)
	{
		return ret2;
	}

	//不存在返回空
	return NULL;
}

（10）层序遍历（利用队列解决层序遍历）

void LevelOeder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	
	//根节点不为空时，从队尾插入
	if (root)
	{
		QueuePush(&q, root);
	}

	printf(" LevelOeder:");
	//队列不为NULL时，一直插入
	while (!QueueEmpty(&q))
	{
		//取队头元素
		QDataType front = QueueFront(&q);

		printf("%d ", front->_data);


		//判断是否存在左子树,存在就插入
		if (front->_left)
		{
			QueuePush(&q, front->_left);
		}

		//判断是否存在右子树,存在就插入
		if (front->_right)
		{
			QueuePush(&q, front->_right);
		}

		//删除队头元素
		QueuePop(&q);
		
	}
	
	QueueDestroy(&q);
}

（11）判断二叉树是否是完全二叉树

bool BinaryTreeComplete(BTNode* root)
{
	//利用层序遍历思路，用队列解决判断是否是完全二叉树
	Queue q;

	//初始化
	QueueInit(&q);
	//插入
	QueuePush(&q, root);

	while (!QueueEmpty(&q))//
	{
		BTNode* front = QueueFront(&q);//取队头元素保存
		QueuePop(&q);//删除队头元素

		if (front == NULL)//当元素为空时跳出判断
		{
			break;
		}
		else
		{
			//左右子树插入
			QueuePush(&q, front->_left);
			QueuePush(&q, front->_right);
		}
	}

	//出到空之后全是空，则是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		if (front != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;
}

（12）二叉树销毁

void TreeDestroy(BTNode* root)
{
	//判断是否为空
	if (root == NULL)
	{
		return;
	}

	//后序遍历销毁
	TreeDestroy(root->_left);
	TreeDestroy(root->_right);

	free(root);

}

BinaryTree.c

#include<stdio.h>
#include<stdlib.h>
#include"queue.h"

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

BTNode* ByBTNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->_data = x;
	newnode->_left = newnode->_right = NULL;

	return newnode;
}



// 二叉树前序遍历  根 左子树 右子树
void PreOrder(BTNode* root)
{
	//判断是否未NULL树
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->_data);
	//再递归访问左子树
	PreOrder(root->_left);
	//再递归访问右子树
	PreOrder(root->_right);
}


// 二叉树中序遍历 左子树 根 右子树
void InOrder(BTNode* root)
{
	//判断是否未NULL树
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	//先递归访问左子树
	InOrder(root->_left);
	printf("%d ", root->_data);
	//再递归访问右子树
	InOrder(root->_right);

}

//后序遍历 左子树 右子树 根
void PostOrder(BTNode* root)
{
	//先判断是否为空树
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	//先访问左子树
	PostOrder(root->_left);
	//再访问右子树
	PostOrder(root->_right);
	printf("%d ", root->_data);
}


//求二叉树节点个数
int TreeSize(BTNode* root)
{
	//1:如果为空则返回0
	//2：不为空则递归左子树和右子树
	return root == NULL ? 0 : TreeSize(root->_left) + TreeSize(root->_right) + 1;

}

//求叶子节点个数
int TreeLeafSize(BTNode* root)
{
	//当节点为空时返回 0，此时为空树
	if (root == NULL)
	{
		return 0;
	}

	//节点的左子树与右子树同时为空是返回1，代表此时为叶子节点
	if (root->_left == NULL&&root->_right == NULL)
	{
		return 1;
	}

	//递归到叶子节点
	return TreeLeafSize(root->_left) + TreeLeafSize(root->_right);
}


//求树高
int TreeHeight(BTNode* root)
{
	//根节点为空时为空树
	if (root == NULL)
	{
		return 0;
	}

	//1：用变量接收左右两边子树的高度
	//2：先递归完左子树高度
	//3：再递归右子树高度
	//最后比较左子树和右子树哪边大，再加根节点高度就为树的高度
	int leftheight = TreeHeight(root->_left);
	int rightheight = TreeHeight(root->_right);

	return leftheight > rightheight ? leftheight + 1 : rightheight + 1;

}

//求第k层节点个数
int TreeKSize(BTNode* root, int k)
{
	
	if (root == NULL)
	{
		return 0;
	}

	//k==1时表示层数为1时
	if (k == 1)
	{
		return 1;
	}

	//逐层递归计算节点个数
	return TreeKSize(root->_left, k - 1) + TreeKSize(root->_right, k - 1);
}

//二叉树查找值为X的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	//该节点为空返回空
	if (root == NULL)
	{
		return NULL;
	}

	//节点值==x,返回root
	if (root->_data == x)
	{
		return root;
	}

	//找递归左子树是否存在，存在则返回ret1;
	BTNode* ret1 = TreeFind(root->_left, x);
	if (ret1)
	{
		return ret1;
	}

	//找递归右子树是否存在，存在则返回ret2
	BTNode* ret2 = TreeFind(root->_right, x);
	if (ret2)
	{
		return ret2;
	}

	//不存在返回空
	return NULL;
}

//层序遍历  利用队列解决层序遍历
void LevelOeder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	
	//根节点不为空时，从队尾插入
	if (root)
	{
		QueuePush(&q, root);
	}

	printf(" LevelOeder:");
	//队列不为NULL时，一直插入
	while (!QueueEmpty(&q))
	{
		//取队头元素
		QDataType front = QueueFront(&q);

		printf("%d ", front->_data);


		//判断是否存在左子树,存在就插入
		if (front->_left)
		{
			QueuePush(&q, front->_left);
		}

		//判断是否存在右子树,存在就插入
		if (front->_right)
		{
			QueuePush(&q, front->_right);
		}

		//删除队头元素
		QueuePop(&q);
		
	}
	
	QueueDestroy(&q);
}


//判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	//利用层序遍历思路，用队列解决判断是否是完全二叉树
	Queue q;

	//初始化
	QueueInit(&q);
	//插入
	QueuePush(&q, root);

	while (!QueueEmpty(&q))//
	{
		BTNode* front = QueueFront(&q);//取队头元素保存
		QueuePop(&q);//删除队头元素

		if (front == NULL)//当元素为空时跳出判断
		{
			break;
		}
		else
		{
			//左右子树插入
			QueuePush(&q, front->_left);
			QueuePush(&q, front->_right);
		}
	}

	//出到空之后全是空，则是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		if (front != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;
}


//二叉树销毁
void TreeDestroy(BTNode* root)
{
	//判断是否为空
	if (root == NULL)
	{
		return;
	}

	//后序遍历销毁
	TreeDestroy(root->_left);
	TreeDestroy(root->_right);

	free(root);

}

int main()
{
	BTNode* n1 = ByBTNode(1);
	BTNode* n2 = ByBTNode(2);
	BTNode* n3 = ByBTNode(3);
	BTNode* n4 = ByBTNode(4);
	BTNode* n5 = ByBTNode(5);
	BTNode* n6 = ByBTNode(6);

	BTNode* n7 = ByBTNode(7);
	n3->_right = n7;


	n1->_left = n2;
	n2->_left = n3;
	n1->_right = n4;
	n4->_left = n5;
	n4->_right = n6;

	//前序遍历
	PreOrder(n1);
	printf("
");

	//中序遍历
	InOrder(n1);
	printf("
");

	//后续遍历
	PostOrder(n1);
	printf("
");

	//层序遍历
	LevelOeder(n1);
	printf("
");
	//求二叉树节点个数
	printf("TreeSize:%d
", TreeSize(n1));

	//求二叉树叶子节点
	printf("TreeLeafSize:%d
", TreeLeafSize(n1));

	//求二叉树的高度
	printf("TreeHeight:%d
", TreeHeight(n1));

	//求第k层的节点个数 
	printf("TreeKSize:%d
", TreeKSize(n1, 3));

	//二叉树查找值为X的节点
	BTNode* ret = TreeFind(n1, 7); 
	printf("ret=%d val=%d
", ret, ret->_data);

	//判断二叉树是否是完全二叉树
	printf("BinaryTreeComplete:%d", BinaryTreeComplete(n1));

	TreeDestroy(n1);
	n1 = NULL;

	return 0;
}