1.16 - 二叉树的中序遍历动态多态的实现原理-洪萨配资

1.二叉树的中序遍历

a.核心思想

b.思路

c.步骤

2.动态多态的实现原理

a.核心思想

b.实现逻辑

c.示例逻辑

1.二叉树的中序遍历

94. 二叉树的中序遍历 - 力扣（LeetCode）https://leetcode.cn/problems/binary-tree-inorder-traversal/

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), * right(right) {} * }; */ class Solution { public: void inorder(TreeNode* root, std::vector<int>& res) { if (root == nullptr) return; inorder(root->left, res); res.push_back(root->val); inorder(root->right, res); } std::vector<int> inorderTraversal(TreeNode* root) { vector<int> res; inorder(root, res); return res; } };

a.核心思想

利用二叉树中序遍历的规则（左子树 -> 根节点 -> 右子树），通过递归的方式依次访问二叉树的节点，将访问到的节点值按顺序存储到结果数组中。

b.思路

定义一个递归函数，该函数接收当前节点和一个用于存储结果的引用数组作为参数。在递归函数中，首先判断当前节点是否为空，若为空则直接返回；否则，先递归遍历左子树，然后将当前节点的值加入结果数组，最后递归遍历右子树。

c.步骤

① 定义递归函数inorder，参数为当前节点root和结果数组的引用res。
② 在inorder函数中，若root为空，返回。
③ 递归调用inorder遍历左子树。
④ 将root的值加入res。
⑤ 递归调用inorder遍历右子树。
⑥ 在主函数中，初始化结果数组，调用inorder函数，返回结果数组。

2.动态多态的实现原理

a.核心思想

动态多态通过虚函数表（vtable）+ 虚指针（vptr）实现运行时绑定，根据对象实际类型调用对应函数。

b.实现逻辑

① 虚函数表（vtable）：编译器为每个含虚函数的类生成一张表，存储该类所有虚函数的实际地址（派生类覆盖基类虚函数时更新表项）。
② 虚指针（vptr）：对象内存首地址存放指向自身类vtable的指针（由构造函数初始化）。
③ 动态绑定：通过基类指针/引用调用虚函数时，通过vptr定位vtable，根据函数偏移量跳转到实际函数执行（非静态绑定）。

c.示例逻辑

class Base { public: virtual void func() { /*...*/ } // 基类虚函数 }; class Derived : public Base { public: void func() override { /*...*/ } // 覆盖基类虚函数 }; int main() { Base* obj = new Derived(); obj->func(); // 运行时调用Derived::func() return 0; }