特殊的二叉树

二叉树的一些重要性质

二叉树储存结构

顺序储存

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树

会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，二叉树顺序存储在物理上是一个数

组，在逻辑上是一颗二叉树。

 

 链式储存

// 二叉链的创建
typedef int BTDataType;
structBinaryTreeNode
{
    structBinTreeNode*Left;   // 指向当前节点左孩子   
    structBinTreeNode*Right; // 指向当前节点右孩子    
    BTDataType_data; // 当前节点值域
}

// 三叉链的创建
structBinaryTreeNode
{
    structBinTreeNode*Parent; // 指向当前节点的双亲    
    structBinTreeNode*Left;   // 指向当前节点左孩子    
    structBinTreeNode*Right; // 指向当前节点右孩子
    BTDataType_data;          // 当前节点值域
}；

链式结构的实现

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中

3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

 

代码实现 

前中后序的实现

//  二叉树的实现
typedef char TDataType;
typedef struct BTreeNode
{
	struct BTreeNode*left;
	struct BTreeNode*right;
	TDataType data;
}BTNode;
//前序遍历
void PrevOrder(BTNode*root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	else
	{
		printf("%c ", root->data);
		PrevOrder(root->left);
		PrevOrder(root->right);
	}
}

//中序遍历
void InOrder(BTNode*root)
{
	if (root== NULL)
	{
		printf("NULL ");
		return;
	}
	else
	{
		InOrder(root->left);
		printf("%c ", root->data);
		InOrder(root->right);
	}
}

//后序遍历
void PostOrder(BTNode*root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	else
	{
		PostOrder(root->left);
		PostOrder(root->right);
		printf("%c ", root->data);
	}
}

计算二叉树节点个数

//分治算法
int  BTreeSize(BTNode*root)
{
	return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1;
    //节点个数=左子树节点个数+右子树节点个数+1，1是指该树根的节点
    
}

计算叶子节点个数

//计算叶子数    分治算法
int  BTreeLeafSize(BTNode*root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL&&root->right == NULL)  //若该树的没有左子树和右子树则就是叶子
		return 1;
	else     //若有右子树或者右子树 则继续向下遍历访问
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
	
}

计算二叉树的最大深度

int maxDepth(struct TreeNode* root) 
{
    if(root==NULL)
    {
        return 0;
    }
    else
    {
        int leftdepth=maxDepth(root->left); //左子树的最大深度
        int rightdepth=maxDepth(root->right); //右子树的最大深度
        
        return leftdepth>rightdepth?leftdepth+1:rightdepth+1; //总的深度 = max（左子树深度，右子树深度）+ 1 
    }
}

层序遍历

void BTreeLevelorder(BTNode*root)
{
	Queue q;              //使用队列实现层序遍历 
	QueueInit(&q);   

	if (root != NULL)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode*front = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", front->data);
    
     //上一层带出下一层
		if (front->left != NULL)
			QueuePush(&q, front->left);
		if (front->right != NULL)
			QueuePush(&q, front->right);
	}
	printf("\n");
	
}