企业官网建设流程全解析

1. 什么是二叉树？

二叉树（Binary Tree）是计算机科学中最基础且最重要的数据结构之一。它是一种树形结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。

2. 二叉树的基本概念

2.1 节点结构

每个二叉树节点通常包含三个部分：

• 数据域：存储节点的值
• 左指针：指向左子节点
• 右指针：指向右子节点

• typedef int BTDataType; typedef struct BinaryTree { struct BinaryTree* left; struct BinaryTree* right; BTDataType data; }BT;

2.2 常见术语

• 根节点：树的顶端节点
• 叶子节点：没有子节点的节点
• 深度：从根节点到该节点的路径长度
• 高度：从该节点到最远叶子节点的路径长度
• 度：节点的子节点个数（二叉树中每个节点的度 ≤ 2）

3. 二叉树的性质

二叉树具有一些重要的数学性质，这些性质是理解和分析二叉树算法的基础。

性质 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 深度优先遍历（DFS）

5.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 广度优先遍历（BFS）

5.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. 总结

二叉树是数据结构与算法学习的基石，掌握其基本概念、遍历方法和常见变种对于编程能力的提升至关重要。通过实际编码练习来加深理解，从简单的递归遍历开始，逐步挑战更复杂的二叉树问题。