深圳幻海软件技术有限公司 欢迎您！
更多

【数据结构】二叉树（二）

2023-06-25

amp 节点 root
目录一、二叉树链式结构及实现 1、二叉树的结构 2、二叉树的遍历  2.1前序遍历  2.2中序遍历  2.3后序遍历  2.4层序遍历 3、二叉树链式结构的实现  3.

目录

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

 1、二叉树的结构

 2、二叉树的遍历

   2.1 前序遍历

   2.2 中序遍历

   2.3 后序遍历

   2.4 层序遍历

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

   3.1 创建一个节点

   3.2 二叉树节点个数 

   3.3 二叉树叶子节点个数

   3.4 二叉树的高度

   3.5 二叉树第k层节点个数

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

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

二、二叉树基础oj练习题

 1、单值二叉树

   1.1 题目说明 

   1.2 题目解析

 2、检查两棵树是否相同

   2.1 题目说明

   2.2 题目解析

 3、对称二叉树

   3.1 题目说明

   3.2 题目解析

 4、二叉树的前序遍历

   4.1 题目说明

   4.2 题目解析

 5、二叉树的中序遍历

   5.1 题目说明

   5.2 题目解析

 6、二叉树的后序遍历

   6.1 题目说明

   6.2 题目解析

 7、另一颗树的子树

   7.1 题目说明

   7.2 题目解析

 

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

 1、二叉树的结构

  1. typedef int BTDataType;
  2. typedef struct BinaryTreeNode
  3. {
  4. BTDataType data;
  5. struct BinaryTreeNode* left;
  6. struct BinaryTreeNode* right;
  7. }BTNode;

二叉树链式结构类型，这种是节点类型，包括了左右孩子节点，和该节点的数据值。

 2、二叉树的遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉 树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。下面给出了4中遍历方法。

   2.1 前序遍历

先是访问根节点，然后访问左子树，最后访问右子树。

  1. //二叉树前序遍历
  2. void PrevOrder(BTNode* root)
  3. {
  4. if (root == NULL)
  5. {
  6. return;
  7. }
  8. printf("%d ", root->data);
  9. PrevOrder(root->left);
  10. PrevOrder(root->right);
  11. }

   2.2 中序遍历

先是访问左子树，然后访问根节点，最后访问右子树。

  1. //二叉树中序遍历
  2. void InOrder(BTNode* root)
  3. {
  4. if (root == NULL)
  5. {
  6. return;
  7. }
  8. InOrder(root->left);
  9. printf("%d ", root->data);
  10. InOrder(root->right);
  11. }

   2.3 后序遍历

先是访问左子树，然后访问右子树，最后访问根节点。

  1. //二叉树后序遍历
  2. void PostOrder(BTNode* root)
  3. {
  4. if (root == NULL)
  5. {
  6. return;
  7. }
  8. PostOrder(root->left);
  9. PostOrder(root->right);
  10. printf("%d ", root->data);
  11. }

   2.4 层序遍历

层序遍历，就是按照二叉树每一层的节点进行访问。

思路：需要创建一个队列，首先将根节点放入队列，然后当队列不为空时，就出队头节点，如果队头节点的左子树不为空，它的左子树节点就入队列，如果队头节点的右子树不为空，它的右子树节点就入队列，依次循环，直到队列里面没有节点，此时，层序遍历结束。

  1. //二叉树层序遍历
  2. void LevelOrder(BTNode* root)
  3. {
  4. Queue q;
  5. QueueInit(&q);
  6. if (root)
  7. QueuePush(&q, root);
  8. while (!QueueEmpty(&q))
  9. {
  10. BTNode* front = QueueFront(&q);
  11. printf("%d ", front->data);
  12. QueuePop(&q);
  13. if (front->left)
  14. {
  15. QueuePush(&q, front->left);
  16. }
  17. if (front->right)
  18. {
  19. QueuePush(&q, front->right);
  20. }
  21. }
  22. printf("\n");
  23. QueueDestroy(&q);
  24. }

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

   3.1 创建一个节点

要想实现二叉树链式结构，首先要创建节点，创建完节点将其初始化。

  1. //创建一个节点
  2. BTNode* BuyBTNode(BTDataType x)
  3. {
  4. BTNode* node = (BTNode*)malloc(sizeof(BTNode));
  5. if (node == NULL)
  6. {
  7. perror("malloc fail");
  8. exit(-1);
  9. }
  10. node->data = x;
  11. node->left = node->right = NULL;
  12. return node;
  13. }

   3.2 二叉树节点个数 

此处给了两种方法，第一种就是通过全局变量，每到一个结点总数就++。第二种方法就是简化了一下，左子树节点个数+右子树节点个数+根节点。

  1. //二叉树节点个数
  2. int size = 0;
  3. int TreeSize1(BTNode* root)
  4. {
  5. if (root == NULL)
  6. return 0;
  8. //前序遍历
  9. size++;
  10. TreeSize1(root->left);
  11. TreeSize1(root->right);
  12.     return size;
  13. }
  14.  
  15. //二叉树节点个数
  16. int TreeSize2(BTNode* root)
  17. {
  18. return root == NULL ? 0 : TreeSize2(root->left) + TreeSize2(root->right) + 1;
  19. }

   3.3 二叉树叶子节点个数

计算叶子节点个数，需要分情况讨论，如果根节点为空时，就等于0，如果根节点的左右子树都为空时，叶子节点个数就为1，剩下就是根节点的左右子树都不为空的情况了，此时遍历左子树和右子树计算叶子节点个数。

  1. //二叉树叶子节点个数
  2. int TreeLeafSize(BTNode* root)
  3. {
  4. if (root == NULL)
  5. return 0;
  6.  
  7. if (root->left == NULL && root->right == NULL)
  8. return 1;
  10. return TreeLeafSize(root->left) + TreeLeafSize(root->right);
  11. }

   3.4 二叉树的高度

二叉树的高度就是算左右两边子树的最大高度。需要递归到最后一层，然后再+当前节点高度。

  1. //二叉树的高度或深度(后序遍历)
  2. int TreeHeight(BTNode* root)
  3. {
  4. if (root == NULL)
  5. return 0;
  6.  
  7. int leftHeight = TreeHeight(root->left);
  8. int rightHeight = TreeHeight(root->right);
  9. return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
  10. }

   3.5 二叉树第k层节点个数

同样需要递归根节点的左右子树，看看每一层左右子树有多少个节点，然后相加即可。

  1. //二叉树第k层的节点个数 k >= 1
  2. int TreeKLevelSize(BTNode* root, int k)
  3. {
  4. if (root == NULL)
  5. return 0;
  6. if (k == 1)
  7. return 1;
  8. //k > 1 子树的k-1
  9. return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1);
  10. }

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

二叉树查找节点的方法也是用的递归，首先先判断这颗二叉树是否为空，如果为空，就不存在x，如果根节点处的值等于x，就找到了，如果没有，就向下进行，先遍历左子树，再遍历右子树，直到找到x。

  1. //二叉树查找值为x的节点
  2. BTNode* TreeFind(BTNode* root, BTDataType x)
  3. {
  4. if (root == NULL)
  5. return NULL;
  6. if (root->data == x)
  7. return root;
  8. BTNode* ret1 = TreeFind(root->left, x);
  9. if (ret1)
  10. return ret1;
  11.  
  12. BTNode* ret2 = TreeFind(root->right, x);
  13. if (ret2)
  14. return ret2;
  15. return NULL;
  16. }

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

思路：和上面层序遍历一致，同样要是用队列，还是一层一层的将节点入队列，出队列，当出队列遇到空节点时，停止入队列。然后判断队列中是否都是空节点，若都是空节点，则为完全二叉树，否则不为完全二叉树。

  1. //判断二叉树是否是完全二叉树
  2. bool BinaryTreeComplete(BTNode* root)
  3. {
  4. Queue q;
  5. QueueInit(&q);
  6. if (root)
  7. QueuePush(&q, root);
  8. while (!QueueEmpty(&q))
  9. {
  10. BTNode* front = QueueFront(&q);
  11. QueuePop(&q);
  12.  
  13. if (front == NULL)
  14. {
  15. break;
  16. }
  17. else
  18. {
  19. QueuePush(&q, front->left);
  20. QueuePush(&q, front->right);
  21. }
  22. }
  23. //出到空以后，如果后面全是空，则是完全二叉树
  24. while (!QueueEmpty(&q))
  25. {
  26. BTNode* front = QueueFront(&q);
  27. QueuePop(&q);
  28. if (front != NULL)
  29. {
  30. QueueDestroy(&q);
  31. return false;
  32. }
  33. }
  34. QueueDestroy(&q);
  35. return true;
  36. }

二、二叉树基础oj练习题

 1、单值二叉树

   1.1 题目说明 

    题目链接：单值二叉树

    如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。

 

   1.2 题目解析

    思路：如果树为空，则说明是单值二叉树，如果它的左子树不为空且左子树的节点值和根节点值不相等，则返回false，如果它的右子树不为空且右子树的节点值和根节点值不相等，则返回false。

  1. bool isUnivalTree(struct TreeNode* root){
  2.     if(root == NULL)
  3.     return true;
  4.  
  5.     if(root->left && root->left->val != root->val)
  6.         return false;
  7.     
  8.     if(root->right && root->right->val != root->val)
  9.         return false;
  10.  
  11.     return isUnivalTree(root->left) && isUnivalTree(root->right);
  12. }

 2、检查两棵树是否相同

   2.1 题目说明

   题目链接：相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

 

 

   2.2 题目解析

   思路：判断根，左子树、右子树是否相同——1.判断结构是否相同     2.判断val是否相同。

首先有两种特殊情况，就是如果根节点 p 和 根节点 q 都为空，说明这两棵树为相同的树，如果根节点 p 和 根节点 q ，有一个为空，说明这两棵树不相同。

如果 节点 p 的值不等于节点 q 的值，很明显这两棵树不相同，最后遍历 p 和 q 的左右子树。 

  1. bool isSameTree(struct TreeNode* p, struct TreeNode* q){
  2.     if(p == NULL && q == NULL)
  3.         return true;
  4.     if(p == NULL || q == NULL)
  5.         return false;
  6.     if(p->val != q->val)
  7.         return false;
  8.     return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
  9. }

 3、对称二叉树

   3.1 题目说明

   题目链接：对称二叉树

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

 

   3.2 题目解析

   思路：为了方便判断这棵树是否是轴对称，我们先写一个函数，判断其轴对称。

轴对称函数其实和上面判断两棵树是否相同一样，就是在最后递归的时候，需要 root1 的左子树和root2 的右子树进行判断是否是相同的，或者是 root1 的右子树和 root2 的左子树进行判断是否是相同的，如果相同，则说明是对称二叉树。

  1. bool _isSymmetric(struct TreeNode* root1,struct TreeNode* root2)
  2. {
  3.     if(root1 == NULL && root2 == NULL)
  4.         return true;
  5.     
  6.     if(root1 == NULL || root2 == NULL)
  7.         return false;
  8.  
  9.     if(root1->val != root2->val)
  10.         return false;
  11.  
  12.     return _isSymmetric(root1->left,root2->right) && _isSymmetric(root1->right,root2->left);
  13. }
  14.  
  15. bool isSymmetric(struct TreeNode* root){
  16.     return !root || _isSymmetric(root->left,root->right);
  17. }

 4、二叉树的前序遍历

   4.1 题目说明

   题目链接：二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

   4.2 题目解析

   思路1：这种方法是递归形式，先是编写一个前序遍历的算法，前序遍历的访问顺序是根节点，然后是左子树，最后是右子树。

  1. class Solution {
  2. public:
  3.     void preorde(TreeNode* root,vector<int>& ret)
  4.     {
  5.         if(root == nullptr)
  6.             return;
  7.         ret.push_back(root->val);
  8.         preorde(root->left,ret);
  9.         preorde(root->right,ret);
  10.         
  11.     }
  12.     vector<int> preorderTraversal(TreeNode* root) {
  13.         vector<int> ret;
  14.         preorde(root,ret);
  15.         return ret;
  16.     }
  17. };

   思路2：这种方法是非递归形式，这种思路是将一棵树分为了两部分：(1)左路节点；(2)左路节点的右子树。这里面用到的栈，它的作用就是为了访问左路节点的右子树。

 

  1. class Solution {
  2. public:
  3.     vector<int> preorderTraversal(TreeNode* root) {
  4.         stack<TreeNode*> s;
  5.         vector<int> v;
  6.         TreeNode* cur = root;
  7.         while(cur || !s.empty())
  8.         {
  9.             while(cur)
  10.             {
  11.                 v.push_back(cur->val);
  12.                 s.push(cur);
  13.                 cur = cur->left;
  14.             }
  15.             TreeNode* top = s.top();
  16.             s.pop();
  17.             cur = top->right;
  18.         }
  19.         return v;
  20.     }
  21. };

 5、二叉树的中序遍历

   5.1 题目说明

   题目链接：二叉树的中序遍历

   给你二叉树的根节点 root ，返回它节点值的 中序 遍历。

   5.2 题目解析

   思路1：用递归方式，先是编写一个中序遍历的算法，中序遍历的访问顺序是左子树，然后是根节点，最后是右子树。

  1. class Solution {
  2. public:
  3.     void inorder(TreeNode* root, vector<int>& ret) {
  4.         if (root == NULL) 
  5.             return;
  6.         inorder(root->left, ret);
  7.         ret.push_back(root->val);
  8.         inorder(root->right, ret);
  9.     }
  10.     vector<int> inorderTraversal(TreeNode* root) {
  11.         vector<int> ret;
  12.         inorder(root, ret);
  13.         return ret;
  14.     }
  15. };

    思路2： 用的是非递归方式，将一颗二叉树分为两个部分：(1)左路节点；(2)左路节点的右子树。和上面前序遍历的非递归方式一样，不同的是进入 v 的顺序不同。

  1. class Solution {
  2. public:
  3.     vector<int> inorderTraversal(TreeNode* root) {
  4.         stack<TreeNode*> s;
  5.         vector<int> v;
  6.         TreeNode* cur = root;
  7.         while(cur || !s.empty())
  8.         {
  9.             while(cur)
  10.             {
  11.                 s.push(cur);
  12.                 cur=cur->left;
  13.             }
  14.             TreeNode* top = s.top();
  15.             s.pop();
  16.             v.push_back(top->val);
  17.  
  18.             cur = top->right;
  19.         }
  20.         return v;
  21.     }
  22. };

 6、二叉树的后序遍历

   6.1 题目说明

   题目链接：二叉树的后序遍历

   给你二叉树的根节点 root ，返回它节点值的 后序 遍历。

   6.2 题目解析

    思路1：用递归方式，先是编写一个后序遍历的算法，后序遍历的访问顺序是左子树，然后是右子树，最后是根节点。

  1. class Solution {
  2. public:
  3.     void postorder(TreeNode *root, vector<int> &ret) 
  4.     {
  5.         if (root == nullptr) 
  6.         {
  7.             return;
  8.         }
  9.         postorder(root->left, ret);
  10.         postorder(root->right, ret);
  11.         ret.push_back(root->val);
  12.     }
  13.     vector<int> postorderTraversal(TreeNode *root) {
  14.         vector<int> ret;
  15.         postorder(root, ret);
  16.         return ret;
  17.     }
  18. };

   思路2：用非递归方式，将一颗二叉树分为两个部分：(1)左路节点；(2)左路节点的右子树。注意：假设第一次取到6时，上一个访问的节点是左子树的根4，第二次取到6时，上一个访问的节点是右子树的根7。所以有了另一个限制条件 top->right == prev 。

  1. class Solution {
  2. public:
  3.     vector<int> postorderTraversal(TreeNode* root) {
  4.         stack<TreeNode*> s;
  5.         vector<int> v;
  6.         TreeNode* cur = root;
  7.         TreeNode* prev = nullptr;
  8.         while(cur || !s.empty())
  9.         {
  10.             while(cur)
  11.             {
  12.                 s.push(cur);
  13.                 cur = cur->left;
  14.             }
  15.             TreeNode* top = s.top();
  16.             //1.右为空 或者 右子树已经访问过了(上一个访问的节点是右子树的根)，可以访问根节点
  17.             if(top->right == nullptr || top->right == prev)
  18.             {
  19.                 v.push_back(top->val);  
  20.                 s.pop(); 
  21.                 prev = top;
  22.             }
  23.             else
  24.             {
  25.                 //访问左路节点右子树  ---- 子问题
  26.                 cur = top->right;
  27.             }
  28.         }
  29.         return v;
  30.     }
  31. };

 7、另一颗树的子树

   7.1 题目说明

   题目链接：另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

   7.2 题目解析

   思路：三步走：1.判断它们是不是相同的树    2.判断subRoot是不是root的左子树  3.判断subRoot是不是root的右子树。

  1. bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
  2.     if (p == NULL && q == NULL)
  3.         return true;
  4.      //其中一个为空
  5.     if (p == NULL || q == NULL)
  6.         return false;
  7.     if (p->val != q->val)
  8.         return false;
  9.     return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
  10. }
  11.  
  12. bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
  13.     if(root == NULL)
  14.         return false;
  15.     if(isSameTree(root,subRoot))
  16.         return true;
  17.     return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
  18. }

   

   

本文要是有不足的地方，欢迎大家在下面评论，我会在第一时间更正。 

老铁们，记着点赞加关注!!!  

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览48400 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪