【二叉树】

简介: 【二叉树】

一、二叉树的链式结构实现

二叉树链式结构的简单实现: 此处为了快速创建一棵二叉树,只是简单创建每一个节点然后把它们连接起来;

示例代码:

typedef int BTDataType;
    //节点的结构体
    typedef struct BinaryTreeNode
    {
      struct BinaryTreeNode* left;
      struct BinaryTreeNode* right;
      BTDataType data;
    }BTNode;
    //创建新的节点
    BTNode* BuyNode(BTDataType x)
    {
      BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
      assert(newnode);
      newnode->data = x;
      newnode->left = NULL;
      newnode->right = NULL;
      return newnode;
    }
    //创建二叉树
    BTNode* CreatBinaryTree()
    {
      BTNode* node1 = BuyNode(1);
      BTNode* node2 = BuyNode(2);
      BTNode* node3 = BuyNode(4);
      BTNode* node4 = BuyNode(3);
      BTNode* node5 = BuyNode(5);
      BTNode* node6 = BuyNode(6);
      node1->left = node2;
      node1->right = node3;
      node2->left = node4;
      node3->left = node5;
      node3->right = node6;
      return node1;
    }

以上代码创建的二叉树如图:

二、二叉树的遍历

所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的节点进行相应的操作,并且每个节点只操作一次。

1. 二叉树的前序遍历

二叉树的前序遍历是先访问根节点,再访问左子树,最后访问右子树,即按照根 - 左子树 - 右子树的顺序遍历;示例代码:

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

代码通过子问题,先打印根的数据,再将当前根的左子树进行递归,最后对右子树递归,结束条件为空,即完成了 根 - 左子树 - 右子树 的顺序访问,若以上面我们创建的二叉树为例,如图为运行结果,假设 N 为空:

遍历的过程我们可以分解为如下,假设 N 为空;

以下是以 1 为根的分解,左子树和右子树如下,

再往下分解如下:

所以遍历的顺序图如下,蓝色数字为访问节点的顺序:

先访问 1 的根节点,然后访问左子树,递归图解:

最后访问右子树,递归图解:

2. 二叉树的中序遍历

二叉树的中序遍历,与前序的区别是,中序遍历先访问左子树,再访问根,最后访问右子树,即按照左子树 - 根 - 右子树的顺序遍历;示例代码:

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

若以上面我们创建的二叉树为例,以下就是中序遍历的结果:

3. 二叉树的后序遍历

二叉树的后序遍历,与前序和中序相似,后序是先访问左子树,再访问右子树,最后访问根;按照左子树 - 右子树 - 根的顺序遍历;示例代码:

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

若以上面我们创建的二叉树为例,以下就是后序遍历的结果:

4. 二叉树的层序遍历

层序遍历:除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

按如图顺序遍历为层序遍历:

层序遍历的思路是用队列实现,每打印出一个根的数据,就将这个根的左节点和右节点入队,如下图,使用上面我们创建的二叉树,再创建一个队列 q ,队列中存的是每个树的节点:

如果队列为空,根就进队列:

然后出队列,出队列后,根2和根4入队:

2出队,3和NULL入队:

最后层序遍历的结果如下:

代码示例:

我们使用以前实现的队列,将队列中每个节点的指针类型改为 BTNode* :

typedef struct BinaryTreeNode* QDataType;
    //每个节点的结构体
    typedef struct QueueNode
    {
      struct QueueNode* next;
      QDataType data;
    }QNode;
    //队列的结构体
    typedef struct Queue
    {
      QNode* phead;
      QNode* ptail;
      int size;
    }Queue;

层序遍历的示例代码:

//层序遍历
    void LevelOrder(BTNode* root)
    {
      //用队列实现层序遍历
      Queue q;
      QueueInit(&q);
      //节点不为空,就入队
      if(root)
        QueuePush(&q, root);
      //每次出队之前,将队头的数据记录下来,然后出队,打印队头的值,再将出队的根的左右子树入队
      while (!QIsEmpty(&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);
    }

假设不打印空,运行的结果如下:

三、求二叉树的常见问题

1. 求二叉树节点个数

求二叉树节点个数化成子问题,左子树的节点个数加上右子树的节点个数加上自身节点;结束条件为空:

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

若以上面创建的树为例子,树的节点个数以及运行结果如下:

2. 求二叉树叶子节点个数

求二叉树叶子节点个数化成子问题,将根的左子树的叶子数加上右子树的叶子数,结束条件为空或者根的左子树和右子树都为空,就是叶子,返回1;

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

运行结果如下:

3. 求二叉树的高度

求二叉树的高度化成子问题,取根的左子树和右子树中高度较高的那个,返回的是较高的那个再加一;结束条件为空;注意这里需要记录左子树和右子树的高度,不记录数据的话每次递归完会丢失数据,还要重新找数据,时间复杂度会翻呈指数形式的倍率;

int BTreeHeight(BTNode* root)
    {
      if (root == NULL)
        return 0;
      int leftHeight = BTreeHeight(root->left);
      int rightHeight = BTreeHeight(root->right);
      return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

运行结果如下:

4. 求二叉树第k层结点个数

求二叉树第k层结点个数化成子问题,求当前根的左子树的 k - 1 层加上右子树的 k - 1 层的节点个数;结束条件有两个,如果为空,返回0;如果 k == 1,表示就是第 k 层,返回1;

int BTreeLevelKSize(BTNode* root, int k)
    {
      assert(k > 0);
      if (root == NULL)
        return 0;
      if (k == 1)
        return 1;
      return BTreeLevelKSize(root->left, k - 1) + BTreeLevelKSize(root->right, k - 1);
    }

假设求第一层的节点,运行结果如下:

5. 二叉树查找值为x的节点

二叉树查找值为x的节点化成子问题,先判断当前的根是否是值为 x 的节点,若不是,就找在左子树中去找,在左子树中找不到,再去右子树找;结束条件为空或者找到值为x的节点;

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

假设查找值为 6 的节点,运行结果如下:

6. 判断二叉树是否是完全二叉树

判断二叉树是否是完全二叉树,思路是用层序遍历的思维,完全二叉树是层序遍历连续的结果,如果遇到空后,队列中的数据还有有效的数据,说明不是完全二叉树;如果是完全二叉树,队列中应该全部是空;

//判断二叉树是否是完全二叉树
    bool BTreeComplete(BTNode* root)
    {
      Queue q;
      QueueInit(&q);
      if (root)
        QueuePush(&q, root);
      //出数据,遇到空就停止出
      while (!QIsEmpty(&q))
      {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front == NULL)
          break;
        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
      }
      //判断队列里面是否还有数据,如果还有数据说明不是完全二叉树
      //完全二叉树是层序遍历连续的结果
      while (!QIsEmpty(&q))
      {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if (front)
        {
          QueueDestroy(&q);
          return false;
        }
      }
      QueueDestroy(&q);
      return true;
    }

假设false为0,true为1,运行结果为:

7. 给定前序遍历创建一颗二叉树

给定前序遍历创建一颗二叉树(假设0为空),思路是用前序遍历的思路,先创建根,再创建左子树,最后创建右子树;假设遍历的前序中 0 为空,参考代码如下:

//给定前序遍历,创建一棵树
    BTNode* CreatTree(BTDataType* a, int* pi)
    {
      if (a[*pi] == 0)
      {
        (*pi)++;
        return NULL;
      }
      BTNode* root = BuyNode(a[(*pi)++]);
      root->left = CreatTree(a, pi);
      root->right = CreatTree(a, pi);
      //返回根
      return root;
    }
    int main()
    {
      int arr[] = { 1,2,3,0,0,0,4,5,0,0,6,0,0 };
      int i = 0;
      BTNode* root = CreatTree(arr, &i);
      PrevOrder(root);
    }

8. 二叉树销毁

二叉树销毁是按照后序的顺序,先销毁左子树,再销毁右子树,最后销毁根;

// 二叉树销毁
    void BTreeDestory(BTNode* root)
    {
      if (root == NULL)
        return;
      BTreeDestory(root->left);
      BTreeDestory(root->right);
      free(root);
    }
目录
相关文章
|
C语言
【二叉树】的实现
【二叉树】的实现
35 0
|
5月前
|
Java
二叉树
二叉树
22 0
|
6月前
|
存储 C++
二叉树
二叉树“【5月更文挑战第22天】”
32 3
二叉树的讲解
1.若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1) 个结点. 2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是 2^h-1. 3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为02 ,则有n0 =n2 +1 4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h= . (ps: 是log以2为底,n+1为对数) 5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:
二叉树的讲解
|
6月前
|
算法 网络协议 NoSQL
认识二叉树(详细介绍)
认识二叉树(详细介绍)
|
6月前
|
存储
二叉树的实现(下)
二叉树的实现(下)
59 0
【二叉树】(二)
【二叉树】(二)
41 0
|
存储 机器学习/深度学习 算法
二叉树(详解)中
二叉树(详解)
78 0