您的位置：首页 > 文旅 > 旅游 > 二叉树详解（2）

二叉树详解（2）

2024/12/21 22:16:38 来源：https://blog.csdn.net/weixin_73077334/article/details/141269028  浏览:  次  关键词：二叉树详解（2）

文章目录

    • 4. 二叉树链式结构的实现
    • 5. 二叉树基础oj练习

4. 二叉树链式结构的实现

首先，我们先要了解一下二叉树的遍历顺序有哪些：
二叉树的遍历顺序

通过了解二叉树的遍历顺序，我们不难看出要实现二叉树的遍历需要用到递归，而使用递归我们就要思考以下两点：

  1. 子问题
  2. 结束条件（最小子问题）

在这里，空树就是不可再分割的子问题。

我们先手搓一棵树，方便我们一会进行验证：

#include <stdio.h>
#include <stdlib.h>typedef struct BinTreeNode
{struct BinTreeNode* left;struct BinTreeNode* right;int val;
}BTNode;BTNode* BuyBTNode(int val)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (NULL == newnode){perror("malloc fail");return NULL;}newnode->val = val;newnode->left = NULL;newnode->right = NULL;return newnode;
}//手搓一棵树
BTNode* CreateTree()
{BTNode* n1 = BuyBTNode(1);BTNode* n2 = BuyBTNode(2);BTNode* n3 = BuyBTNode(3);BTNode* n4 = BuyBTNode(4);BTNode* n5 = BuyBTNode(5);BTNode* n6 = BuyBTNode(6);n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;return n1;
}int main()
{BTNode* root = CreateTree();return 0;
}
  1. 前序
void PreOrder(BTNode* root)
{if (NULL == root){printf("N ");return;}printf("%d ", root->val);PreOrder(root->left);PreOrder(root->right);
}

前序的递归展开图

  1. 中序
void InOrder(BTNode* root)
{if (NULL == root){printf("N ");return;}InOrder(root->left);printf("%d ", root->val);InOrder(root->right);
}
  1. 后序
void PostOrder(BTNode* root)
{if (NULL == root){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->val);
}
  1. 节点个数
    最容易想到的就是用计数的方法来实现：
int TreeSize(BTNode* root)
{static int size = 0;if (NULL == root){return 0;}else{++size;}TreeSize(root->left);TreeSize(root->right);return size;
}

但是这样写会出现问题：

int main()
{BTNode* root = CreateTree();printf("%d\n", TreeSize(root));printf("%d\n", TreeSize(root));printf("%d\n", TreeSize(root));return 0;
}

多次调用时它的个数就会出错，这是因为第一次调用完之后第二次再调用时size的值并不为0，但是size又是在函数里面的，在函数外又不能把它变为0，所以我们可以这样修改：

//static int size = 0;
int size = 0;int TreeSize(BTNode* root)
{if (NULL == root){return 0;}else{++size;}TreeSize(root->left);TreeSize(root->right);return size;
}int main()
{BTNode* root = CreateTree();printf("%d\n", TreeSize(root));size = 0;printf("%d\n", TreeSize(root));size = 0;printf("%d\n", TreeSize(root));return 0;
}

但是因为创建的是全局变量，这样写会有线程安全的风险，比如说这个函数给多个线程用，它们之间互相会影响（这里先了解一下，之后学了多线程就可以理解了）

如果一定要用计数的方式来实现，可以这样写：

void TreeSize(BTNode* root, int* psize)
{if (NULL == root){return;}else{++(*psize);}TreeSize(root->left, psize);TreeSize(root->right, psize);
}

那么还有没有其他更好的方法呢？

还是递归，递归本质上就是分而治之。

我们举一个形象的例子：
二叉树节点个数的举例

int TreeSize(BTNode* root)
{return NULL == root ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}int main()
{BTNode* root = CreateTree();printf("%d\n", TreeSize(root));printf("%d\n", TreeSize(root));printf("%d\n", TreeSize(root));return 0;
}

这种写法可以看作是后序，因为先算出左子树的节点个数，再算出右子树的节点个数，最后加上根就可以算出根所在的这棵树的节点个数。（代码中的 + 1 不管放在最前面，还是中间还是最后面都不会影响它是后序，因为我们必须要先算出左右子树的个数才能算出总的节点个数；如果把 + 1 放在中间就认为是中序，那么就变成了只要算出左子树的节点个数，再加上根就可以算出总的节点个数了，这显然是不对的；所以判断前中后序不能简单的看代码，而是要了解它的核心逻辑，它是如何达到这个结果的）

  1. 树的高度
int TreeHeight(BTNode* root)
{if (NULL == root){return 0;}int leftHeight = TreeHeight(root->left);int rightHeight = TreeHeight(root->right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

如果我们不记录左右子树的高度，而是直接把递归写到return里，也是对的，但是它的时间复杂度会变得很大：
求树的高度的时间复杂度

  1. 第k层的节点个数
    第k层的节点个数
int TreeKLevel(BTNode* root, int k)
{assert(k > 0);if (NULL == root){return 0;}if (1 == k){return 1;}//不等于空，且k > 1说明第k层的节点在子树里面，转换成子问题求解return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}
  1. 查找x所在的节点
    查找x所在的节点

用递归写很容易会写出这样错误的代码：

BTNode* TreeFind(BTNode* root, int x)
{if (NULL == root){return NULL;}if (root->val == x){return root;}TreeFind(root->left, x);TreeFind(root->right, x);
}

通过画递归展开图我们就可以很容易发现问题：有一些递归函数是没有返回值的。

那我们这样修改：

BTNode* TreeFind(BTNode* root, int x)
{if (NULL == root){return NULL;}if (root->val == x){return root;}return TreeFind(root->left, x) || TreeFind(root->right, x);
}

这样写也是不对的，如果是实现查找x在不在二叉树中，那么可以用这种写法：

bool TreeFind(BTNode* root, int x)
{if (NULL == root){return false;}if (root->val == x){return true;}return TreeFind(root->left, x) || TreeFind(root->right, x);
}

正确写法：

BTNode* TreeFind(BTNode* root, int x)
{if (NULL == root){return NULL;}if (root->val == x){return root;}BTNode* ret1 = TreeFind(root->left, x);if (ret1){return ret1;}BTNode* ret2 = TreeFind(root->right, x);if (ret2){return ret2;}return NULL;
}

当然，也可以简化一下：

BTNode* TreeFind(BTNode* root, int x)
{if (NULL == root){return NULL;}if (root->val == x){return root;}BTNode* ret1 = TreeFind(root->left, x);if (ret1){return ret1;}return TreeFind(root->right, x);
}

第一种写法：为空树就返回空；找到了就返回当前节点；找不到就先找左子树，找到了返回节点；找不到就再找右子树，找到了返回节点；左右子树都找不到就返回空

第二种写法：为空树就返回空；找到了就返回当前节点；找不到就先找左子树，找到了返回节点；找不到就直接返回右子树（因为右子树中如果找到了就返回节点，找不到就返回空，而左右子树都没找到的时候确实应该返回空，所以这样写没有问题 ）

5. 二叉树基础oj练习

  1. 检查两颗树是否相同
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 isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
  1. 单值二叉树

子问题：根（根的值和它的孩子的值进行比较）、左子树、右子树

结束条件（最小子问题）：空树

bool isUnivalTree(struct TreeNode* root)
{if (NULL == root){return true;}if (root->left && root->left->val != root->val){return false;}if (root->right && root->right->val != root->val){return false;}return isUnivalTree(root->left) && isUnivalTree(root->right);
}
  1. 对称二叉树

这道题其实就是检查两棵树是否相同的变形：将左子树和左子树比，右子树和右子树比改成了左子树和右子树比，右子树和左子树比。

bool _isSymmetric(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 _isSymmetric(root1->left, root2->right) && _isSymmetric(root1->right, root2->left);
}bool isSymmetric(struct TreeNode* root)
{return _isSymmetric(root->left, root->right);
}
  1. 二叉树的前序遍历

这道题的第二个参数有些小伙伴可能会觉得有些奇怪，其实这个参数传的是数组大小的一个指针；因为我们最后要返回一个数组，后台为了方便测试，就统一规定了返回数组的时候就要返回数组的大小。

法一：像顺序表一样，空间不够了就扩容

法二：先把树的节点个数算出来，再malloc数组

第一次写的时候可能会出现这样的问题：

int TreeSize(struct TreeNode* root){return NULL == root ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;}void preorder(struct TreeNode* root, int* a, int i)
{if (NULL == root){return;}a[i++] = root->val;preorder(root->left, a, i);preorder(root->right, a, i);
}int* preorderTraversal(struct TreeNode* root, int* returnSize)
{*returnSize = TreeSize(root);int* a = (int*)malloc(sizeof(int) * (*returnSize));preorder(root, a, 0);return a;
}

这样写只能过一部分测试用例，原因在于：函数在递归的时候开辟了很多块栈帧，一个栈帧中的i++是不会影响另一个栈帧中的i的，所以当递归返回的时候上一个递归函数中的i并没有被++，就会导致数组中存的数据被覆盖掉（画递归展开图可以很直观的看出来）

正确代码：

int TreeSize(struct TreeNode* root)
{return NULL == root ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}void preorder(struct TreeNode* root, int* a, int* pi)
{if (NULL == root){return;}a[(*pi)++] = root->val;preorder(root->left, a, pi);preorder(root->right, a, pi);
}int* preorderTraversal(struct TreeNode* root, int* returnSize)
{*returnSize = TreeSize(root);int* a = (int*)malloc(sizeof(int) * (*returnSize));int i = 0;preorder(root, a, &i);return a;
}
  1. 另一颗树的子树

思路：跟原树的每一棵子树进行比较，看是不是相同（比较两棵树是不是相同前面的题已经写过，可以直接复用前面的代码）

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 isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}//查找 + 树的比较
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{if (NULL == root){return false;}if (root->val == subRoot->val && isSameTree(root, subRoot)){return true;}return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
  1. 二叉树的构建及遍历

二叉树的构建

#include <stdio.h>
#include <stdlib.h>typedef struct BinTreeNode
{struct BinTreeNode* left;struct BinTreeNode* right;char val;
}BTNode;BTNode* CreateTree(char* a, int* pi)
{if ('#' == a[(*pi)]){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));root->val = a[(*pi)++];root->left = CreateTree(a, pi);root->right = CreateTree(a, pi);return root;
}void InOrder(BTNode* root)
{if (NULL == root){return;}InOrder(root->left);printf("%c ", root->val);InOrder(root->right);
}int main()
{char a[100];scanf("%s", a);int i = 0;BTNode* root = CreateTree(a, &i);InOrder(root);return 0;
}

补充：

  1. 二叉树的销毁：

用后序比较好（前序也可以，但是比较麻烦，要在销毁根之前把它保存起来）

void TreeDestroy(BTNode* root)
{if (NULL == root){return;}TreeDestroy(root->left);TreeDestroy(root->right);free(root);
}
  1. 层序遍历

层序遍历

//Queue.h#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>typedef struct BinTreeNode* QDataType;typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);

//Test.ctypedef struct BinTreeNode
{struct BinTreeNode* left;struct BinTreeNode* right;int val;
}BTNode;#include "Queue.h"void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->val);//带入下一层if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}printf("\n");QueueDestroy(&q);
}

注： 队列具体的实现由于之前讲过，所以这里就不展示出来了

如果想要把空也打印出来，可以这样写：

void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){printf("%d ", front->val);//带入下一层QueuePush(&q, front->left);QueuePush(&q, front->right);}else{printf("N ");}}printf("\n");QueueDestroy(&q);
}
  1. 判断二叉树是否是完全二叉树
    判断二叉树是否是完全二叉树
bool TreeIsComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);//遇到空以后就跳出后续判断if (NULL == front){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;
}

补充：

二叉树的性质：

  1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点

  2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h - 1

  3. 对任何一棵二叉树, 如果度为0的叶结点个数为n0，度为2的分支结点个数为n2，则有 n0＝n2 ＋ 1

  4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度 h= log2(n + 1) (ps：log2(n + 1) 是log以2为底，n+1为对数)

  5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

  • 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点

  • 若2i+1<n，左孩子序号：2i+1；2i+1>=n，无左孩子

  • 若2i+2<n，右孩子序号：2i+2；2i+2>=n，无右孩子

二叉树的性质
选择题：

  1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（B）
    A 不存在这样的二叉树
    B 200
    C 198
    D 199

  2. 下列数据结构中，不适合采用顺序存储结构的是（A）
    A 非完全二叉树
    B 堆
    C 队列
    D 栈

  3. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（A）
    A n
    B n+1
    C n-1
    D n/2

  4. 一个具有767个节点的完全二叉树，其叶子节点个数为（B）
    A 383
    B 384
    C 385
    D 386

选择题分析

  1. .一棵完全二叉树的节点数位为531个，那么这棵树的高度为（B）
    A 11
    B 10
    C 8
    D 12

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

最新新闻

热搜词

pbootcms优化-列表模板优化 HTML5期末大作业：电商购物网站设计——红色的服装商城B2C网站(40页) HTML+CSS+JavaScript 电商购物功能齐全 dw网页设计 大学生商城购物网站 Vue超详细学习笔记 写一个可拖动的布局 电影网站的建设与站点盈利方式 长江后浪推前浪 被移动支付拍到沙滩上的行业有哪些？

声明：本站所有新闻及新闻图片来源于其他网站，如有侵权，请及时联系我们！

客户服务 | 关于我们 | 版权声明

版权所有：

Copyright 2024 尧图网 All Rights Reserved.QQ:809451989