[C]二叉树的实现——喵喵成长记

代码实现

typedef char BTDataType;
 
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;
 
// 通过前序遍历的数组"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);

#include "BTree.h"
#include "queue.h" 
#include "stack.h"
 
BTNode *BinaryTreeCreate(BTDataType * src, int n, int* pi)
{
	if (*pi >= n || src[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
 
	BTNode * cur = (BTNode *)malloc(sizeof(BTNode));
	cur->_data = src[*pi];
	(*pi)++;
 
	cur->_left = BinaryTreeCreate(src, n, pi);
	cur->_right = BinaryTreeCreate(src, n, pi);
 
	return cur;
}
 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root)
	{ 
		putchar(root->_data);
		BinaryTreePrevOrder(root->_left);
		BinaryTreePrevOrder(root->_right);
	}
}
 
void BinaryTreeInOrder(BTNode* root)
{
	if (root)
	{
		BinaryTreeInOrder(root->_left);
		putchar(root->_data);
		BinaryTreeInOrder(root->_right);
	}
}
 
void BinaryTreePostOrder(BTNode* root)
{
	if (root)
	{
		BinaryTreePostOrder(root->_left);
		BinaryTreePostOrder(root->_right);
		putchar(root->_data);
	}
}
 
void BinaryTreeDestory(BTNode** root)
{
	if (*root)
	{
		BinaryTreeDestory(&(*root)->_left);
		BinaryTreeDestory(&(*root)->_right);
		free(*root);
        *root = NULL;
	}
}
 
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue qu;
	BTNode * cur;
 
	QueueInit(&qu);
 
	QueuePush(&qu, root);
 
	while (!QueueIsEmpty(&qu))
	{
		cur = QueueTop(&qu);
 
		putchar(cur->_data);
 
		if (cur->_left)
		{
			QueuePush(&qu, cur->_left);
		}
 
		if (cur->_right)
		{
			QueuePush(&qu, cur->_right);
		}
 
		QueuePop(&qu);
	}
 
	QueueDestory(&qu);
}
 
int BinaryTreeComplete(BTNode* root)
{
	Queue qu;
	BTNode * cur;
	int tag = 0;
 
	QueueInit(&qu);
 
	QueuePush(&qu, root);
 
	while (!QueueIsEmpty(&qu))
	{
		cur = QueueTop(&qu);
 
		putchar(cur->_data);
 
		if (cur->_right && !cur->_left)
		{
			return 0;
		}
 
		if (tag && (cur->_right || cur->_left))
		{
			return 0;
		}
 
		if (cur->_left)
		{
			QueuePush(&qu, cur->_left);
		}
 
		if (cur->_right)
		{
			QueuePush(&qu, cur->_right);
		}
		else
		{
			tag = 1;
		}
 
		QueuePop(&qu);
	}
 
	QueueDestory(&qu);
	return 1;
}

二叉树的练习题

965. 单值二叉树

简单

197

相关企业

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

示例 1：

输入：[1,1,1,1,1,null,1]
输出：true

示例 2：

输入：[2,2,2,5,2]
输出：false
提示

1. 给定树的节点数范围是 [1, 100]。
2. 每个节点的值都是整数，范围为 [0, 99] 。

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

   ---

   100. 相同的树

   简单

   1.1K

   相关企业

   给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

   如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

   示例 1：

   

   输入：p = [1,2,3], q = [1,2,3]
   输出：true
   

   示例 2：

• 

  输入：p = [1,2], q = [1,null,2]
  输出：false
  

  示例 3：

  输入：p = [1,2,1], q = [1,1,2]
  输出：false
  

  提示：

• 

1. 两棵树上的节点数目都在范围 [0, 100] 内

• -104 <= Node.val <= 104

  bool isSameTree(struct TreeNode* p, struct TreeNode* q){
  if(p==NULL&&q==NULL)
  return true;
  else if(p==NULL||q==NULL)
  {
  return false;
  }
  else if(p->val!=q->val)
  {
      return false;
  }
  else{
      return  isSameTree(p->left,q->left)&& isSameTree(p->right,q->right);
  }
   
  }
  

  ---

  101. 对称二叉树

  简单

  2.6K

  相关企业

  给你一个二叉树的根节点 root ， 检查它是否轴对称。

  示例 1：

• 

1. 输入：root = [1,2,2,3,4,4,3] 输出：true

2. 示例 2：

   

   输入：root = [1,2,2,null,3,null,3]
   输出：false
   

   提示：

3. 树中节点数目在范围 [1, 1000] 内
4. -100 <= Node.val <= 100

 bool check(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 check(p->left,q->right)&&check(p->right,q->left);
     else
     return false;
}
bool isSymmetric(struct TreeNode* root){
     return check(root,root);
}

总结

来嘛，来嘛，笑一个，今天的你也是超级赞滴，喵~

宝子，你不点个赞吗？不评个论吗？不收个藏吗？

最后的最后，关注我，关注我，关注我，你会看到更多有趣的博客哦！！！

喵喵喵，你对我真的很重要。