🍔 构建二叉树

🚩构建二叉树的时候要先来引用一道牛客网的题目二叉树遍历_牛客题霸_牛客网 (nowcoder.com)这个是它的链接可以试着去做一下

✅ 题目要求：

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

🥝 示例：

输入：abc##de#g##f###

输出：c b e g d f a

🍟示例的实际图应该是下图这样的一颗树

082ad718504c775ca9d7ea5d72225f1a_fb5c9888ba8940ab953c61e3d8e10a34.png

🥰解题思路：这个题目要我们构造一个链式二叉树，在先序遍历的过程中构建每一个节点。

😍代码：

#include <stdio.h>
#include <malloc.h>
typedef struct BTNode
{
    char _data;
    struct BTNode* _left;
    struct BTNode* _right;
}BTNode;
//中序遍历
void Inorder(BTNode* root)
{
    if(root)
    {
        Inorder(root->_left);
        printf("%c ", root->_data);
        Inorder(root->_right);
    }
}
BTNode* CreatBTree(char* str, int* pi)
{
    if(str[*pi]!= '#')
    {
        //当前节点非空，则创建当前节点
        BTNode*root=(BTNode*)malloc(sizeof(BTNode));
        root->_data = str[*pi];
        //字符位置向后移动一个位置
        ++(*pi);
        //创建左子树
        root->_left=CreatBTree(str,pi);
        //字符位置向后移动一个位置
        ++(*pi);
        //创建右子树
        root->_right=CreatBTree(str,pi);
        return root;
    }
    else
        return NULL;  //如果是空节点，则返回NULL
}
int main()
{
    char str[101];
    int i = 0;
    //读入字符串
    scanf("%s", str);
    //创建二叉树
    BTNode* root = CreatBTree(str, &i);
    //中序打印二叉树
    Inorder(root);
    printf("\n");
    return 0;
}

🍔二叉树销毁

😍代码：

// 二叉树销毁—递归实现
void BinaryTreeDestory(BTNode* root)
{
  if (root == NULL)  
  {
  return;
  }
  BinaryTreeDestory(root->right);  
  BinaryTreeDestory(root->left);
  free(root);
}

✅运用后序遍历（因为如果先释放根节点的话就不能直接找到左右子树了）来实现递归二叉树销毁，结束标志是遇见空节点返回上一级。

🍔二叉树节点个数

😍代码：

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

✅运用递归（前序）简化了问题，即：二叉树节点个数 = 左子树节点数 + 右子树节点数 + 1

✅递归结束条件是遇到空节点返回 0。

🍔二叉树叶子节点个数

😍代码：

// 二叉树叶子节点个数
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);
}

🍎叶子节点的概念：度为0的节点称为叶节点

🍟运用递归（前序）简化了问题，即：二叉树叶子节点个数 = 左子树叶子节点个数 + 右子树叶子节点个数

🍟递归结束条件是遇到空节点返回 0，该节点的左子树节点为空并且右子树节点为空，则该节点为叶子节点，返回1。

🍔二叉树第k层节点个数

😍代码：

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
  assert(k > 0); //k的值不能为负数
  if (k == 1 && root)  //第k层的判断条件
  {
  return 1;
  }
  return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

🍎层的概念：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

🍟不满足第k层的判断条件的不计数,（继续递归下去），当满足第K层的条件的就返回1（返回上一级的函数中）

🍔二叉树查找值为x的节点

😍代码：

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
  {
  return NULL;
  }
  if (root->data == x)
  {
  return root;
  }
  BTNode* ret1 = BinaryTreeFind(root->left, x);
  BTNode* ret2 = BinaryTreeFind(root->right, x);
  if (ret1)
  return ret1;
  if (ret2)
  return ret2;
  return NULL;
}

✅运用递归（前序）简化了问题，即：二叉树中等于X的节点个数 = 左子树等于X的节点个数 + 右子树等于X的节点个数

✅等于空，或者等于这个要找的值为这里的结束条件，返回的是值等于X的节点指针。这里用了两个临时变量来储存左右两边的个数，这样做可以在返回的时候直接返回，不用再一次的计算。🥰

🍔判断二叉树是否是完全二叉树

69234c5c71fe51659f21dcdc41ceb29d_48985be1b37c44a88cdddae860d42d3c.png

🍁完全二叉树的概念：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

✅运用前面层序遍历的思想用队列进行层序遍历，与它不一样的地方在于这次空值也要入队列，只要队列的队头为空指针就停止操作，看后面是否都为空，由于完全二叉树的自身特性决定了它的后面如果都为空则是完全二叉树，否则不是。

😍代码：

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
  {
  QueuePush(&q, root);
  }
  while (!QueueEmpty(&q))
  {
  BTNode* front = QueueFront(&q);
  QueuePop(&q);
  if (front == NULL)   // 遇到空就跳出
    break;
  QueuePush(&q, front->left);
  QueuePush(&q, front->right);
  }
  // 检查后面的节点有没有非空
  // 有非空，不是完全二叉树
  while (!QueueEmpty(&q))
  {
  BTNode* front = QueueFront(&q);
  QueuePop(&q);
  if (front)
  {
    QueueDestroy(&q);
    return false;
  }
  }
  QueueDestroy(&q);
  return true;
}

😍二叉树的链式结构所有代码汇总😍

✅BinaryTree.c

typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
  BTNode* node = (BTNode*)malloc(sizeof(BTNode));
  if (node == NULL)
  {
  perror("malloc fail");
  return NULL;
  }
  node->data = x;
  node->left = NULL;
  node->right = NULL;
  return node;
}
//二叉树创建
BTNode* CreatBTree(char* str, int* pi)
{
    if(str[*pi]!= '#')
    {
        //当前节点非空，则创建当前节点
        BTNode*root=(BTNode*)malloc(sizeof(BTNode));
        root->_data = str[*pi];
        //字符位置向后移动一个位置
        ++(*pi);
        //创建左子树
        root->_left=CreatBTree(str,pi);
        //字符位置向后移动一个位置
        ++(*pi);
        //创建右子树
        root->_right=CreatBTree(str,pi);
        return root;
    }
    else
        return NULL;  //如果是空节点，则返回NULL
}
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
  if (root == NULL)
  {
  return;
  }
  BinaryTreeDestory(root->right);
  BinaryTreeDestory(root->left);
  free(root);
}
// 二叉树节点个数
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 == NULL && root->right == NULL)
  {
  return 1;
  }
  return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
  assert(k > 0);
  if (k == 1 && root)
  {
  return 1;
  }
  return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
  {
  return NULL;
  }
  if (root->data == x)
  {
  return root;
  }
  BTNode* ret1 = BinaryTreeFind(root->left, x);
  BTNode* ret2 = BinaryTreeFind(root->right, x);
  if (ret1)
  return ret1;
  if (ret2)
  return ret2;
  return NULL;
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
  if (root == NULL)
  {
  printf("N ");
  return;
  }
  printf("%d ", root->data);
  BinaryTreePrevOrder(root->left);
  BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root) 
{
  if (root == NULL)
  {
  printf("N ");
  return;
  }
  BinaryTreeInOrder(root->left);
  printf("%d ", root->data);
  BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
  if (root == NULL)
  {
  printf("N ");
  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))
  {
  BTNode* front = QueueFront(&q);
  QueuePop(&q);
  printf("%d ", front->data);
  if (front->left)
    QueuePush(&q, front->left);
  if (front->right)
    QueuePush(&q, front->right);
  }
  printf("\n");
  QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
  {
  QueuePush(&q, root);
  }
  while (!QueueEmpty(&q))
  {
  BTNode* front = QueueFront(&q);
  QueuePop(&q);
  if (front == NULL)   // 遇到空就跳出
    break;
  QueuePush(&q, front->left);
  QueuePush(&q, front->right);
  }
  // 检查后面的节点有没有非空
  // 有非空，不是完全二叉树
  while (!QueueEmpty(&q))
  {
  BTNode* front = QueueFront(&q);
  QueuePop(&q);
  if (front)
  {
    QueueDestroy(&q);
    return false;
  }
  }
  QueueDestroy(&q);
  return true;
}

✅Queue.c

void QueueInit(Queue* pq)
{
  assert(pq);
  pq->phead = NULL;
  pq->ptail = NULL;
  pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->phead;
  while (cur)
  {
  QNode* next = cur->next;
  free(cur);
  cur = next;
  }
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
  perror("malloc fail\n");
  return;
  }
  newnode->data = x;
  newnode->next = NULL;
  if (pq->ptail == NULL)
  {
  assert(pq->phead == NULL);
  pq->phead = pq->ptail = newnode;
  }
  else
  {
  pq->ptail->next = newnode;
  pq->ptail = newnode;
  }
  pq->size++;
}
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  if (pq->phead->next == NULL)
  {
  QNode* head = pq->phead;
  free(head);
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
  }
  else
  {
  QNode* head = pq->phead;
  pq->phead = pq->phead->next;
  free(head);
  pq->size--;
  }
}
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return(pq->phead->data);
}
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->ptail->data;
}
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->size == 0;
}

二叉树的链式结构 - C语言（含有大量递归）下

🍔 构建二叉树

😍代码：

🍔二叉树销毁

😍代码：

🍔二叉树节点个数

😍代码：

🍔二叉树叶子节点个数

😍代码：

🍔二叉树第k层节点个数

😍代码：

🍔二叉树查找值为x的节点

😍代码：

🍔判断二叉树是否是完全二叉树

😍代码：

😍二叉树的链式结构所有代码汇总😍

✅BinaryTree.c

✅Queue.c

热门文章

最新文章

相关课程

相关电子书