PAT树笔记

算法树的遍历二叉搜索树完全二叉树 AVL树

字数统计: 4.9k阅读时长: 24 min

 2023/08/13 

PAT考试树相关笔记

二叉树的遍历

[1020] Tree Traversals

⼆叉树的遍历，后序中序转层序

题目

给定⼀棵⼆叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这⾥假设键值都是互不相等的正整数。

分析与注意点

create函数的返回值是TreeNode类型指针。
根据后序和中序构建二叉树的要点是后序的最后一个结点就是根结点，在中序中找到此结点，以此为分界线，左边是左子树，右边是右子树，递归搜寻。
在中序中找到的下标为$k$的话，左子树中结点的个数就为 $k-inL$，记作 $numberLeft$，以此我们可以对当前后序和中序遍历进行切分：
- 后序遍历 => 左子树 $[postL, postL+numberLeft-1]$，右子树 $[postL+numberLeft, postR-1]$
- 中序遍历 => 左子树 $[inL, k-1]$，右子树 $[k+1, inR]$
递归的结束条件为给定后序遍历的左右范围中左范围大于右范围
层序遍历就用队列来维护就行

代码

#include <bits/stdc++.h>
using namespace std;
vector<int> postOrder, inOrder;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
};

TreeNode* create(int postL, int postR, int inL, int inR) {
  if (postL > postR)
    return NULL;
  TreeNode* root = new TreeNode;
  root -> val = postOrder[postR];
  int k;
  for (k = inL; k <= inR; k++)
    if (inOrder[k] == postOrder[postR])
      break;
  int numberLeft = k - inL;
  root -> left = create(postL, postL + numberLeft - 1, inL, k - 1);
  root -> right = create(postL + numberLeft, postR - 1, k + 1, inR);
  return root;
}

void levelTraversal(TreeNode* root, int n) {
  if (!root)  return;
  queue<TreeNode*> q;
  q.push(root);
  int num = 0;
  while(!q.empty()) {
    TreeNode* cur = q.front();
    q.pop();
    cout << cur -> val;
    num++;
    if (num < n)  cout << " ";
    if (cur -> left)  q.push(cur -> left);
    if (cur -> right)  q.push(cur -> right);
  }
  return;
}

int main() {
  int n;
  cin >> n;
  postOrder.resize(n);
  inOrder.resize(n);
  for (int i = 0; i < n; i++)  cin >> postOrder[i];
  for (int i = 0; i < n; i++)  cin >> inOrder[i];
  TreeNode* root = create(0, n-1, 0, n-1);
  levelTraversal(root, n);
  return 0;
}

[1086] Tree Traversals Again

⼆叉树的遍历，先序中序转后序

题目

⽤栈的形式给出⼀棵⼆叉树的建⽴的顺序，求这棵⼆叉树的后序遍历

分析与注意点

栈实现的是⼆叉树的中序遍历（左根右），⽽每次push⼊值的顺序是⼆叉树的前序遍历（根左右），所以这里其实是根据先序和中序求后序的题，只需要根据输入对栈的操作进行模拟：
- push的东西一个个放入先序遍历数组；
- pop前获取栈顶元素放入中序遍历数组
若结点个数为 $n$，则就有 $2n$ 个操作；
调用create创建二叉树，最后返回根结点指针，再后序遍历
构建方法和上题类似

代码

#include <bits/stdc++.h>
using namespace std;
int n, num = 0;
vector<int> preOrder, inOrder;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
};

TreeNode* create(int preL, int preR, int inL, int inR) {
  if (preL > preR)  return NULL;
  TreeNode* root = new TreeNode;
  root -> val = preOrder[preL];
  int k;
  for (k = inL; k <= inR; k++)
    if (inOrder[k] == preOrder[preL])
      break;
  int numLeft = k - inL;
  root -> left = create(preL + 1, preL + numLeft, inL, k - 1);
  root -> right = create(preL + numLeft + 1, preR, k + 1, inR);
  return root;
}

void postTraversal(TreeNode* root) {
  if (!root)  return;
  postTraversal(root -> left);
  postTraversal(root -> right);
  cout << root ->val;
  num++;
  if (num < n)  cout << " ";
  return;
}

int main() {
  stack<int> stk;
  cin >> n;
  for (int i = 0; i < n * 2; i++) {
    string s;
    int temp;
    cin >> s;
    if (s == "Push") {
      cin >> temp;
      preOrder.push_back(temp);
      stk.push(temp);
    } else {
      temp = stk.top();
      stk.pop();
      inOrder.push_back(temp);
    }
  }
  TreeNode* root = create(0, n-1, 0, n-1);
  postTraversal(root);
  return 0;
}

[1102] Invert a Binary Tree

⼆叉树的遍历，先序中序转后序

题目

反转⼀棵⼆叉树，给出原⼆叉树的每个结点的左右孩⼦，输出它的层序和中序遍历

分析与注意点

代码

#include <bits/stdc++.h>
using namespace std;
int n;
map<int, pair<int, int>> mp;
vector<bool> isRoot;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
};

void insert(TreeNode* &root) {
  if (mp[root->val].first < 0 && mp[root->val].second < 0)
    return;
  if (mp[root->val].first >= 0) {
    TreeNode* l = new TreeNode;
    l -> val = mp[root->val].first;
    root -> left = l;
    insert(root -> left);
  }
  else  root -> left = NULL;
  if (mp[root->val].second >= 0) {
    TreeNode* r = new TreeNode;
    r -> val = mp[root->val].second;
    root -> right = r;
    insert(root -> right);
  }
  else  root -> right = NULL;
  return;
}

void levelTraversal(TreeNode* root) {
  if (!root)  return;
  queue<TreeNode*> q;
  q.push(root);
  int num = 0;
  while(!q.empty()) {
    TreeNode* cur = q.front();
    q.pop();
    cout << cur -> val;
    num++;
    if (num < n)  cout << " ";
    if (cur -> left)  q.push(cur -> left);
    if (cur -> right)  q.push(cur -> right);
  }
  cout << endl;
  return;
}

int num = 0;
void inOrderTraversal(TreeNode* root) {
  if (!root)  return;
  inOrderTraversal(root -> left);
  cout << root -> val;
  num++;
  if (num < n)  cout << " ";
  inOrderTraversal(root -> right);
  return;
}

int main() {
  cin >> n;
  isRoot.resize(n, true);
  for (int i = 0; i < n; i++) {
    char s1, s2;
    cin >> s1 >> s2;
    int a, b;
    if (s1 == '-')  a = -1;
    else  a = s1 - '0';
    if (s2 == '-')  b = -1;
    else  b = s2 - '0';
    if (a != -1)  isRoot[a] = false;
    if (b != -1)  isRoot[b] = false;
    mp[i] = make_pair(b, a);
  }
  int i;
  for (i = 0; i < n; i++)
    if (isRoot[i])  break;
  TreeNode* root = new TreeNode;
  root -> val = i;
  insert(root);
  levelTraversal(root);
  inOrderTraversal(root);
  return 0;
}

树的遍历

[1053] Path of Equal Weight

树的遍历

题目

给出树的结构和权值，找从根结点到叶⼦结点的路径上的权值相加之和等于给定⽬标数的路径，并且从⼤到⼩输出路径

分析与注意点

对于接收孩⼦结点的数据时，每次完全接收完就对孩⼦结点按照权值进⾏排序（序号变，根据权值变），这样保证深度优先遍历的时候直接输出就能输出从⼤到⼩的顺序。

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, s;
vector<int> temp;
vector<vector<int>> ans;

struct TreeNode {
  int weight;
  vector<int> child;
} treeNode[110];

void dfs(int index, int sum) {
  if (sum == s && !treeNode[index].child.size()) {
    ans.push_back(temp);
    return;
  }
  if (index >= n || !treeNode[index].child.size())  return;
  for (int i = 0; i < treeNode[index].child.size(); i++) {
    int curW = treeNode[treeNode[index].child[i]].weight;
    int curSum = sum + curW;
    if (curSum <= s) {
      temp.push_back(curW);
      dfs(treeNode[index].child[i], curSum);
      temp.pop_back();
    }
  }
  return;
}

int main() {
  cin >> n >> m >> s;
  for (int i = 0; i < n; i++)
    cin >> treeNode[i].weight;
  for (int i = 0; i < m; i++) {
    int cur, num, k;
    scanf("%d %d", &cur, &num);
    for (int j = 0; j < num; j++) {
      scanf("%d", &k);
      treeNode[cur].child.push_back(k);
    }
    sort(treeNode[cur].child.begin(), treeNode[cur].child.end(), [&](int a, int b) {
      return treeNode[a].weight > treeNode[b].weight;
    });
  }
  temp.push_back(treeNode[0].weight);
  dfs(0, treeNode[0].weight);

  for (int i = 0; i < ans.size(); i++) {
    for (int j = 0; j < ans[i].size(); j++) {
      cout << ans[i][j];
      if (j != ans[i].size() - 1)
        cout << " ";
    }
    if (i != ans.size() - 1)
      cout << endl;
  }
  return 0;
}

[1004] Counting Leaves

DFS，树的遍历

题目

给出⼀棵树，问每⼀层各有多少个叶⼦结点

分析与注意点

简单的，考前稍微康康

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, d = -1;
vector<int> ans;
vector<vector<int>> node;

void dfs(int index, int depth) {
  if (!node[index].size()) {
    ans[depth]++;
    d = max(d, depth);
  }
  for(int i = 0; i < node[index].size(); i++)
    dfs(node[index][i], depth + 1);
  return;
}

int main() {
  cin >> n >> m;
  node.resize(n + 1);
  ans.resize(n, 0);
  for (int i = 0; i < m; i++) {
    int cur, num, k;
    scanf("%d %d", &cur, &num);
    for (int j = 0; j < num; j++) {
      scanf("%d", &k);
      node[cur].push_back(k);
    }
  }
  dfs(1, 0);
  for (int i = 0; i <= d; i++) {
    cout << ans[i];
    if (i != d)  cout << " ";
  }
}

[1079] Total Sales of Supply Chain

DFS，树的遍历

题目

给⼀棵树，在树根出货物的价格为p，然后从根结点开始每往下⾛⼀层，该层的货物价格将会在⽗亲结点的价格上增加r%，给出每个叶结点的货物量，求他们的价格之和

分析与注意点

简单的，考前稍微康康

代码

#include <bits/stdc++.h>
using namespace std;
int n;
double p, r, prices;

struct TreeNode {
  vector<int> child;
  int sales;
};
vector<TreeNode> chain;

void dfs(int index, int depth) {
  if (!chain[index].child.size()) {
    // cout << index << " " << depth << " " << chain[index].sales << endl;
    prices +=  pow(1+r, depth) * chain[index].sales * p;
    return;
  }
  for (int i = 0; i < chain[index].child.size(); i++) {
    dfs(chain[index].child[i], depth + 1);
  }
  return;
}

int main() {
  scanf("%d %lf %lf", &n, &p, &r);
  r /= 100;
  chain.resize(n);
  for (int i = 0; i < n; i++) {
    int num, k;
    cin >> num;
    if (num) {
      for (int j = 0; j < num; j++) {
        cin >> k;
        chain[i].child.push_back(k);
        chain[i].sales = -1;
      }
    } else {
      cin >> k;
      chain[i].sales = k;
    }
  }
  dfs(0, 0);
  printf("%.1f", prices);
  return 0;
}

[1090] Highest Price in Supply Chain

DFS，树的层序遍历

题目

给⼀棵树，在树根处货物的价格为p，然后每往下⾛⼀层，价格增加r%，求所有叶⼦结点的最⾼价格，以及这个价格的叶⼦结点个数。

分析与注意点

简单的，考前稍微康康

代码

#include <bits/stdc++.h>
using namespace std;
int n, root;
double p, r;
pair<double, int> ans = {0.0, 0};
vector<vector<int>> node;

void dfs(int index, int depth) {
  if (node[index].size() == 0) {
    double price = pow(1+r, depth) * p;
    if (price > ans.first) {
      ans.first = price;
      ans.second = 1;
    } else if (price == ans.first) {
      ans.second++;
    }
    return;
  }
  for (int i = 0; i < node[index].size(); i++) {
    dfs(node[index][i], depth + 1);
  }
  return;
}

int main() {
  scanf("%d %lf %lf", &n, &p, &r);
  r /= 100;
  node.resize(n);
  for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    if (k != -1)  node[k].push_back(i);
    else  root = i;
  }
  dfs(root, 0);
  printf("%.2f %d", ans.first, ans.second);
  return 0;
}

[1106] Lowest Price in Supply Chain

DFS，树的遍历

题目

提供⼀棵树，在树根处货物的价格为p，从根结点开始每往下⼀层，该层货物价格将会在⽗亲结点的价格上增加r%。求叶⼦结点出能获得的最低价格以及能提供最低价格的叶⼦结点数

分析与注意点

简单的，考前稍微康康

代码

#include <bits/stdc++.h>
using namespace std;
int n;
double p, r;
pair<double, int> ans = {INT_MAX, 0};
vector<vector<int>> node;

void dfs(int index, int depth) {
  if (!node[index].size()) {
    double price = pow(1+r, depth) * p;
    if (price < ans.first) {
      ans.first = price;
      ans.second = 1;
    } else if (price == ans.first) {
      ans.second++;
    }
    return;
  }
  for (int i = 0; i < node[index].size(); i++) {
    dfs(node[index][i], depth + 1);
  }
  return;
}

int main() {
  scanf("%d %lf %lf", &n, &p, &r);
  r /= 100;
  node.resize(n);
  for (int i = 0; i < n; i++) {
    int num, k;
    cin >> num;
    if (!num)  continue;
    for (int j = 0; j < num; j++) {
      cin >> k;
      node[i].push_back(k);
    }
  }
  dfs(0, 0);
  printf("%.4f %d", ans.first, ans.second);
  return 0;
}

[1094] The Largest Generation

DFS，树的遍历

题目

输⼊树的结点个数N，结点编号为1~N，⾮叶⼦结点个数M，然后输出M个⾮叶⼦结点格⼦的孩⼦结点的编号，求结点个数最多的⼀层，根结点的层号为1，输出该层的结点个数以及层号

分析与注意点

简单的，考前稍微康康

代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
pair<int, int> ans = {-1, -1};
vector<int> level;
vector<vector<int>> node;

void dfs(int index, int depth) {
  level[depth]++;
  if (level[depth] > ans.first) {
    ans.first = level[depth];
    ans.second = depth;
  }
  if (!node[index].size())  return;
  for (int i = 0; i < node[index].size(); i++)
    dfs(node[index][i], depth + 1);
  return;
}

int main() {
  cin >> n >> m;
  node.resize(n + 1);
  level.resize(m + 1);
  vector<bool> isRoot(n + 1, true);
  isRoot[0] = false;
  for (int i = 0;i < m; i++) {
    int num, k, cur;
    scanf("%d %d", &num, &k);
    for (int j = 0; j < k; j++) {
      scanf("%d", &cur);
      node[num].push_back(cur);
      isRoot[cur] = false;
    }
  }
  int i;
  for (i = 0; i <= n; i++)
    if (isRoot[i])  break;
  dfs(i, 1);
  cout << ans.first << " " << ans.second;
  return 0;
}

二叉搜索树

[1043] Is It a Binary Search Tree

⼆叉搜索树BST

题目

给出N个正整数来作为一棵二叉排序树的结点插入顺序，问这串序列是否是该二叉排序树的先序序列或是该二叉排序树的镜像树的先序序列。所谓镜像树是指交换二叉树的所有结点的左右子树而形成的树（也即左子树所有结点数据域大于或等于根结点，而根结点数据域小于右子树所有结点的数据域）。如果是，则输出“YES”，并输出对应的树的后序序列;否则，输出“NO”

分析与注意点

简单的，考前稍微康康

代码

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> node, pre, preMirror, post, postMirror;

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
};

void insert(TreeNode*& root, int x) {
  if (!root) {
    root = new TreeNode;
    root -> val = x;
    root -> left = root -> right = NULL;
    return;
  }
  if (x >= root -> val)  insert(root -> right, x);
  else  insert(root -> left, x);
}

void preOrderTraversal(TreeNode* root) {
  if (!root)  return;
  pre.push_back(root -> val);
  preOrderTraversal(root -> left);
  preOrderTraversal(root -> right);
}

void preMirrorTraversal(TreeNode* root) {
  if (!root)  return;
  preMirror.push_back(root -> val);
  preMirrorTraversal(root -> right);
  preMirrorTraversal(root -> left);
}

void postTraversal(TreeNode* root) {
  if (!root)  return;
  postTraversal(root -> left);
  postTraversal(root -> right);
  post.push_back(root -> val);
}

void postMirrorTraversal(TreeNode* root) {
  if (!root)  return;
  postMirrorTraversal(root -> right);
  postMirrorTraversal(root -> left);
  postMirror.push_back(root -> val);
}

int main() {
  cin >> n;
  TreeNode* root = NULL;
  for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    node.push_back(k);
    insert(root, k);
  }
  preOrderTraversal(root);
  preMirrorTraversal(root);
  if (pre == node) {
    postTraversal(root);
    cout << "YES" << endl;
    for (int i = 0; i < post.size(); i++) {
      cout << post[i];
      if (i != post.size() - 1)
        cout << " ";
    }
  } else if (preMirror == node) {
    postMirrorTraversal(root);
    cout << "YES" << endl;
    for (int i = 0; i < postMirror.size(); i++) {
      cout << postMirror[i];
      if (i != postMirror.size() - 1)
        cout << " ";
    }
  } else {
    cout << "NO";
  }
  return 0;
}

[1064] Complete Binary Search Tree

⼆叉搜索树BST

题目

给⼀串构成树的序列，已知该树是完全⼆叉搜索树，求它的层序遍历的序列

分析与注意点

完全二叉树：除了最下面一层之外，其余层的结点个数都达到了当层能达到的最大结点数，且最下面一层只从左至右连续存在若干结点，而这些结点右边的结点全部不存在。
因为⼆叉搜索树的中序是⼀组序列的从⼩到⼤排列，所以只需将所给序列排序即可得到中序数组 node；
假设把树按从左到右、从上到下的顺序依次编号，根节点为1，则从根结点$root = 1$开始中序遍历， root结点的左孩⼦下标是 $root * 2$，右孩⼦下标是 $root * 2 + 1$，通过这个下标规则计算出左右结点在 cbt 数组中的位置下标；
因为是中序遍历，所以遍历结果与中序数组 node 中的值从1开始依次递增的结果相同，那么只需要一个id 来得到当前结点的权值，即 node[id++]（id从1开始），最后将node[id++] 赋值给 cbt[x] 数组

代码

#include <bits/stdc++.h>
using namespace std;
int n, idx = 0;
vector<int> node, cbt;

// 二叉排序树的中序遍历是递增的，按顺序赋值给cbt
void inOrderTraversal(int x) {
  if (x > n)  return;
  inOrderTraversal(x * 2);  // 左子树
  cbt[x] = node[idx++];
  inOrderTraversal(x * 2 + 1);  // 右子树
}

int main() {
  cin >> n;
  cbt.resize(n + 1);
  for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    node.push_back(k);
  }
  sort(node.begin(), node.end());
  inOrderTraversal(1);  // 编号从1开始，如果从0开始则左子树是(x*2+1)，右子树是(x*2+2)
  // cbt数组按顺序输出就是其层序遍历
  for (int i = 1; i <= n; i++) {
    cout << cbt[i];
    if (i < n)  cout << " ";
  }
  return 0;
}

[1099] Build A Binary Search Tree

⼆叉搜索树BST

题目

二叉树有 $N$ 个结点（结点编号为 $0$ ~ $N-1$），给出每个结点的左右孩子结点的编号（不存在用-1表示）。接着给出一个个整数的序列，需要把这个整数填入二叉树的结点中，使得二叉树成为一棵二叉查找树。输出这棵二叉查找树的层序遍历序列。

1099

分析与注意点

还是利用二叉搜索树中序遍历是递增的这个特性，将输入的序列直接进行排序就得到了中序遍历的结果。先根据输入得到的结果建立树的结构；然后和上题一样，进行一次中序遍历，这次在中序遍历的时候将得到的权值填入 root->val。

代码

#include <bits/stdc++.h>
using namespace std;
int n, idx = 0;
vector<int> node;
unordered_map<int, pair<int, int>> mp;

struct TreeNode {
  int order;
  int val;
  TreeNode* left;
  TreeNode* right;
};

void insert(TreeNode* &root) {
  if (mp[root->order].first >= 0) {
    TreeNode* l = new TreeNode;
    l -> order = mp[root->order].first;
    root -> left = l;
    insert(root -> left);
  } else {
    root -> left = NULL;
  }
  if (mp[root->order].second >= 0) {
    TreeNode* r = new TreeNode;
    r -> order = mp[root->order].second;
    root -> right = r;
    insert(root -> right);
  } else {
    root -> right = NULL;
  }
  return;
}

void inOrderTraversal(TreeNode* root) {
  if (!root)  return;
  inOrderTraversal(root -> left);
  root -> val = node[idx++];
  inOrderTraversal(root -> right);
}

void levelTraversal(TreeNode* root) {
  if (!root)  return;
  queue<TreeNode*> q;
  q.push(root);
  int num = 0;
  while(!q.empty()) {
    TreeNode* cur = q.front();
    q.pop();
    cout << cur -> val;
    num++;
    if (num < n)  cout << " ";
    if (cur -> left)  q.push(cur -> left);
    if (cur -> right)  q.push(cur -> right);
  }
  return;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    int a,b;
    cin >> a >> b;
    mp[i] = make_pair(a, b);
  }
  for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    node.push_back(k);
  }
  sort(node.begin(), node.end());
  TreeNode* root = new TreeNode;
  root -> order = 0;
  insert(root);
  inOrderTraversal(root);
  levelTraversal(root);
  return 0;
}

AVL树

AVL树仍是一颗二叉查找树，但对AVL树来说，其左子树和右子树的高度之差的绝对值不超过1，其中左子树和右子树的高度只差称为该结点的平衡因子。
因为需要对每个结点都得到平衡因子，因此需要在树的结构中加入一个变量height来记录以当前结点为根结点的子树的高度。子树的高度就是左子树与右子树高度较大的值加上1，

查找操作

和二叉查找树的查找是一样的。

void search(Node *root, int x) {
  if (!root) {
    cout << "fail";
    return;
  }
  if (x == root -> val)
    cout << root -> val;
  else if (root -> val >= x)
    search(root -> left, x);
  else
    search(root -> right, x);
}

插入操作

左旋

步骤如下：

让B的左子树成为A的右子树；
让A成为B的左子树；
将根结点设置为B。

l_rotate

代码如下

void l_rotation(TreeNode* &root) {
  TreeNode* temp = root -> right;
  root -> right = temp -> left;
  temp -> left = root;
  updateHeight(root);
  updateHeight(temp);
  root = temp;
  return;
}

右旋

步骤如下：

让A的右子树成为B的左子树；
让B成为A的右子树；
将根结点设置为A。

r_rotate

代码如下

void r_rotation(TreeNode* &root) {
  TreeNode* temp = root -> left;
  root -> left = temp -> right;
  temp -> right = root;
  updateHeight(root);
  updateHeight(temp);
  root = temp;
  return;
}

插入调整

table

void insert(TreeNode* &root, int k) {
  if (root == NULL) {
    root = newNode(k);
    return;
  }
  if (k < root -> val) {
    insert(root -> left, k);
    updateHeight(root);
    if (getBalanceFactor(root) == 2) {
      if (getBalanceFactor(root -> left) == 1)  // LL
        r_rotation(root);
      else if (getBalanceFactor(root -> left) == -1) {  // LR
        l_rotation(root -> left);
        r_rotation(root);
      }
    }
  } else {
    insert(root -> right, k);
    updateHeight(root);
    if (getBalanceFactor(root) == -2) {
      if (getBalanceFactor(root -> right) == -1)  // RR
        l_rotation(root);
      else if (getBalanceFactor(root -> right) == 1) {  // RL
        r_rotation(root -> right);
        l_rotation(root);
      }
    }
  }
  return;
}

Next Post

Z-Order
Previous Post

Greenplum操作遇到的问题记录

CATALOG

1. 二叉树的遍历
2. 树的遍历
3. 二叉搜索树
4. AVL树
1. 4.1. 查找操作
2. 4.2. 插入操作