数据结构初阶 —— 树（二叉树）

目录

一，二叉树

特殊二叉树

二叉树的性质

二叉树的存储结构 

 二，二叉树链式结构

二叉树的遍历（四种）

二叉树接口

试题

一，二叉树

• 由一个根节点，加上两颗左二叉树和右二叉树组成，可以为空；
• 二叉树度不大于2；
• 二叉树子树有左右之分，次序不可颠倒，因此二叉树是有序树；

特殊二叉树

• 满二叉树，若每层节点数都达到最大值，如有k层，则节点总数为；
• 完全二叉树，如有k层，k-1层为满，最后一层从左到右为连续的二叉树；完全二叉树是效率很高的数据结构，是由满二叉树引出来的，满二叉树是特殊的完全二叉树；

二叉树的性质

• 若根节点为1层，则一颗非空二叉树第k层上最多个节点；
• 若根节点为1层，则深度为h的二叉树最多 - 1个节点；
• 若根节点为1层，则具有n个节点的满二叉树，其深度为；
• 任何一个二叉树，叶节点个数比度为2的节点数多1个；
• 对于具有n个节点的二叉树，如按从上到下、从左到右的数组顺序对所有节点从0编号，则对序号为i的节点，如下：

二叉树的存储结构 

•  一般可使用两种结构存储，顺序结构或链式结构；

顺序存储

• 顺序存储即为数组存储，一般只适用表示完全二叉树，不完全二叉树会有空间浪费；
• 实际使用中，只有堆(一种二叉树)才会使用数组来存储；
• 物理上为数组，逻辑上是一颗二叉树；

注：这里的堆和虚拟进制地址空间中的堆是两回事，一个是数据结构，一个是管理内存的一块区域分段；

 链式存储

• 用链表来表示元素的逻辑关系，通常链表中每个节点有三个域组成（数据域、左右指针域）；
• 链式结构可分为二叉链和三叉链；

//二叉链
typedef int BTDataType;
struct BinaryTreeNode
{
	struct BinaryTreeNode* _pLeft; //指向左孩子节点
	struct BinaryTreeNode* _pReft; //指向右孩子节点
	BTDataType _data; //值域
}BinaryTreeNode;

//三叉链
typedef int BTDataType;
struct BinaryTreeNode
{
    struct BinaryTreeNode* _pParent; //指向父节点
	struct BinaryTreeNode* _pLeft; //指向左孩子节点
	struct BinaryTreeNode* _pReft; //指向右孩子节点
	BTDataType _data; //值域
}BinaryTreeNode;

 二，二叉树链式结构

• 普通二叉树的增删查改，意义不大；
• 普通二叉树+搜索树规则，增删查改才有价值；

//二叉树链式结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

//创建节点
BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("BuyNode");
		exit(-1);
	}
	node->_data = x;
	node->_left = node->_right = NULL;
	return node;
}

//自定义二叉树
BTNode* CreatBinaryTree()
{
	BTNode* nodeA = BuyNode('A');
	BTNode* nodeB = BuyNode('B');
	BTNode* nodeC = BuyNode('C');
	BTNode* nodeD = BuyNode('D');
	BTNode* nodeE = BuyNode('E');
	BTNode* nodeF = BuyNode('F');
	nodeA->_left = nodeB;
	nodeA->_right = nodeC;
	nodeB->_left = nodeD;
	nodeC->_left = nodeE;
	nodeC->_right = nodeF;
	return nodeA;
}

二叉树的遍历（四种）

• 前序遍历，根  左子树  右子树；
• 中序遍历，左子树  根  右子树；
• 后序遍历，左子树  右子树  根；
• 层序遍历，一层一层遍历；

注：深度优先遍历（前序、中序、后序），广度优先遍历（层序）；

1，前序遍历

//前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
		return;
	printf("%c ", root->_data);
	PreOrder(root->_left);
	PreOrder(root->_right);
}

2，中序遍历

//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
		return;
	InOrder(root->_left);
	printf("%c ", root->_data);
	InOrder(root->_right);
}

3，后序遍历

//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
		return;
	PostOrder(root->_left);
	PostOrder(root->_right);
	printf("%c ", root->_data);
}

4，层序遍历

//层序遍历-利用队列
//一个节点出列，入列其子节点
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
    QueueNode* phead;
    QueueNode* ptail;   
}

void LevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if(root)
        QueuePush(&q, root);
    while(!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        printf("%c ", front->val);
        if(front->left)
            QueuePush(&q, front->left);
        if(front->right)
            QueuePush(&q, front->right);
    }
    printf("\n");
    QueueDestroy(&q);
}

二叉树接口

//求二叉树节点个数-递归
//方法一，全局变量或static
int size = 0; 
void BinaryTreeSize(BTNode* root)
{
	if (root)
		size++;
	else
		return;
	BinaryTreeSize(root->_left);
	BinaryTreeSize(root->_right);
}

//方法二，局部变量-传址
void BinaryTreeSize(BTNode* root, int* psize)
{
	if (root)
		(*psize)++;
	else
		return;
	BinaryTreeSize(root->_left, psize);
	BinaryTreeSize(root->_right, psize);
}

//方法三，返回值
int BinaryTreeSize(BTNode* root)
{
	if (root)
		return 1 + BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right);
	else
		return 0;
}

//求二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->_left == NULL && root->_right == NULL)
		return 1;
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

//求二叉树第k层节点个数
//当前树第K层节点个数 = 其左子树的第K-1层节点个数 + 其右子树的第K-1层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}

//求二叉树深度
//当前树深度 = max(左子树深度， 右子树深度) + 1；
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftDepth = BinaryTreeDepth(root->_left);
	int rightDepth = BinaryTreeDepth(root->_right);
	return leftDepth > rightDepth ? (1 + leftDepth) : (1 + rightDepth);
}

//二叉树查找值为x的节点
//先当前节点查找，没有，在去左子树查找，没有，在取右子树查找
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->_data == x)
		return root;

	BTNode* retLeft = BinaryTreeFind(root->_left, x);
	if (retLeft)
		return retLeft;

	BTNode* retRight = BinaryTreeFind(root->_right, x);
	if (retRight)
		return retRight;

	return NULL;
}

//二叉树的销毁
void BinaryTreeDestory(BTNode* root)
{
    if(root==NULL)
        return;
    BinaryTreeDestory(root->left);
    BinaryTreeDestory(root->right);
    free(root);
}

//判断二叉树是否是完全二叉树
//利用层序，空也入列，完全二叉树非空是连续的
bool BinaryTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if(root)
        QueuePush(&q, root);
    while(!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if(front == NULL)
            break;
        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
    }
    while(!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if(front)
        {
            QueueDestroy(&q);
            return false; 
        }
    }
    QueueDestroy(&q);
    return true;
}

试题

• 二叉树的前序遍历(设置子程序);
• 二叉树的中序变量(设置子程序)；
• 二叉树的后序遍历(设置子程序)；
• 单值二叉树；
• 两颗树是否相等(时间复杂度O(N)、空间复杂度即高度O(N))；
• 另一颗树的子树；
• 对称二叉树；
• 根据指定前序遍历的字符串，重构此二叉树；

注：完全二叉树O(log(N))；

附（前序/后序：可得到根，中序：可得到左右树的区间）

• 前序+中序，可重建树；
• 后序+中序，可重建树；
• 前序+后序，不可重建树；