C++ 树中到底什么是孩子表示法和父亲表示法
孩子表示法和父亲表示法都是用于表示树的数据结构，它们各有优缺点，适用于不同的场景。
孩子表示法
孩子表示法是一种基于指针的树的表示方法，它将每个节点的左右子节点指针直接存储在该节点中。在孩子表示法中，每个节点包含一个指向左子节点和右子节点的指针，如果一个节点没有左子节点或右子节点，则将其对应的指针设为空。
优点：
孩子表示法方便进行二叉树的遍历和操作。例如，可以通过递归的方式实现前序遍历、中序遍历和后序遍历等算法，也可以通过非递归的方式使用栈等数据结构来实现这些算法。
孩子表示法支持高效的查找、插入和删除等操作。
缺点：
在存储空间方面相对较大，因为需要为每个节点存储两个指针。
对于某些二叉树操作（如判断一棵二叉树是否为平衡二叉树），孩子表示法可能比其他表示方法效率较低。
父亲表示法
父亲表示法是一种基于数组的树的表示方法，它将每个节点的父节点信息存储在该节点中。在父亲表示法中，节点的信息包括节点的值和节点的父节点在数组中的下标。
优点：
在存储空间方面相对较小，因为只需要为每个节点存储一个父节点的下标。
父亲表示法支持一些二叉树操作（如判断一棵二叉树是否为平衡二叉树）的效率较高。
缺点：
父亲表示法不方便进行二叉树的遍历和操作。例如，实现前序遍历、中序遍历和后序遍历等算法需要使用递归或栈等数据结构。
父亲表示法对于节点的删除和插入等操作比较复杂，需要重新调整数组中的节点位置和更新父节点信息。
总之，孩子表示法和父亲表示法都有自己的优点和缺点，需要根据具体场景选择合适的树的表示方法。
基本性质
在二叉树中，每个节点最多有两个子节点，通常称为左子节点和右子节点。如果一个节点没有左子节点或右子节点，则将其对应的指针设为空。二叉树的一个重要性质是，它可以递归地定义为一个根节点和两个分别为根的左子树和右子树的二叉树。
除了具有根、左子节点、右子节点的基本属性外，二叉树还具有以下基本性质：
每个节点的左子树和右子树都是二叉树。
左子树和右子树是有序的，即左子树上的所有节点的值都小于根节点的值，而右子树上的所有节点的值都大于根节点的值。
因为这些基本性质，二叉树是一种非常有用的数据结构，可以用于解决很多计算机科学问题。例如，二叉搜索树是一种基于二叉树的数据结构，它支持高效的插入、删除和搜索操作，被广泛用于数据库、编译器和操作系统等领域。
二叉树的遍历
二叉树的遍历是指按照一定的顺序遍历二叉树的所有节点，常用的遍历方式包括前序遍历、中序遍历和后序遍历。具体定义如下：
前序遍历：按照根节点-左子树-右子树的顺序遍历二叉树。
中序遍历：按照左子树-根节点-右子树的顺序遍历二叉树。
后序遍历：按照左子树-右子树-根节点的顺序遍历二叉树。
二叉树的遍历可以使用递归或非递归的方式实现。递归方式是最简单的实现方法，但存在函数调用的开销，可能导致栈溢出。非递归方式使用栈来模拟递归过程，避免了函数调用的开销，但需要手动维护栈的操作。
二叉树的应用
二叉树是一种常用的数据结构，被广泛应用于计算机科学的各个领域。以下是二叉树的一些常见应用：
二叉搜索树：用于实现动态集合和关联数组等数据结构，支持高效的插入、删除和搜索操作。
平衡树：包括红黑树、AVL树、Treap等，可以保证树的高度始终处于一个较小的范围内，从而保证操作的时间复杂度稳定。
堆：用于实现优先队列等数据结构，可以快速地找到最大或最小元素。
表达式树：用于表示和计算表达式，例如算术表达式和布尔表达式等。
Huffman树：用于实现数据压缩和解压缩等操作。
除了以上的应用之外，二叉树还可以用于图形学、计算几何、网络流等领域，是一种非常基础和重要的数据结构。
下面给出二叉树的前序遍历、中序遍历和后序遍历的递归和非递归实现的代码示例，以及二叉树的层序遍历的代码示例。
二叉树的递归遍历
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 二叉树的前序遍历（递归）
void preorderTraversal(TreeNode* root) {
if (root == nullptr) return;
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 二叉树的中序遍历（递归）
void inorderTraversal(TreeNode* root) {
if (root == nullptr) return;
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
// 二叉树的后序遍历（递归）
void postorderTraversal(TreeNode* root) {
if (root == nullptr) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}二叉树的非递归遍历
#include <stack>
// 二叉树的前序遍历（非递归）
void preorderTraversal(TreeNode* root) {
if (root == nullptr) return;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
cout << node->val << " ";
if (node->right != nullptr) st.push(node->right);
if (node->left != nullptr) st.push(node->left);
}
}
// 二叉树的中序遍历（非递归）
void inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* node = root;
while (!st.empty() || node != nullptr) {
while (node != nullptr) {
st.push(node);
node = node->left;
}
node = st.top();
st.pop();
cout << node->val << " ";
node = node->right;
}
}
// 二叉树的后序遍历（非递归）
void postorderTraversal(TreeNode* root) {
if (root == nullptr) return;
stack<TreeNode*> st1, st2;
st1.push(root);
while (!st1.empty()) {
TreeNode* node = st1.top();
st1.pop();
st2.push(node);
if (node->left != nullptr) st1.push(node->left);
if (node->right != nullptr) st1.push(node->right);
}
while (!st2.empty()) {
TreeNode* node = st2.top();
st2.pop();
cout << node->val << " ";
}
}二叉树的层序遍历
#include <queue>
// 二叉树的层序遍历
void levelOrderTraversal(TreeNode* root) {
if (root == nullptr) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left != nullptr) q.push(node->left);
if (node->right != nullptr) q.push(node->right);
}
}在以上代码中，我们使用了 STL 中的 stack 和 queue 数据结构，实现了二叉树的遍历和层序遍历。
另外，需要注意的是，二叉树的遍历和层序遍历的时间复杂度都是 O(n)，其中 n 是二叉树的节点数。因为在遍历每个节点的时候，都只是对其进行了一次访问操作。但空间复杂度可能会达到 O(n)，因为需要使用栈或队列来存储节点。
