数据结构——树

参考：数据结构（C++版）第2版 [王红梅]

树和二叉树

基本术语

• 结点的度、树的度：某结点拥有子树的个数为该结点的度（degree），各节点中度最大的值为树的度
• 叶子结点、分支节点：度等于0的结点为叶子节点（leaf node）,度不等于0的结点为分支节点（branch node）
• 结点的层数、树的深度：根节点的层数为1，其孩子节点的层数为k + 1层，层数的最大值为树的深度

二叉树概念

• 满二叉树
  所有分支结点都存在左右子树，所有叶子结点都在同一层，这样的二叉树称为满二叉树
  

• 完全二叉树
  叶子结点只能出现在最后两层上，最后一层的叶子结点都集中在二叉树的左侧。度为1的结点只可能有一个，且这个结点只有左孩子。
  

二叉树的性质

• 第 i 层最多有 2^(i - 1) 个结点 （i >= 1）
• 在深度为 k 的二叉树中，最少有 k 个结点，最多有 2^k - 1
• 二叉树中叶子结点的个数为n0，度为2的结点为n2，则n0 = n2 + 1
• 具有n个结点的完全二叉树的深度为
• 对于完全二叉树，从根节点开始进行编号，对于任意为 i 编号的结点有：
  1. i > 1，则 i 的双亲结点编号为 i / 2
  2. 2i <= n，则 i 的左孩子为 2i
  3. 2i + 1<= n，则 i 的右孩子为 2i + 1

二叉树的存储

顺序存储

用数组来映射二叉树的编号，将二叉树按照完全二叉树进行编号，根据二叉树的性质进行映射

二叉链表

插入结点，按照层序插入

void AddNode(int val)
{TreeNode* node = new TreeNode(val);if (!root){root = node;return;}queue<TreeNode*> qu;qu.push(root);while (!qu.empty()){TreeNode* t = qu.front();qu.pop();if (t->left) qu.push(t->left);else{t->left = node;return;}if (t->right) qu.push(t->right);else{t->right = node;return;}}
}

二叉树的遍历

广度遍历

广度遍历即层序遍历

void LeverOder(TreeNode* node)
{if (node == nullptr) return;queue<TreeNode*> q;q.push(node);while (!q.empty()){TreeNode* t = q.front();q.pop();q.push(t->left);q.push(t->right);cout << t->val << " ";}
}

深度遍历

深度遍历有前序遍历、中序遍历、后续遍历

1.前序遍历：根结点 → 左子树 → 右子树

• 递归方法：

void PreOder(TreeNode* node)
{if (node == nullptr) return;cout << node->val << " ";PreOder(node->left);PreOder(node->right);
}

• 非递归方法：使用栈

void PreOder(TreeNode* root)
{vector<int> vec;stack<TreeNode*> st;st.push(root);while (!st.empty()){TreeNode* tnode = st.top();vec.push_back(tnode->val);st.pop();if (tnode->right != nullptr) st.push(tnode->right);if (tnode->left != nullptr) st.push(tnode->left);}
}

2.中序遍历：左子树→ 根结点 → 右子树

递归方法：

void InOder(TreeNode* node)
{if (node == nullptr) return;PreOder(node->left);cout << node->val << " ";PreOder(node->right);
}

非递归方法：

void InOrder(TreeNode* root)
{vector<int> vec;stack<TreeNode*> st;TreeNode* tnode = root;while (!st.empty() || tnode != nullptr){if (tnode != nullptr){st.push(tnode);tnode = tnode->left;}else{TreeNode* top = st.top();st.pop();vec.push_back(top->val);tnode = top->right;}}
}

3.后序遍历：左子树 → 右子树 → 根结点

递归方法：

void InOder(TreeNode* node)
{if (node == nullptr) return;PreOder(node->left);cout << node->val << " ";PreOder(node->right);
}