二叉树

程序员文章站 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);

}

二叉树

Java中二叉树的建立和各种遍历实例代码

二叉树的遍历算法(详细示例分析)

Java实现的二叉树常用操作【前序建树，前中后递归非递归遍历及层序遍历】

关于c#二叉树的实现

Java语言描述二叉树的深度和宽度

图解二叉树的三种遍历方式及java实现代码

C#非递归先序遍历二叉树实例

Java二叉树路径和代码示例

java编程求二叉树最大路径问题代码分析

Java实现二叉树的深度优先遍历和广度优先遍历算法示例