1. 什么是二叉树二叉树Binary Tree是计算机科学中最基础且最重要的数据结构之一。它是一种树形结构其中每个节点最多有两个子节点通常称为左子节点和右子节点。2. 二叉树的基本概念2.1 节点结构每个二叉树节点通常包含三个部分数据域存储节点的值左指针指向左子节点右指针指向右子节点typedef int BTDataType; typedef struct BinaryTree { struct BinaryTree* left; struct BinaryTree* right; BTDataType data; }BT;2.2 常见术语根节点树的顶端节点叶子节点没有子节点的节点深度从根节点到该节点的路径长度高度从该节点到最远叶子节点的路径长度度节点的子节点个数二叉树中每个节点的度 ≤ 23. 二叉树的性质二叉树具有一些重要的数学性质这些性质是理解和分析二叉树算法的基础。性质 1在二叉树的第 i 层上至多有 2^(i-1) 个节点 (i ≥ 1)。性质 2深度为 k 的二叉树至多有 2^k - 1 个节点 (k ≥ 1)。性质 3对于任何一棵二叉树如果其叶子节点数为 n0度为 2 的节点数为 n2则 n0 n2 1。(选择题常考性质 4具有 n 个节点的完全二叉树的深度为 ⌊log2n⌋ 1。性质 5对一棵有 n 个节点的完全二叉树按层序编号从 1 开始则对任意节点 i (1 ≤ i ≤ n) 有如果 i 1则节点 i 是二叉树的根无双亲如果 i 1则其双亲节点是 ⌊i/2⌋。如果 2i ≤ n则节点 i 的左孩子是 2i否则无左孩子。如果 2i 1 ≤ n则节点 i 的右孩子是 2i 1否则无右孩子。这些性质在分析二叉树算法的时间复杂度、空间复杂度以及设计高效算法时非常有用。4. 二叉树的存储二叉树的存储方式主要分为两种顺序存储和链式存储。选择哪种存储方式取决于具体的应用场景和对操作效率的要求。4.1 顺序存储顺序存储使用数组或列表来存储二叉树节点。这种存储方式特别适合完全二叉树或满二叉树因为可以充分利用数组空间且能通过下标快速定位父子节点关系。存储规则将二叉树的节点按照层序遍历的顺序依次存入数组中。对于任意节点如果其在数组中的下标为i则其左子节点的下标为2*i 1。其右子节点的下标为2*i 2。其父节点的下标为⌊(i-1)/2⌋。优点存储紧凑无指针开销空间利用率高对完全二叉树。通过下标计算即可访问父子节点访问速度快。适合存储静态二叉树或需要频繁随机访问的场景。缺点对于非完全二叉树数组中间会出现大量空位造成空间浪费。插入和删除节点可能涉及大量数据移动效率较低。4.2 链式存储链式存储是二叉树最常用、最灵活的存储方式。每个节点通过指针或引用连接其左右子节点。优点结构灵活能高效表示任意形状的二叉树包括普通二叉树、斜树等。插入和删除节点只需修改指针效率高。动态分配内存无需预先确定树的最大规模。缺点每个节点需要额外的指针空间存储开销较大。访问节点需要遍历指针链随机访问效率低于顺序存储。可能存在内存碎片问题。4.3 存储方式的选择在实际应用中应根据具体需求选择合适的存储方式场景推荐存储方式理由完全二叉树/满二叉树且规模固定顺序存储空间利用率高访问速度快代码简单。需要频繁插入、删除节点的动态二叉树链式存储操作灵活无需移动大量数据。堆优先队列的实现顺序存储数组符合堆的完全二叉树性质能高效进行上浮/下沉操作。理解这两种存储方式是实现二叉树各种算法如遍历、查找、插入、删除的基础。在后续的遍历算法和面试题实现中我们将主要使用链式存储因为它更通用更能体现二叉树的递归特性。5. 二叉树的遍历算法在二叉树的遍历中始终要将 一棵 二叉树 分为 根节点左子树右子树而子树继续分为 根节点左子树右子树一直细分直至遍历结束。在遍历算法中主要是利用递归的思想。这里我们还未接触二叉树的真正创建方式在这里我们先手搓一棵二叉树来方便下面的遍历。//二叉树的创建 BT* BuyNode(BTDataType x) { BT* newnode (BT*)malloc(sizeof(BT)); if (newnode NULL) { perror(malloc failed!); return 0; } newnode-data x; newnode-left newnode-right NULL; return newnode; } BT* root BuyNode(1); BT* Node1 root-left BuyNode(2); BT* Node2 root-right BuyNode(3); BT* Node3 Node1-left BuyNode(4); BT* Node5 Node3-left BuyNode(5); BT* Node6 Node3-right BuyNode(6); BT* Node4 Node2-right BuyNode(7);5.1 深度优先遍历DFS5.1.1 前序遍历根-左-右// 二叉树前序遍历 void PreOrder(BT* root) { if (root NULL) { printf(N ); return; } printf(%d , root-data); PreOrder(root-left); PreOrder(root-right); }5.1.2 中序遍历左-根-右// 二叉树中序遍历 void InOrder(BT* root) { if (root NULL) { printf(N ); return; } InOrder(root-left); printf(%d , root-data); InOrder(root-right); }5.1.3 后序遍历左-右-根// 二叉树后序遍历 void PostOrder(BT* root) { if (root NULL) { printf(N ); return; } PostOrder(root-left); PostOrder(root-right); printf(%d , root-data); }5.2 广度优先遍历BFS5.2.1 层序遍历思路使用队列 “先进先出” 的特性在将 根节点 入队时将其的左孩子和右孩子同时入队直至队列为空则遍历完成。//队尾入队 void QPush(Que* pst,QDataType node) { assert(pst); QNode* newnode (QNode*)malloc(sizeof(QNode)); if (newnode NULL) { perror(malloc failed!); return; } newnode-data node; newnode-next NULL; if (pst-phead NULL)//这里不能使用 pst-phead pst-ptail来判断当只有一个元素这个条件同样成立 { pst-phead pst-ptail newnode; } else { pst-ptail-next newnode; pst-ptail newnode; } pst-size; } //队头出队 void QPop(Que* pst) { assert(pst); if (pst-phead-next NULL) { free(pst-phead); pst-phead pst-ptail NULL; } else { QNode* next pst-phead-next; free(pst-phead); pst-phead next; } pst-size--; } //队列的初始化 void QInit(Que* pst) { assert(pst); pst-phead pst-ptail NULL; pst-size 0; } //队列的判空 bool QEmpty(Que* pst) { assert(pst); return pst-size 0; } //取队头元素 QDataType QTop(Que* pst) { assert(pst); assert(pst-size 0); return pst-phead-data; } //二叉树的层序遍历 void LevelOrder(BT* root) { Que queue; QInit(queue); QPush(queue, root); while (!QEmpty(queue)) { BT* cur QTop(queue); QPop(queue); printf(%d , cur-data); if(cur-left ! NULL) QPush(queue, cur-left); if(cur-right ! NULL) QPush(queue, cur-right); } }5.3 二叉树的其他算法5.3.1 二叉树结点个数// 二叉树结点个数 int BinaryTreeSize1(BT* root, int* psize) { if (root NULL) return 0; else { (*psize); BinaryTreeSize1(root-left,psize); BinaryTreeSize1(root-right, psize); } return *psize; } // 二叉树结点个数 int BinaryTreeSize2(BT* root) { static int size 0; //使用静态变量时调用第二次会持续累加 if (root NULL) return 0; else { size; BinaryTreeSize2(root-left); BinaryTreeSize2(root-right); } return size; } // 二叉树结点个数 int size 0;//使用全局变量 int BinaryTreeSize3(BT* root) { if (root NULL) return 0; else { size; BinaryTreeSize3(root-left); BinaryTreeSize3(root-right); } return size; } // 二叉树结点个数 //将二叉树看做 根节点左子树右子树 int BinaryTreeSize4(BT* root) { if (root NULL) return 0; return BinaryTreeSize4(root-left) BinaryTreeSize4(root-right)1; }5.3.2二叉树叶子结点个数// 二叉树叶子结点个数 int BinaryTreeLeafSize(BT* root) { if (root NULL) return 0; if (root-left NULL root-right NULL) return 1; return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right); }5.3.3二叉树第k层结点个数// 二叉树第k层结点个数 int BinaryTreeLevelKSize(BT* root, int k) { if (root NULL) return 0; if (k 1) return 1; return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1); }5.3.4 二叉树查找值为x的结点// 二叉树查找值为x的结点 BT* BinaryTreeFind(BT* root, BTDataType x) { if (root NULL) return NULL; if (root-data x) return root; BT* ret1 BinaryTreeFind(root-left, x); if (ret1) return ret1; return BinaryTreeFind(root-right, x); }5.3.5 二叉树的高度//二叉树的高度 int BinaryHight(BT* root) { if (root NULL) return 0; int LeftHight BinaryHight(root-left); int RightHight BinaryHight(root-right); return LeftHight RightHight ? LeftHight 1 : RightHight 1; }5.3.6二叉树的销毁//二叉树的销毁 void BinaryDestroy(BT* root) { if (root NULL) return; BinaryDestroy(root-left); BinaryDestroy(root-right); free(root);//函数调用之后要及时置空或者直接使用二级指针作为参数在本函数体内将其置空 }5. 总结二叉树是数据结构与算法学习的基石掌握其基本概念、遍历方法和常见变种对于编程能力的提升至关重要。通过实际编码练习来加深理解从简单的递归遍历开始逐步挑战更复杂的二叉树问题。 数据结构：二叉树
1. 什么是二叉树二叉树Binary Tree是计算机科学中最基础且最重要的数据结构之一。它是一种树形结构其中每个节点最多有两个子节点通常称为左子节点和右子节点。2. 二叉树的基本概念2.1 节点结构每个二叉树节点通常包含三个部分数据域存储节点的值左指针指向左子节点右指针指向右子节点typedef int BTDataType; typedef struct BinaryTree { struct BinaryTree* left; struct BinaryTree* right; BTDataType data; }BT;2.2 常见术语根节点树的顶端节点叶子节点没有子节点的节点深度从根节点到该节点的路径长度高度从该节点到最远叶子节点的路径长度度节点的子节点个数二叉树中每个节点的度 ≤ 23. 二叉树的性质二叉树具有一些重要的数学性质这些性质是理解和分析二叉树算法的基础。性质 1在二叉树的第 i 层上至多有 2^(i-1) 个节点 (i ≥ 1)。性质 2深度为 k 的二叉树至多有 2^k - 1 个节点 (k ≥ 1)。性质 3对于任何一棵二叉树如果其叶子节点数为 n0度为 2 的节点数为 n2则 n0 n2 1。(选择题常考性质 4具有 n 个节点的完全二叉树的深度为 ⌊log2n⌋ 1。性质 5对一棵有 n 个节点的完全二叉树按层序编号从 1 开始则对任意节点 i (1 ≤ i ≤ n) 有如果 i 1则节点 i 是二叉树的根无双亲如果 i 1则其双亲节点是 ⌊i/2⌋。如果 2i ≤ n则节点 i 的左孩子是 2i否则无左孩子。如果 2i 1 ≤ n则节点 i 的右孩子是 2i 1否则无右孩子。这些性质在分析二叉树算法的时间复杂度、空间复杂度以及设计高效算法时非常有用。4. 二叉树的存储二叉树的存储方式主要分为两种顺序存储和链式存储。选择哪种存储方式取决于具体的应用场景和对操作效率的要求。4.1 顺序存储顺序存储使用数组或列表来存储二叉树节点。这种存储方式特别适合完全二叉树或满二叉树因为可以充分利用数组空间且能通过下标快速定位父子节点关系。存储规则将二叉树的节点按照层序遍历的顺序依次存入数组中。对于任意节点如果其在数组中的下标为i则其左子节点的下标为2*i 1。其右子节点的下标为2*i 2。其父节点的下标为⌊(i-1)/2⌋。优点存储紧凑无指针开销空间利用率高对完全二叉树。通过下标计算即可访问父子节点访问速度快。适合存储静态二叉树或需要频繁随机访问的场景。缺点对于非完全二叉树数组中间会出现大量空位造成空间浪费。插入和删除节点可能涉及大量数据移动效率较低。4.2 链式存储链式存储是二叉树最常用、最灵活的存储方式。每个节点通过指针或引用连接其左右子节点。优点结构灵活能高效表示任意形状的二叉树包括普通二叉树、斜树等。插入和删除节点只需修改指针效率高。动态分配内存无需预先确定树的最大规模。缺点每个节点需要额外的指针空间存储开销较大。访问节点需要遍历指针链随机访问效率低于顺序存储。可能存在内存碎片问题。4.3 存储方式的选择在实际应用中应根据具体需求选择合适的存储方式场景推荐存储方式理由完全二叉树/满二叉树且规模固定顺序存储空间利用率高访问速度快代码简单。需要频繁插入、删除节点的动态二叉树链式存储操作灵活无需移动大量数据。堆优先队列的实现顺序存储数组符合堆的完全二叉树性质能高效进行上浮/下沉操作。理解这两种存储方式是实现二叉树各种算法如遍历、查找、插入、删除的基础。在后续的遍历算法和面试题实现中我们将主要使用链式存储因为它更通用更能体现二叉树的递归特性。5. 二叉树的遍历算法在二叉树的遍历中始终要将 一棵 二叉树 分为 根节点左子树右子树而子树继续分为 根节点左子树右子树一直细分直至遍历结束。在遍历算法中主要是利用递归的思想。这里我们还未接触二叉树的真正创建方式在这里我们先手搓一棵二叉树来方便下面的遍历。//二叉树的创建 BT* BuyNode(BTDataType x) { BT* newnode (BT*)malloc(sizeof(BT)); if (newnode NULL) { perror(malloc failed!); return 0; } newnode-data x; newnode-left newnode-right NULL; return newnode; } BT* root BuyNode(1); BT* Node1 root-left BuyNode(2); BT* Node2 root-right BuyNode(3); BT* Node3 Node1-left BuyNode(4); BT* Node5 Node3-left BuyNode(5); BT* Node6 Node3-right BuyNode(6); BT* Node4 Node2-right BuyNode(7);5.1 深度优先遍历DFS5.1.1 前序遍历根-左-右// 二叉树前序遍历 void PreOrder(BT* root) { if (root NULL) { printf(N ); return; } printf(%d , root-data); PreOrder(root-left); PreOrder(root-right); }5.1.2 中序遍历左-根-右// 二叉树中序遍历 void InOrder(BT* root) { if (root NULL) { printf(N ); return; } InOrder(root-left); printf(%d , root-data); InOrder(root-right); }5.1.3 后序遍历左-右-根// 二叉树后序遍历 void PostOrder(BT* root) { if (root NULL) { printf(N ); return; } PostOrder(root-left); PostOrder(root-right); printf(%d , root-data); }5.2 广度优先遍历BFS5.2.1 层序遍历思路使用队列 “先进先出” 的特性在将 根节点 入队时将其的左孩子和右孩子同时入队直至队列为空则遍历完成。//队尾入队 void QPush(Que* pst,QDataType node) { assert(pst); QNode* newnode (QNode*)malloc(sizeof(QNode)); if (newnode NULL) { perror(malloc failed!); return; } newnode-data node; newnode-next NULL; if (pst-phead NULL)//这里不能使用 pst-phead pst-ptail来判断当只有一个元素这个条件同样成立 { pst-phead pst-ptail newnode; } else { pst-ptail-next newnode; pst-ptail newnode; } pst-size; } //队头出队 void QPop(Que* pst) { assert(pst); if (pst-phead-next NULL) { free(pst-phead); pst-phead pst-ptail NULL; } else { QNode* next pst-phead-next; free(pst-phead); pst-phead next; } pst-size--; } //队列的初始化 void QInit(Que* pst) { assert(pst); pst-phead pst-ptail NULL; pst-size 0; } //队列的判空 bool QEmpty(Que* pst) { assert(pst); return pst-size 0; } //取队头元素 QDataType QTop(Que* pst) { assert(pst); assert(pst-size 0); return pst-phead-data; } //二叉树的层序遍历 void LevelOrder(BT* root) { Que queue; QInit(queue); QPush(queue, root); while (!QEmpty(queue)) { BT* cur QTop(queue); QPop(queue); printf(%d , cur-data); if(cur-left ! NULL) QPush(queue, cur-left); if(cur-right ! NULL) QPush(queue, cur-right); } }5.3 二叉树的其他算法5.3.1 二叉树结点个数// 二叉树结点个数 int BinaryTreeSize1(BT* root, int* psize) { if (root NULL) return 0; else { (*psize); BinaryTreeSize1(root-left,psize); BinaryTreeSize1(root-right, psize); } return *psize; } // 二叉树结点个数 int BinaryTreeSize2(BT* root) { static int size 0; //使用静态变量时调用第二次会持续累加 if (root NULL) return 0; else { size; BinaryTreeSize2(root-left); BinaryTreeSize2(root-right); } return size; } // 二叉树结点个数 int size 0;//使用全局变量 int BinaryTreeSize3(BT* root) { if (root NULL) return 0; else { size; BinaryTreeSize3(root-left); BinaryTreeSize3(root-right); } return size; } // 二叉树结点个数 //将二叉树看做 根节点左子树右子树 int BinaryTreeSize4(BT* root) { if (root NULL) return 0; return BinaryTreeSize4(root-left) BinaryTreeSize4(root-right)1; }5.3.2二叉树叶子结点个数// 二叉树叶子结点个数 int BinaryTreeLeafSize(BT* root) { if (root NULL) return 0; if (root-left NULL root-right NULL) return 1; return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right); }5.3.3二叉树第k层结点个数// 二叉树第k层结点个数 int BinaryTreeLevelKSize(BT* root, int k) { if (root NULL) return 0; if (k 1) return 1; return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1); }5.3.4 二叉树查找值为x的结点// 二叉树查找值为x的结点 BT* BinaryTreeFind(BT* root, BTDataType x) { if (root NULL) return NULL; if (root-data x) return root; BT* ret1 BinaryTreeFind(root-left, x); if (ret1) return ret1; return BinaryTreeFind(root-right, x); }5.3.5 二叉树的高度//二叉树的高度 int BinaryHight(BT* root) { if (root NULL) return 0; int LeftHight BinaryHight(root-left); int RightHight BinaryHight(root-right); return LeftHight RightHight ? LeftHight 1 : RightHight 1; }5.3.6二叉树的销毁//二叉树的销毁 void BinaryDestroy(BT* root) { if (root NULL) return; BinaryDestroy(root-left); BinaryDestroy(root-right); free(root);//函数调用之后要及时置空或者直接使用二级指针作为参数在本函数体内将其置空 }5. 总结二叉树是数据结构与算法学习的基石掌握其基本概念、遍历方法和常见变种对于编程能力的提升至关重要。通过实际编码练习来加深理解从简单的递归遍历开始逐步挑战更复杂的二叉树问题。