欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树

程序员文章站 2022-05-06 21:36:48
...

二叉树的描述

struct TreeNode {
    int val;  //根节点存储的数据
    struct TreeNode *left; //根节点的左孩子
    struct TreeNode *right; //根节点的右孩子
};

    二叉树是一种特殊的树,特殊之处就在于,它好像每一个根最多只能有两个分叉,并且它在逻辑和物理上是一个倒着的树,它的根节点在上面,自上而下进行分叉。

二叉树的组织
    既然二叉树是一种倒着存放的结构,那么它的定义就可以使用递归来实现

//初始化
void BinaryTreeInit(BTNode* pt);
//二叉树的深度
int BinaryTreeDepth(BTNode* root);
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

二叉树的初始化呢,就是让根节点的左右子树都等于NULL,毕竟初始化只是一个根嘛

//初始化
void BinaryTreeInit(BTNode* pt)
{
	pt->_left = pt->_right = NULL;
}

求二叉树的深度,可以采用递归来实现,先找到叶子节点,然后逐层向上,直到根节点位置

//二叉树的深度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	//求左子树的深度
	int lDepth = BinaryTreeDepth(root->_left) + 1;
	//求右子树的深度
	int rDepth = BinaryTreeDepth(root->_right) + 1;
	//返回左右子树最深的一个深度给上一层的根
	return lDepth > rDepth ? lDepth : rDepth;
}

    通过前序遍历来构建一颗二叉树,构建二叉树要注意的是我们直接输入的时候,无法分辨出哪一个是叶子节点,不能找到左子树停止的条件,这时就需要一个符号来表示这棵树的叶子节点的下一层,以此来区分叶子节点和其他节点。
二叉树

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (n <= *pi || a[*pi] == '#')
	{
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	BinaryTreeInit(root);
	root->_data = a[*pi];

	(*pi)++;
	root->_left = BinaryTreeCreate(a, n,pi);
	(*pi)++;
	root->_right = BinaryTreeCreate(a, n,pi);
	return root;
}

二叉树的销毁,这里要采取后序遍历的方式来进行销毁,所传的参数得是这个树每一个根节点的地址

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}

	BinaryTreeDestory(&(*root)->_left);
	BinaryTreeDestory(&(*root)->_right);
	free(*root);
}

二叉树所有结点个数,叶子结点的个数,第K层的节点个数

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	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 && !root->_right)
	{
		return 1;
	}

	return BinaryTreeLeafSize(root->_left) \
		+ BinaryTreeLeafSize(root->_right);
}

// 二叉树第k层节点个数
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);
}

二叉树查找值为K的结点(采取的是先序遍历)

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}

	if (root->_data == x)
	{
		return root;
	}
	BTNode* node;
	node = BinaryTreeFind(root->_left, x);
	//如果左子树返回后的结果不是NULL
	//就说明找到了该结点,直接返回
	if (node != NULL)
	{
		return node;
	}
	//左子树返回结果是空
	//说明结点可能在右子树
	node = BinaryTreeFind(root->_right, x);
	return node;
}

二叉树的递归遍历,二叉树在遍历时,不论它是先序,中序还是后序,都是只能打印一个根结点,讲所有的节点都当成不同情况的一个根结点来进行打印。

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	BinaryTreeInOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right);
}

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c ", root->_data);
}

非递归遍历,这里需要利用栈的后进先出的特性,来找到当前子树根结点的上一层根结点,然后再进行判断

//非递归中序遍历
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    int* a=(int*)malloc(sizeof(int)*1000);
    *returnSize=0;
    if(root==NULL)
    {
        return a;
    }
    Stack* st=(Stack*)malloc(sizeof(Stack));
    StackInit(st);
    struct TreeNode* p=root;
	//如果栈为空  并且根节点为空,则跳出循环
    while(p!=NULL || StackEmpty(st)==0)
    {
    	//如果P不为空,说明左子树还没有遍历完毕
    	//继续遍历左子树,并保存当前根节点
        if(p!=NULL)
        {
            StackPush(st,p);
            p=p->left;
        }
        else
        {
        	//此时 P为空,通过弹栈来拿到上一层的跟节点
        	//打印跟节点,再判断跟节点右节点的情况
            p=StackTop(st);
            StackPop(st);
            a[(*returnSize)++]=p->val;
            p=p->right;
        }
    }
    return a;
}

//非递归后序遍历
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    int* a=(int*)malloc(sizeof(int)*1000);
    *returnSize=0;
    if(root==NULL)
    {
        return a;
    }
    Stack* st=(Stack*)malloc(sizeof(Stack));
    StackInit(st);
    struct TreeNode* p=root;
    struct TreeNode* q=NULL;
	//如果栈为空  并且根节点为空,则跳出循环
    while(p!=NULL || StackSize(st)!=0)
    {
   		//如果P不为空,说明左子树还没有遍历完毕
    	//继续遍历左子树,并保存当前根节点
        if(p!=NULL)
        {
            StackPush(st,p);
            p=p->left;
        }
        else
        {
        	//此时左子树已经遍历完毕
            p=StackTop(st);
            //再通过弹栈拿到上一层跟节点
            //如果根的右节点是空,或者它的右节点已经遍历过了
            //就打印当前根节点
            if((p->right==NULL) || (p->right==q))
            {
                a[(*returnSize)++]=p->val;
                StackPop(st);

                q=p;//保存上一个打印的节点
                p=NULL;
            }
            else
            {
                p=p->right;
            } 
        }
    }
    return a;
}

二叉树的层序遍历(层序需要利用队列先进先出的特性,保证每一层都是按照从左到右的顺序来打印的)

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	//建立一个队列
	Queue* qu = (Queue*)malloc(sizeof(Queue));
	QueueInit(qu);
	QueuePush(qu, root);


	while (!QueueEmpty(qu))
	{
		int i = 0;
		//获取当前层节点数
		int num = QueueSize(qu);
		for (i = 0; i < num; i++)
		{
			BTNode* node = QueueFront(qu);
			printf("%c ", node->_data);
			//左右子树不为空 入队列
			if (node->_left)
			{
				QueuePush(qu, node->_left);
			}

			if (node->_right)
			{
				QueuePush(qu, node->_right);
			}
			//队头元素出队列
			QueuePop(qu);
		}
		printf("\n");
	}
}

判断是否是完全二叉树
还是利用队列先进先出的特点,一层一层来判断,如果遇到根节点为NULL,就判断队列中其他数据有没有非空的,如果有,就不是一个完全二叉树。

// 判断二叉树是否是完全二叉树
//返回值为 0 --> 不是完全二叉树
//返回值为 1 --> 是完全二叉树 
int BinaryTreeComplete(BTNode* root)
{
	if (root == NULL)
	{
		return 1;
	}

	//建立一个队列
	Queue* qu = (Queue*)malloc(sizeof(Queue));
	QueueInit(qu);
	QueuePush(qu, root);


	while (!QueueEmpty(qu))
	{
		int i = 0;
		//获取当前层节点数
		int num = QueueSize(qu);
		for (i = 0; i < num; i++)
		{
			BTNode* node = QueueFront(qu);
			//如果遇到空节点,就开始判断是否为完全二叉树
			if (node == NULL)
			{
				int j = 0;
				int count = QueueSize(qu);
				for (j = 0; j < count; j++)
				{
					BTNode* cur = QueueFront(qu);
					if (cur)
					{
						return 0;
					}
					QueuePop(qu);//队头元素出队列
				}
				return 1;
			}
			//左右子树入队列
			QueuePush(qu, node->_left);
			QueuePush(qu, node->_right);
			//队头元素出队列
			QueuePop(qu);
		}
	}
	return 1;
}

LeetCode一些二叉树的简单面试题
1.单值二叉树
如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时,才返回 true;否则返回 false。二叉树二叉树

bool isUnivalTree(struct TreeNode* root){
    if(root==NULL)
    {
        return true;
    }

    //如果左子树不是空 根节点和左子树的值不相等,返回false
    if(root->left!=NULL && root->val!=root->left->val)
    {
        return false;
    }
    //如果右子树不是空 根节点和右子树的值不相等,返回false
    if(root->right!=NULL && root->val!=root->right->val)
    {
        return false;
    }
    //递归判断根节点的左右子树的情况
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

2.翻转一棵二叉树
二叉树
这里也是用先序遍历二叉树的思想,进行左右子树的交换

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

3.相同的树
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
二叉树

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //如果根节点同时为空,可以是相同的
    if(p==NULL && q==NULL)
    {
        return true;
    }

    //根节点 只有一个为空 则为不同的树
    if(p==NULL || q==NULL)
    {
        return false;
    }
    //根节点的值不同也不是相同的树
    if(q->val!=p->val)
    {
        return false;
    }
    //递归遍历每个树的左右子树,然后结果与一下
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

4.对称二叉树
给定一个二叉树,检查它是否是镜像对称的。二叉树
树都可以分成根节点,左子树和右子树三部分,对称二叉树则是判断左子树的右子树 和 右子树的左子树是否相同

bool isJudge(struct TreeNode* left,struct TreeNode* right)
{

    if(left==NULL && right==NULL)
    {
        return true;
    }

    if(left==NULL || right==NULL)
    {
        return false;
    }

    if(left->val!=right->val)
    {
        return false;
    }

    return isJudge(left->left,right->right) && isJudge(right->left,left->right);
}

//判断是否对称
bool isSymmetric(struct TreeNode* root){
    if(root==NULL)
    {
        return true;
    }

    //递归判断第一个根节点的左右子树是否是相同的
    return isJudge(root->left,root->right);
}

5.另一个树的子树
给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
二叉树
二叉树
是一个判断两颗树是否相同的思想,树都可以分成根节点,左子树和右子树三部分,再利用拆分的这一点,判断两棵树是否相等


bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p==NULL && q==NULL)
    {
        return true;
    }
    if(p==NULL || q==NULL)
    {
        return false;
    }

    
    if(q->val!=p->val)
    {
        return false;
    }
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

bool isSubtree(struct TreeNode* s, struct TreeNode* t){
    if(s == NULL)
    {
        return false;
    }
    
    //二叉树的拆分,判断两个树是否相同 中间为或的关系
    return isSameTree(s,t) || \
                isSubtree(s->left,t) || \
                isSubtree(s->right,t);

}

6.平衡二叉树判断
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
二叉树二叉树

//求树的深度
int len(struct TreeNode* root)
{
    if(root==NULL)
    {
        return 0;
    }
    int a=len(root->left)+1;
    int b=len(root->right)+1;
    return a>b?a:b;
}

bool isBalanced(struct TreeNode* root){
    if(root==NULL)
    {
        return true;
    }
    //递归找到左右子树的深度
    int a=len(root->left);
    int b=len(root->right);
    //返回左右子树相减后的真值
    return abs(a-b)<2 \
            && isBalanced(root->left)\
             && isBalanced(root->right);

}
相关标签: C语言 二叉树