• 链式二叉树

    在这里插入图片描述

    链式二叉树

    一，相关函数接口实现

    所谓链式二叉树，就是存储方式是链式存储的，所以首先要定义出二叉树结点的结构体：

    typedef struct TreeNode
{
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
}TreeNode;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    为了方便测试后面的函数，在这里手动创建一个二叉树
    在这里插入图片描述

    TreeNode* BuyTreeNode(int x)
{
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
	if (!node)
	{
		perror("malloc fail");
		exit(-1);
	}
	node->val = x;
	node->left = node->right = NULL;
	return node;
}
int main()
{
	TreeNode* n1 = BuyTreeNode(1);
	TreeNode* n2 = BuyTreeNode(2);
	TreeNode* n3 = BuyTreeNode(3);
	TreeNode* n4 = BuyTreeNode(4);
	TreeNode* n5 = BuyTreeNode(5);
	TreeNode* n6 = BuyTreeNode(6);
	n1->left = n2;
	n1->right = n4;
	n4->left = n5;
	n4->right = n6;
	n2->left = n3;
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    1，前序遍历

    前序遍历就是先遍历的顺序为：根节点-左子树-右子树

    void PrevOrder(TreeNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    二叉树这里的相关问题都会大量使用递归，为了更直观的看到是如何递归的可以画一下递归展开图：
    在这里插入图片描述

    2，中序遍历

    中序后序与前序没有什么区别就是先遍历根节点与后遍历根节点的区别

    void InOrder(TreeNode* root)
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    3，后序遍历

    void PostOrder(TreeNode* root)
{
	if (root == NULL)
	{
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    4，节点个数

    递归采用的是分治思想，不断地把问题进行细分，直到不可细分为止。
    数结点个数可以这样看：
    对于根节点来说，树的结点数就是根的左子树的节点数+根的右子树的节点数+1（这个1就是根节点）

    int TreeSize(TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    5，叶子结点个数

    叶子结点个数与上面的节点个数有所不同，不能每次都加上根节点的‘1’，而是当某个根节点的左右子树都是空树的时候再返回1。

    int TreeLeafSize(TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    递归展开图：
    在这里插入图片描述

    6，树的高度

    树的高度思想与树的节点数思想类似，但是有区别：
    是左右子树高度大的那一个+根节点的‘1’

    int TreeHeight(TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftheight = TreeHeight(root->left);
	int rightheight = TreeHeight(root->right);
	return leftheight > rightheight ?  leftheight + 1 : rightheight + 1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    7，第K层结点个数

    第k层是相对于根节点的，那么就相当于左右子树的k-1层，这样分治下去直到k==1就返回1。

    int TreeLevelSize(TreeNode* root,int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeLevelSize(root->left, k - 1) + TreeLevelSize(root->right, k - 1);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    8，查找值为X的结点

    如果根节点的值就为x，那么直接返回。否则就先从左子树找，再找不到就去右子树找，直到找到为止，如果树中没有此结点就返回空。

    TreeNode* TreeFind(TreeNode* root, int x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == x)
	{
		return root;
	}
	TreeNode* left = TreeFind(root->left, x);
	if (left)
	{
		return left;
	}
	TreeNode* right = TreeFind(root->right, x);
	if (right)
	{
		return right;
	}
	return NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    9，通过前序遍历数组构建二叉树

    后面的一个OJ题：二叉树的建立及遍历与这个问题相同，放在后面讲解。

    10，销毁二叉树

    销毁二叉树也是采用递归的形式删除，但要注意的是应该先删除左右子树再删除根节点，因为如果先删除根节点就无法找到左右子树了。

    void TreeDestory(TreeNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	TreeDestory(&((*root)->left));
	TreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    11，层序遍历

    剩余的两个问题与前面有所不同，前面的问题都是采用递归的方式解决的，层序遍历和判断是否为完全二叉树都是通过借助队列迭代实现的。
    首先将根节点进队列，在根节点出队列的时候把左右子树（当左右子树不是空树时）带入到队列中，依次进行，直到队列为空为止。
    在这里插入图片描述

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    12，判断是否为完全二叉树

    这个问题最好的解决方法就是利用层序遍历，不过与上面的层序遍历有些区别，就是左右子树为空树的时候也入队列，当出队列的元素是NULL时，若是完全二叉树，则此时队列中的元素都是NULL，反之不是完全二叉树。
    在这里插入图片描述

    bool TreeComplete(TreeNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		TreeNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			while (!QueueEmpty(&q))
			{
				TreeNode* tmp = QueueFront(&q);
				QueuePop(&q);
				if (tmp != NULL)
				{
					return false;
				}
			}
		}
		if (front)
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}
	QueueDestroy(&q);
	return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    二，OJ题实战

    1，单值二叉树

    链接: 单值二叉树
    在这里插入图片描述

    同样采用分治的思想，先比较根与左右子树是否相等，如果不等直接返回false，如果相等，那么左右子树作为新的根节点进行递归。

    bool isUnivalTree(struct TreeNode* root){
    if(root==NULL)
    {
        return true;
    }
    if(root->left&&root->val!=root->left->val)
    {
        return false;
    }
    if(root->right&&root->val!=root->right->val)
    {
        return false;
    }
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    2，检查两棵树是否相同

    链接: 检查两棵树是否相同
    在这里插入图片描述

    思路：先比较根结点如果相同就分治下去左右子树作为新的根，反之则返回false
    但是要注意几点特殊情况：
    一个根节点为空另一个不为空则返回false
    两个根节点都是空则返回true

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    3，另一棵树的子树

    链接: 另一棵树的子树

    在这里插入图片描述
    上面判断两个树是否相等相当于这个问题的子问题，我们只需要依次遍历根结点，左子树，右子树，看是否与subroot是相同的树，如果是就返回true。
    注意：如果左子树与subroot相同就不用看右子树了，直接返回true

    bool issametree(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 issametree(root1->left,root2->left)&&issametree(root1->right,root2->right);
}


bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root==NULL)
    {
        return false;
    }
    if(issametree(root,subRoot))
    {
        return true;
    }
    bool ret1=isSubtree(root->left,subRoot);
    if(ret1)
        return ret1;
    bool ret2=isSubtree(root->right,subRoot);
    if(ret2)
        return ret2;
    return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    4，二叉树的前序遍历

    链接: 二叉树的前序遍历

    在这里插入图片描述
    OJ题中的前序遍历，是要把遍历的结果放到数组中返回，但是要在传参数的时候要注意，控制数组下标的变量传参时要传指针，否则会有麻烦哦。

    void PrevOrder(struct TreeNode* root,int* ret,int* i)
{
    if(root==NULL)
    {
        return ;
    }
    ret[(*i)++]=root->val;
    PrevOrder(root->left,ret,i);
    PrevOrder(root->right,ret,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    if(!root)
    {
        *returnSize=0;
        return NULL;
    }
    int* ret=(int*)malloc(sizeof(int)*100);
    int i=0;
    PrevOrder(root,ret,&i);
    *returnSize=i;
    return ret;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    下面来画一下传参时不传指针造成的后果：
    在这里插入图片描述
    i是记录数组下标的，应该往数组中放一个元素就改变，而向上图中，将3放到数组中后，返回到上一层栈帧此时的i的值仍为2，所以将4放到数组中的时候会把3覆盖掉。
    为了防止这样的错误，我们得采用传i的地址，就不会存在上图中的问题。

    5，二叉树的中序遍历

    链接: 二叉树的中序遍历

    中序后序与前序遍历大同小异

     void InOrder(struct TreeNode* root,int* ret,int* i)
{
    if(root==NULL)
    {
        return ;
    }
    InOrder(root->left,ret,i);
    ret[(*i)++]=root->val;
    InOrder(root->right,ret,i);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    if(!root)
    {
        *returnSize=0;
        return NULL;
    }
    int* ret=(int*)malloc(sizeof(int)*100);
    int i=0;
    InOrder(root,ret,&i);
    *returnSize=i;
    return ret;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    6，二叉树的后序遍历

    链接: 二叉树的后序遍历

     void PostOrder(struct TreeNode* root,int* ret,int* i)
{
    if(root==NULL)
    {
        return ;
    }
    PostOrder(root->left,ret,i);
    PostOrder(root->right,ret,i);
    ret[(*i)++]=root->val;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize){
    if(!root)
    {
        *returnSize=0;
        return NULL;
    }
    int* ret=(int*)malloc(sizeof(int)*100);
    int i=0;
    PostOrder(root,ret,&i);
    *returnSize=i;
    return ret;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    7，对称二叉树

    链接: 对称二叉树

    在这里插入图片描述
    此题与判断两棵树是否相同，非常类似，只需稍加修改即可。
    判断两个数是否相同，先判断根结点，再判断root1的左子树与root2的左子树，而对称二叉树只需对比root1的左子树与root2的右子树，这样交叉对比就可以了。

    bool issametree(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 issametree(root1->left,root2->right)&&issametree(root1->right,root2->left);
}
bool isSymmetric(struct TreeNode* root){
    if(root==NULL)
    {
        return true;
    }
    return issametree(root->left,root->right);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    8，二叉树的建立及遍历

    链接: 二叉树的建立及遍历

    在这里插入图片描述
    根据给定的输入字符串，我们先创建根结点，再创建左右子树，如果字符是‘#’就返回NULL。
    注意：传数组下标i的时候，也要传地址，与上面讲过的问题一样。

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

struct TreeNode
{
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
};
struct TreeNode* TreeCreate(char* str,int* pi)
{
    if(str[*pi]=='\0')
    {
        return NULL;
    }
    if(str[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
    struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val=str[(*pi)++];
    root->left=TreeCreate(str,pi);
    root->right=TreeCreate(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 pi=0;
    struct TreeNode* ret=TreeCreate(str,&pi);
    InOrder(ret);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    9，判断是否为平衡二叉树

    链接: 判断是否为平衡二叉树

    在这里插入图片描述

    这个问题实质就是求二叉树高度函数的复用，每次都判断一下左右子树的高度差，如果大于1就返回false。

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
  • 相关阅读:
    Css Flex 弹性布局中的换行与溢出处理方法
    【Linux网络（一）初识计算机网络】
    python连接postgresql数据库及操作
    通信算法之七十七：无人机设备上的通信系统
    web前端-javascript-标识符(说明,命名规则、不以数字关键字保留字开头、驼峰命名,补充)
    opencv4第二章
    get√接口自动化核心知识点浓缩，为面试加分
    Keil5中复制粘贴中文乱码解决
    Sentinel浅层介绍（上）
    基于K8s构建Jenkins持续集成平台（部署流程）(转)
  • 原文地址：https://blog.csdn.net/Djsnxbjans/article/details/128086647