树

树的一些代码(C/C++非模板实现)

代码示例

#include <iostream>
#include <limits.h>
#include <queue>
#include <stack>
#include <utility>

struct TreeNode {
  int data;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
typedef struct TreeNode *Tree;

// 非递归函数，根据先根遍历的数据构建二叉树
TreeNode *buildTree(int data[], int n) {
  if (n == 0)
    return nullptr;
  TreeNode *root = new TreeNode(data[0]);
  TreeNode *current = root;
  std::stack<TreeNode *> nodeStack;
  nodeStack.push(current);
  for (int i = 1; i < n; i++) {
    if (data[i] != -1) {
      current->left = new TreeNode(data[i]);
      current = current->left;
      nodeStack.push(current);
    } else {
      while (!nodeStack.empty() && data[i] == -1) {
        current = nodeStack.top();
        nodeStack.pop();
        i++;
      }
      if (i < n && data[i] != -1) {
        if (data[i] == 9 || data[i] == 10) {
          std::cerr << "current: " << current->data << std::endl;
        }
        current->right = new TreeNode(data[i]);
        current = current->right;
        nodeStack.push(current);
      }
    }
  }
  return root;
}

// 辅助函数，用于前序遍历验证建立的树
void inOrderTraversal(Tree root) {
  if (root) {
    std::cout << root->data << " ";
    inOrderTraversal(root->left);
    inOrderTraversal(root->right);
  }
}

// TODO 满二叉树鉴定
/*
Algorithm IsCompleteBinaryTree(root):
    Input: 二叉树的根节点 root
    Output: 布尔值，表示是否为完全二叉树

    1. 初始化一个队列 queue，并将根节点 root 入队。
    2. 初始化一个标志位 isComplete 为 true。
    3. 开始循环：
        a. 从队列中取出一个节点 node。
        b. 如果 node 为 null，则执行下一步。
        c. 如果 isComplete 为 false，而且 node 不为 null，返回 false。
        d. 如果 node 不为 null，将 node 的左子节点和右子节点入队。
        e. 如果 node 为 null，将 isComplete 设置为 false。
        f. 如果队列为空，跳出循环。
    4. 如果队列中还有节点，返回 false；否则，返回 true。

通过这个算法，我们逐层遍历二叉树节点，一旦遇到一个空节点后，就设置 isComplete 为
false。如果在此之后还有非空节点，就可以确定这不是一个完全二叉树。如果整个过程完成，没有发现不满足条件的节点，那么这是一个完全二叉树。
*/

// TODO 二叉树从root的最长路径
/*
Algorithm FindLongestPath(root):
    Input: 二叉树的根节点 root
    Output: 一条最长路径上的各结点的值

    1. 初始化一个变量 maxPath 为空列表，用于存储最长路径。
    2. 初始化一个变量 maxLength 为 0，用于记录最长路径的长度。
    3. 调用辅助函数 DFS(root, [],
0)，传入根节点、当前路径、当前路径长度、maxPath 和 maxLength。
    4. 返回 maxPath，即一条最长路径上的各结点的值。

Algorithm DFS(node, path, length, maxPath, maxLength):
    1. 如果节点 node 为空，返回。
    2. 将节点 node 的值添加到路径 path 中。
    3. 增加 length 值。
    4. 如果 length 大于 maxLength，则更新 maxLength 和 maxPath 为当前路径 path。
    5. 递归调用 DFS(node 的左子节点, path, length, maxPath, maxLength)。
    6. 递归调用 DFS(node 的右子节点, path, length, maxPath, maxLength)。
*/

// TODO 判断树相似
/*
Algorithm AreSimilar(root1, root2):
    Input: 两棵二叉树的根节点 root1 和 root2
    Output: 布尔值，表示两棵树是否相似

    1. 如果 root1 和 root2 都为空，返回 true，它们是相似的。
    2. 如果 root1 和 root2 中只有一个为空，返回 false，它们不是相似的。
    3. 如果 root1 和 root2 的值不相等，返回 false，它们不是相似的。
    4. 递归调用 AreSimilar(root1 的左子树, root2 的左子树) 并递归调用
AreSimilar(root1 的右子树, root2 的右子树)。
    5. 如果步骤4中的两次递归都返回 true，返回 true；否则返回 false。
*/

// 完全二叉树判断非递归
bool IsCBT(Tree root) {
  std::queue<TreeNode *> que;
  que.push(root);
  bool meetleaf = false;
  while (!que.empty()) {
    auto head = que.front();
    que.pop();
    auto l = head->left;
    auto r = head->right;
    if ((meetleaf && (!l || !r)) || (r && !l))
      return false;
    if (r)
      que.push(r);
    if (l)
      que.push(l);
    /* if (!l||!r) */
    if (!r)
      meetleaf = true;
  }
  return true;
}
// 平衡二叉树判断
std::pair<bool, int> IsBT(Tree root) {
  if (!root) {
    return std::pair<bool, int>{true, 0};
  }
  std::pair<bool, int> l = IsBT(root->left);
  std::pair<bool, int> r = IsBT(root->right);
  return std::pair<bool, int>{
      l.first && r.first &&
          (l.second - r.second >= -1 && l.second - r.second <= 1),
      1 + (l.second >= r.second ? l.second : r.second)};
}
// 搜索二叉树
std::pair<bool, std::pair<int, int>> IsBST(Tree root) {
  if (!root)
    return {true, {INT_MAX, INT_MIN}};
  auto l = IsBST(root->left);
  auto r = IsBST(root->right);
  return {l.first && r.first && root->data > l.second.first &&
              root->data < r.second.second,
          {l.second.first, r.second.second}
  };
}
bool IsBST2(Tree root, int minVal = INT_MIN, int maxVal = INT_MAX) {
    if (!root)
        return true;

    if (root->data <= minVal || root->data >= maxVal)
        return false;

    return IsBST2(root->left, minVal, root->data) && IsBST2(root->right, root->data, maxVal);
}


int main() {
  // Balanced
  int data[] = {1, 2, 3,  4, -1, -1, -1, 5,  -1, 6,  -1, -1,
                7, 8, -1, 9, -1, -1, 10, 11, -1, -1, -1};
  // Not Balanced
  /* int data[] = {1, 2, 3, 4, -1, -1, -1, 5, 6, 7, -1, -1, 8, -1, -1, -1}; */

  int n = sizeof(data) / sizeof(data[0]);
  Tree root = buildTree(data, n);
  inOrderTraversal(root);
  std::cout << std::endl << IsBT(root).first;

  return 0;
}