数据结构——树

参考：数据结构（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 编号的结点有：
  
  
  • i > 1，则 i 的双亲结点编号为 i / 2
    
  • 2i <= n，则 i 的左孩子为 2i
    
  • 2i + 1<= n，则 i 的右孩子为 2i + 1
    
  
  

二叉树的存储

次序存储

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

二叉链表

插入结点，按照层序插入

1. void AddNode(int val)
2. {
3.     TreeNode* node = new TreeNode(val);
4.     if (!root)
5.     {
6.         root = node;
7.         return;
8.     }
10.     queue<TreeNode*> qu;
11.     qu.push(root);
12.     while (!qu.empty())
13.     {
14.         TreeNode* t = qu.front();
15.         qu.pop();
17.         if (t->left) qu.push(t->left);
18.         else
19.         {
20.             t->left = node;
21.             return;
22.         }
24.         if (t->right) qu.push(t->right);
25.         else
26.         {
27.             t->right = node;
28.             return;
29.         }
31.     }
32. }

复制代码

二叉树的遍历

广度遍历

广度遍历即层序遍历

1. void LeverOder(TreeNode* node)
2. {
3.     if (node == nullptr) return;
5.     queue<TreeNode*> q;
6.     q.push(node);
7.     while (!q.empty())
8.     {
9.         TreeNode* t = q.front();
10.         q.pop();
11.         q.push(t->left);
12.         q.push(t->right);
13.         cout << t->val << " ";
14.     }
15. }

复制代码

深度遍历

深度遍历有前序遍历、中序遍历、后续遍历
1.前序遍历：根结点 → 左子树 → 右子树

• 递归方法：
  

1. void PreOder(TreeNode* node)
2. {
3.     if (node == nullptr) return;
5.     cout << node->val << " ";
6.     PreOder(node->left);
7.     PreOder(node->right);
8. }

复制代码

• 非递归方法：使用栈
  

1. void PreOder(TreeNode* root)
2. {
3.     vector<int> vec;
4.     stack<TreeNode*> st;
5.     st.push(root);
7.     while (!st.empty())
8.     {
9.         TreeNode* tnode = st.top();
10.         vec.push_back(tnode->val);
11.         st.pop();
12.         if (tnode->right != nullptr) st.push(tnode->right);
13.         if (tnode->left != nullptr) st.push(tnode->left);
14.     }
15. }

复制代码

2.中序遍历：左子树→ 根结点 → 右子树
递归方法：

1. void InOder(TreeNode* node)
2. {
3.     if (node == nullptr) return;
5.     PreOder(node->left);
6.     cout << node->val << " ";
7.     PreOder(node->right);
8. }

复制代码

非递归方法：

1. void InOrder(TreeNode* root)
2. {
3.     vector<int> vec;
4.     stack<TreeNode*> st;
5.     TreeNode* tnode = root;
7.     while (!st.empty() || tnode != nullptr)
8.     {
9.         if (tnode != nullptr)
10.         {
11.             st.push(tnode);
12.             tnode = tnode->left;
13.         }
14.         else
15.         {
16.             TreeNode* top = st.top();
17.             st.pop();
18.             vec.push_back(top->val);
19.             tnode = top->right;
20.         }
21.     }
22. }

复制代码

3.后序遍历：左子树 → 右子树 → 根结点
递归方法：

1. void InOder(TreeNode* node)
2. {
3.     if (node == nullptr) return;
5.     PreOder(node->left);
6.     cout << node->val << " ";
7.     PreOder(node->right);
8. }

复制代码

二叉搜索树

二叉搜索树又称为二叉排序树、二叉查找树
特点

• 非空左子树的全部键值小于其根结点的键值。
  
• 非空右子树的全部键值大于其根结点的键值。
  
• 左、右子树都是二叉搜索树。
  

查找最大和最小元素

• 最大元素肯定是在树的最右分枝的端结点上。
  
• 最小元素肯定是在树的最左分枝的端结点上。
  

次序

二叉搜索树的中序遍历是有序的
题单：
530.二叉搜索树的最小绝对差