【数据结构初阶】链式二叉树接口实现+痛苦的OJ题

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyBTNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	newnode->left = newnode->right = NULL;
	newnode->data = x;

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

	n1->left = n2;
	n2->left = n3;
	n1->right = n4;
	n4->left = n5;
	n4->right = n6;//这样我们就手动建立了一棵二叉树

	return 0;
}

void PrevOrder(BTNode* root)//根，左子树，右子树
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
void InOrder(BTNode* root)//左子树，根，右子树
{
	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 BinaryTreeSize(BTNode* root)//先得到左子树结点个数再获得右子树节点个数再加1，就得到整个二叉树的结点个数了
{
	if (root == NULL)
		return 0;
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

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);
}

int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);//把返回的结果记录下来

	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)//都已经找到空结点的位置了还是没找到或者这就是一个空树，肯定不存在我要找的值
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	return BinaryTreeFind(root->left, x)||
	BinaryTreeFind(root->right, x);
}

int BinaryTreeLevelKSize(BTNode* root, int k)//k层结点个数 = 左子树的k-1层结点个数 + 右子树的k-1层节点个数
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) +
	BinaryTreeLevelKSize(root->right, k - 1);

}

void BinaryTreeDestory(BTNode** root)
{
	if (root == NULL)
		return;
	
	BinaryTreeDestory((*root)->left);
	BinaryTreeDestory((*root)->right);
	free(*root);//将每一个根节点都置空了。
	*root = NULL;
}

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);//队列中存放的数据应该是二叉树的每个结点，但由于结点拷贝空间太大，我们存放每个结点的地址
	if (root)
		QueuePush(&q, root);//root不是空，将根节点指针入队列
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);
		QueuePop(&q);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
}

bool TreeComplete(BTNode* root)
{

	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)//遇到NULL，就可以开始判断是否为完全二叉树了
		{
			break;
		}
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}

	//出到NULL以后，如果后面全是空，则是完全二叉树，如果有非空结点，那就不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		
		if (front != NULL)
		{
			QueueDestroy(&q);//防止内存泄露
			return false;
		}
	}
	QueueDestroy(&q);//如果别人写的是带有哨兵卫结点的队列的话，这里有destroy的话，也可以防止内存泄露
	//即使是队列为空的时候，再删除也不会报错，因为队列为空，说明动态开辟的结点已经全部释放完毕了，head和tail也都为NULL了
	//所以会直接从QueueDestroy中的while循环跳出来，不进行节点空间的释放。

	return true;//return一不小心就内存泄漏了，因为如果不是完全二叉树的话，队列里还是有结点的空间是没有释放的，所以很容易造成内存泄露
}

bool isUnivalTree(struct TreeNode* root){
    if(root==NULL)
        return true;
    if(root->left&&root->left->val!=root->val)//左边不等于空的时候，我们才可以和左进行比较
        return false;

    if(root->right&&root->right->val!=root->val)
        return false;
    
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

int maxDepth(struct TreeNode* root){
    if(root==0)
        return 0; 
    if(root->left==NULL&&root->right==NULL)
        return 1;
    int left=maxDepth(root->left);
    int right=maxDepth(root->right);
    return left>right?left+1:right+1;

}

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //1.每一层递归的逻辑，就是先比较根，再比较左子树的根节点，然后比较右子树的根节点
    if(p==NULL&&q==NULL)
        return true;
    //这时候只要有一个结点为空，那就说明两个结点不相等
    if(p==NULL||q==NULL)
        return false;
    if(p->val!=q->val)
        return false;
    //上面这些代码都是单层的逻辑
    
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    //到了这里说明此时比较的两个结点值相同，我们继续比较左子树的根结点和右子树的根节点
    //左和右都相等才能说明两个树相同
}

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //1.每一层递归的逻辑，就是先比较根，再比较左子树的根节点，然后比较右子树的根节点
    if(p==NULL&&q==NULL)
        return true;
    //这时候只要有一个结点为空，那就说明两个结点不相等
    if(p==NULL||q==NULL)
        return false;
    if(p->val!=q->val)
        return false;
    //上面这些代码都是单层的逻辑
    
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    //到了这里说明此时比较的两个结点值相同，我们继续比较左子树的根结点和右子树的根节点
    //左和右都相等才能说明两个树相同
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    //拿右边的树和左边的每一棵子树进行比较，如果和其中某一棵子树相等，就返回true
    
    if(root==NULL)//根节点都为空了，说明肯定root没有subroot
        return false;
    
    if(isSameTree(root,subRoot))
        return true;
    
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
    //你如果把这里的函数调用不小心改成上面的函数来进行调用的话，就相当于你只对root的两个子树
    //查找了一下，剩余的子树根本没查找


}//默认subroot不为空

//递归结束的条件是什么呢？
//1.就是如果我从左边的树中找到我的右边的树了，那就递归结束了
//2.或者来root以及root的左和右子树中找了半天，到NULL了都还没找到，那递归也应该结束了

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


struct TreeNode
{
    char val;
    struct TreeNode*left;
    struct TreeNode*right;
};

struct TreeNode*rebulidTree(char*str,int* pi)//我们这里应该传i的地址，过去，如果不这么干，每个函数栈帧都有自己的i，i++的时候，+的不是同一个i
{
    if(str[*pi]=='#')//必须是#，我们才往后++
    {
       (*pi)++;
        return NULL;
    }
       

    struct TreeNode*root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val=str[(*pi)++];

    root->left=rebulidTree(str, pi);
    root->right=rebulidTree(str, pi);
    return root;

}
void InOrder(struct TreeNode*root)
{
    if(root==NULL)
        return;
    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);
}
int main() {
    char str[100];
    scanf("%s",str);    
    int i=0;
    struct TreeNode*root=rebulidTree(str,&i);//传i的地址的话，上面函数的每次调用操作的就是同一个i了
    //如果不用指针，绝对会出问题
    InOrder(root);

    return 0;
}
//递归建立一棵二叉树
//递归中序遍历二叉树
//递归需要传参，我们需要额外定义函数

struct TreeNode* invertTree(struct TreeNode* root){

    if(root==NULL)
        return NULL;
    struct TreeNode*tmp=root->left;
    root->left=root->right;
    root->right=tmp;
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

bool _isSymmetric(struct TreeNode*root1,struct TreeNode*root2)
{
    if(root1==NULL&&root2==NULL)
        return true;
    if(root1==NULL||root2==NULL)
        return false;
    if(root1->val!=root2->val)
        return false;
    return _isSymmetric(root1->left,root2->right)&&
    _isSymmetric(root1->right,root2->left);

}
bool isSymmetric(struct TreeNode* root){
    return _isSymmetric(root->left,root->right);
}

int TreeSize(struct TreeNode*root)
{
    if(root==NULL)
        return 0;
    return TreeSize(root->left)  + TreeSize(root->right) + 1;
}
void preorder(struct TreeNode* root,int*a,int*pi)
{
    if(root==NULL)
        return;
    a[(*pi)++]=root->val;
    preorder(root->left,a,pi);
    preorder(root->right,a,pi);

}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int size=TreeSize(root);
    *returnSize=size;
    int*a=(int*)malloc(sizeof(int)*size);//开辟一个数组
    int i=0;
    preorder(root,a,&i);
    return a;
}

int TreeHeight(struct TreeNode* root)
{
    if(root==NULL)
        return 0;
    if(root->left==NULL&&root->right==NULL)
        return 1;
    int left=TreeHeight(root->left);
    int right=TreeHeight(root->right);
    return left>right?left+1:right+1;
}
bool isBalanced(struct TreeNode* root){
    if(root==NULL)
        return true;
    int left=TreeHeight(root->left);
    int right=TreeHeight(root->right);
    if(abs(left-right)>1)
        return false;

    return isBalanced(root->left)&&isBalanced(root->right);
}