二叉树前中后序遍历+刷题【中】【数据结构/初阶/C语言实现】

// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("# ");
    return;
  }
  printf("%d ", root->data);
  BinaryTreePrevOrder(root->left);
  BinaryTreePrevOrder(root->right);
}

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("# ");
    return;
  }
  BinaryTreeInOrder(root->left);
  printf("%d ", root->data);
  BinaryTreeInOrder(root->right);
}

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("# ");
    return;
  }
  BinaryTreePostOrder(root->left);
  BinaryTreePostOrder(root->right);
  printf("%d ", root->data);
}

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
  //创建并初始化队列
  Queue q;
  QueueInit(&q);
  //把根结点放入
  if (root)
  {
    QueuePush(&q, root);
  }
  //每次只取队头元素(当前的根结点),
  //然后将当前根结点的非空孩子结点存入
  //终止条件:队空
  while (!QueueEmpty(&q))
  {
    //取队头元素后pop
    BTNode* front = QueueFront(&q);
    printf("%d ", front->data);
    QueuePop(&q);
    if (front->left)
    {
      QueuePush(&q, front->left);
    }
    if (front->right)
    {
      QueuePush(&q, front->right);
    }
  }
  QueueDestory(&q);
}

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
  /*if (root == NULL)
    return 0;
  return   BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;*/
  return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  if (root->left == NULL && root->right == NULL)
    return 1;
  return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
  assert(k >= 1);
  if (root == NULL)
    return 0;
  if (k == 1)
    return 1;
  return BinaryTreeLevelKSize(root->left, k - 1) 
         + BinaryTreeLevelKSize(root->right, k - 1) + 1;
}

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
    return NULL;
  if (root->data == x)
  {
    printf("%d\n", root->data);
    return root;
  }
  BinaryTreeFind(root->left, x);
  BinaryTreeFind(root->right, x);
}

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

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 isSameTrree(p->left, q->left) 
        && isSameTree(p->right, q->right);
}

bool isSymmetricSubTree(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 isSymmetricSubTree(root1->left, root2->right)
        && isSymmetricSubTree(root1->right, root2->left);
}
bool isSymmetric(struct TreeNode* root){
    //先处理根结点
    if(root == NULL)
        return true;
    //剩下的都是根结点不为空的情况
    return isSymmetricSubTree(root->left, root->right);
}

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){
    //遍历每个结点,与subRoot比较
    if(root == NULL)
        return false;
    if(isSametree(root, subRoot))
        return true;
    //注意||而不是&&
    return isSubtree(root->left, subRoot)
        || isSubtree(root->right, subRoot);
}

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

#include <stdio.h>
#include <stdlib.h>
//创建二叉树结点
typedef char BTDataType;
typedef struct BTNode
{
    struct BTNode* left;
    struct BTNode* right;
    BTDataType data;
}BTNode;
BTNode* CreateNode(BTDataType x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    newnode->data = x;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}
//前序遍历存入数组
BTNode* CreateBinaryTree(char* str, int* pi)
{
    if(str[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root = CreateNode(str[(*pi)++]);
    root->left = CreateBinaryTree(str, pi);
    root->right = CreateBinaryTree(str, pi);
    return root;
}
//中序遍历打印
void InOrder(struct BTNode* root)
{
    if(root == NULL)
        return;
    InOrder(root->left);
    printf("%c ", root->data);
    InOrder(root->right);
}
int main()
{
    char str[100];
    scanf("%s", str);
    int i = 0;
    BTNode* root = CreateBinaryTree(str, &i);
    InOrder(root);
    return 0;
}