Binary Trees(二叉树)

他是涉及如何高效实现一个集合的问题

Tree(树)

一种有向的、无环的链接节点结构。

• 什么是有向？:

  节点之间有单向链接。

• 什么是无环？:

  没有路径会回绕到同一节点两次。

最常见的树结构是二叉树。

Binary Tree(二叉树)

二叉树就是每个节点最多有两个子节点的树。

树要么是空,要么是一个根节点

• 空: 树中没有节点(nullptr)
• 根节点: 树的顶端节点
  • 数据
  • 左子树
  • 右子树

---

tree node

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

---

print tree

void print(TreeNode* node) {
    cout << node->date << endl;
    if (node->left != nullptr) {
        print(node->left);
    }
    if (node->right != nullptr) {
        print(node->right);
    }
}

但是这段代码有个小问题: 就是根节点如果为空，那么就会崩溃。

void print(TreeNode* node) {
    if (node != nullptr) {
        cout << node->date << endl;
        print(node->left);
        print(node->right);
    }
}

---

size of tree

int size(TreeNode* node) {
    if (node == nullptr) {
        return 0;
    }else {
        return 1 + size(node->left) + size(node->right);
    }
}