【数据结构】二叉树

一、二叉树的遍历

遍历顺序 

前序：根，左子树，右子树

中序：左子树，根，右子树

后序：左子树，右子树，根

N代表空元素

前序 1 2 3 N N N 4 5 N N 6 N N

中序 N 3 N 2 N 1 N 5 N 4 N 6 N

后序 N N 3 N 2 N N 5 N N 6 4 1

层序 1 2 4 3 5 6一层层从左到右 

一个树分成根和子树，子树再分为根和子树

二、代码实现

2.1 前中后续

void PreOrder(BTNode* root)
{
	//根 左子树 右子树
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}
void InOrder(BTNode* root)
{
	//左子树 根 右子树
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

void EndOrder(BTNode* root)
{
	//左子树 右子树 根
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	EndOrder(root->left);
	EndOrder(root->right);
	printf("%d ", root->val);
}

总的概况就是函数栈帧创建销毁，再创建，再销毁

2.2统计节点个数

分治

1.递归子问题

2.返回条件（最小子问题）

 1.节点个数 == 左子树的节点个数 + 右子树的节点个数 + 1 （+1是根节点的个数）

 2.如果节点为空则返回0

int TreeSize(BTNode* root)
{
	return root == NULL ? 0 :
		TreeSize(root->left) + TreeSize(root->right) + 1;
}

每个矩形代表的是一个空间，画了左子树 ，右子树类似

2.3计算树高度 

分治

1.递归子问题

2.返回条件（最小子问题）

 1.最高的高度 == 最高的左子树 + 1 或者是 最高的右子树 + 1（+1是加自身的节点）

 2.如果节点为NULL返回0

int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDepth = TreeHeight(root->left);
	int rightDepth = TreeHeight(root->right);
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

2.4计算第k层树的节点个数 

分治

1.递归子问题

2.返回条件（最小子问题）

1. 树的第k层节点个数 == 左子树的第k-1层个数 + 右子树的第k-1层个数 

2. root不为NULL且k等于1

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

	if (k == 1)
	{
		return 1;
	}
	
	int leftk = Treelevel(root->left, k - 1);
	int rightk = Treelevel(root->right, k - 1);
	return leftk + rightk;
}

1的第三层 = 左子树2的第2层 + 右子树4的第2层

 左子树2的第2层 = 左子树的3的第1层 + 右子树的NULL的第1层

右子树4的第2层 = 左子树的5的第1层 + 右子树的6的第1层

2.5查找二叉树某个节点

分治

1.递归子问题

2.返回条件（最小子问题）

 1.左子树找，找不到去右子树找，还找不到为NULL

 2.找到了返回根节点，根节点为NULL返回NULL

BTNode* TreeFind(BTNode* root, int x)
{
	if (root == NULL)
		return NULL;
	if (root->val == x)
		return root;
	BTNode* ret1 = TreeFind(root->left, x);
	if (ret1)
		return ret1;
	BTNode* ret2 = TreeFind(root->right, x);
	if (ret2)
		return ret2;

	return NULL;
}

 2.6层序遍历

这里使用队列

层序遍历使用的方法是上一层带下一层

出 1 进 2 4 ，然后出 2 进 3 空 ，然后出 4 进 5 6以此类推

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty)
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//如果不为NULL则打印N
		if (front)
		{
			printf("%d ", front->data);

			//带入下一层
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
		else {
			printf("N ");
		}
	}
	printf("\n");

	QueueDestroy(&q);
}

2.7判断二叉树是否是完全二叉树

这里采用的是层序的遍历思想

如果是完全二叉树后面就是：非空 空

如果不是则：非空 空 非空 空

区别就是完全二叉树后面全是空，非完全二叉树后面又有空又有非空

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)
		{
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

三、二叉树练习题

3.1相同的树

思路：

1.子问题：左子树和左子树比，右子树和右子树比

2.最小问题：两颗树不能为NULL，一颗树为NULL另一颗树不为NULL也不行

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    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);
}

 思考：能不能把下面条件变成p->val == q->val，不行因为他们即使相等也不能说这是相同的树

if(p->val!=q->val)
    {
        return false;
    }

 3.2对称的二叉树

思路：

先分成两颗树分别为左子树，右子树 

1.子问题：A左子树跟B右子树比

2.最小问题：跟相同的数的子问题一样

 bool _isSymmetric(struct TreeNode*A,struct TreeNode*B)
 {
    if(A == NULL && B == NULL)
    {
        return true;
    }
    if(A == NULL||B ==NULL)
    {
        return false;
    }
    if(A->val!=B->val)
    {
        return false;
    }

    return _isSymmetric(A->left,B->right)&&_isSymmetric(A->right,B->left);
 }
bool isSymmetric(struct TreeNode* root) {
    bool ret = _isSymmetric(root->left,root->right);
    return ret;
}

 3.3二叉树的前序遍历

先遍历一遍二叉树，返回节点个数可以节省开辟的空间 

int TreeSize(struct TreeNode* root)
 {
    return root == NULL? 0 :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) {
    *returnSize = TreeSize(root);
    int* a = malloc(sizeof(int)*(*returnSize));
    int i = 0;
    preorder(root,a,&i);
    return a;
}

3.4 二叉树的遍历

思路：

1.先建左子树再建右子树

2.当为叶子节点后为NULL时返回NULL 

个人觉得，建树的时候最难

1.传递的是地址

2.建立一个根节点就要开辟一个空间 

typedef struct BinaryTree
{
    struct BinaryTree* left;
    struct BinaryTree* right;
    char val;
}BT;
BT* creatTree(char* a,int* i)
{
    if(a[*i] == '#')
    {
        (*i)++;
        return NULL;
    }
    BT* root = (BT*)malloc(sizeof(BT));
    root->val = a[(*i)++];
    root->left = creatTree(a, i);
    root->right = creatTree(a, i);
    return root;
}
void inOrder(BT* root)
{
    if(root == NULL)
    {
        return;
    }
    inOrder(root->left);
    printf("%c ",root->val);
    inOrder(root->right);
}
int main()
{
    char a[100];
    scanf("%s",a);
    int i = 0;
    BT* root = creatTree(a,&i);
    inOrder(root);
    return 0;
}

3.5另一颗树的子树 

思路： 

1.找到相同节点

2.然后左右子树比较

不能按照以上思路思考，会不全面

应该每个节点都要遍历

1.遍历p，q的左子树和右子树

2.跟相同树的子问题一样

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    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);
}