Aczy156

Algorithm11.4 数据结构 树 二叉树 性质 建树 前中后序遍历

[TOC]

数据结构 树 二叉树 性质 建树、前中后序遍历

树相关

遍历操作：

  • 【递归】先根遍历、后根遍历。看所有儿子节点和根节点的遍历顺序
  • 【非递归】也是用队列先进先出作为数据结构来存

二叉树相关

两种实现方式：（基本的树结构是两种，如果转换为图进行储存也是可以的）

  • 「顺序表」结构体数组实现

  • 「链接表」二叉链表实现

  • 拓展方法：通过图方式进行存储

树结构性质：

  • 对于各种二叉树都有的性质：各种类型的节点个数之间的关系

    • 叶子结点个数=度为2的节点个数+1（推导：连线个数=2*n2+1*n1+0*n0，节点个数=n2+n1+n0，连线个数+1=节点个数 => n2+1 = n0）

  • 对于完全二叉树：高度相关，pow(2, k-1) < n < pow(2, k)，这样可以反推出k的范围。

遍历操作：

  • 基本的三种前中后序「主要根据碰到根节点的三个时机，分出了前中后序遍历」
    • 【递归实现】
    • 【非递归实现】通过 栈 模拟函数调用栈先进后出 来 模拟 递归前中后序遍历
  • 【非递归】层次遍历：通过维护一个先进先出

遍历性质：

  • 前序 中序 后序 dfs序 相关性质
  • 给出两个，推第三个
    • 给出前+后【不带中】 => 中序不一定唯一
    • 给出中+前【带中】 => 后序唯一
    • 给出中+后【带中】 => 前序唯一

树与二叉树之间转换

兄弟节点法，把当前节点的同层的右边节点按次顺到右儿子，一直这样下去。

转换回去，通过把右节点往上一直连接

二叉链表实现 - 利用链表来链接起树的结构

1、节点中有两个指向叶子结点的指针。

struct node(){
  int data;
  node * lchild;
  node * rchild;
  node(){}
  node(int data): data(data){}
  node(int data, node * lchild, node * rchild): data(data), lchild(lchild), rchild(rchild){}
}

2、要给出的数据，是一串字符串，然后通过递归建树的过程中，逐渐输入scanf进去

例如：

// 两组测试用例
// A B D # # E # # C F # # G # #
// 1 2 4 # # 5 # # 3 6 # # 7 # #

// A B C # # D E # G # # F # # #
// 1 2 3 # # 4 5 # 6 # # 7 # # #

3、思路：由于是二叉链表，实质上是指针指向的，所以就写一个递归的返回指针的函数。

node * build() {
  char ch;
  cin>>ch;
  if (ch == '#') return NULL;
  else {
    // 声明出当前指向结构体的指针
    node * n = (node*)malloc(sizeof(node));
    n->data = ch-'0';
    n->lchild = build();
    n->rchild = build();
  }
}

// main函数里 => 先创建一个指向根节点的指针，然后就可以开始给这个指针build了
node * tree = (node*)malloc(sizeof(node));
tree = build();

4、前周后序遍历，都只需要将指向根节点的指针传入即可。

#include <iostream>
using namespace std;
struct node {
    int data;
    // 指向左右子叶
    node * lchild;
    node * rchild;
    // 构造函数
    node(){}
    node(int data): data(data){}
    node(int data, node * lchild, node * rchild): data(data), lchild(lchild), rchild(rchild){}
};
#include <queue>

// 构造二叉树
char ch;
node * build(){
    cin>>ch;
    if (ch == '#') return NULL;
    else {
        node * n = (node*)malloc(sizeof(node));
        n->data = ch-'0';
        n->lchild = build();
        n->rchild = build();
        return n;
    }
}

// 前序遍历
void pre_traverse(node * n) {
    cout<<n->data<<" ";
    if (n->lchild) pre_traverse(n->lchild);
    if (n->rchild) pre_traverse(n->rchild);
}

// 中序遍历
void in_traverse(node * n) {
    if (n->lchild) in_traverse(n->lchild);
    cout<<n->data<<" ";
    if (n->rchild) in_traverse(n->rchild);
}

// 后序遍历
void post_traverse(node * n) {
    if (n->lchild) post_traverse(n->lchild);
    if (n->rchild) post_traverse(n->rchild);
    cout<<n->data<<" ";
}

// 非递归遍历
int cnt_node, cnt_1, cnt_2, cnt_leaf, val_min=INT_MAX, val_max;
queue<node*> q1;
void non_recursive_traverse(node * n) {
    q1.push(n);
    while (!q1.empty()) {
        node * nw = q1.front();q1.pop();
        cnt_node++;
        val_min = min(val_min, nw->data); val_max = max(val_max, nw->data);
        if (nw->lchild && nw->rchild) cnt_2++;
        else if (nw->lchild==NULL && nw->rchild==NULL) cnt_leaf++;
        else cnt_1++;
        if (nw->lchild) q1.push(nw->lchild);
        if (nw->rchild) q1.push(nw->rchild);
    }
}

// 选做内容：bfs 层次遍历
queue<node*> q2;
void bfs(node * n) {
    q2.push(n);
    while (!q2.empty()) {
        node * nw = q2.front();q2.pop();
        cout<<nw->data<<" ";
        if (nw->lchild) q2.push(nw->lchild);
        if (nw->rchild) q2.push(nw->rchild);
    }
}

int main() {
    node * tree = (node*)malloc(sizeof(node));
    // 建树
    tree = build();
    // 前中后序遍历
    cout<<"前序遍历: "; pre_traverse(tree);
    cout<<endl<<"中序遍历: "; in_traverse(tree);
    cout<<endl<<"后序遍历: "; post_traverse(tree);
    // 非递归遍历
    cout<<endl<<"非递归遍历: "; non_recursive_traverse(tree);
    cout<<"节点个数:"<<cnt_node<<"  度为1的节点个数:"<<cnt_1<<"  度为2的节点个数:"<<cnt_2<<"  叶子节点个数:"<<cnt_leaf<<endl<<"最大值:"<<val_max<<"  最小值:"<<val_min;
    // bfs
    cout<<endl<<"层次遍历(bfs): "; bfs(tree); cout<<endl;
    return 0;
}

二叉树建树 - 节点值做索引表示

https://www.luogu.com.cn/problem/P1305

1、节点值做索引的数据结构

结构体中不需要当前节点的值，因为这个节点的值已经在做数据结构的索引了

struct node {
  int left, right;
}tree[maxnode];

要求给出的数据（节点的顺序必须为对应的，不然这样匹配是有问题的）

// 读入字符串abc，得到a为根节点，bc分别为两个子节点 (注意读取单个字符的时候，要给空格来冲刷掉回车的影响)
scanf(" %c", &ch);
scanf(" %c%c", &tree[ch].left, &tree[ch].right);

2、前中后序的遍历

  • 前：根->左->右
  • 中：左->根->右
  • 后：右->根->左
void front_traverse(char ch) {
  printf("%c", ch);
  if (当前节点的左儿子不是空) front_traverse(tree[ch].left);
  if (当前节点的右儿子不是空) front_traverse(tree[ch].right);
}
void mid_traverse(char ch) {
  if (当前节点的左儿子不是空) mid_traverse(tree[ch].left);
  printf("%c", ch);
  if (当前节点的右儿子不是空) mid_traverse(tree[ch].right);
}
void back_traverse(char ch) {
  if (当前节点的左儿子不是空) back_traverse(tree[ch].left);
  if (当前节点的右儿子不是空) back_traverse(tree[ch].right);
  printf("%c", ch);
}

AC代码：

#include <iostream>
using namespace std;
int n;
struct node {
    char left, right;
}tree[1000];
char ch, root;

void front_traverse(char ch) {
    // front traverse => root, left, right
    printf("%c", ch);
    if (tree[ch].left != '*') front_traverse(tree[ch].left);
    if (tree[ch].right != '*') front_traverse(tree[ch].right);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf(" %c", &ch);
        if (i == 1) root = ch;
        scanf(" %c%c", &tree[ch].left, &tree[ch].right);
    }
    front_traverse(root);
    return 0;
}

二叉树 - 节点值做索引 搜索深度

https://www.luogu.com.cn/problem/P4913

1、遍历的过程中就筛选出最大的深度，通过维护一个ans来提取。

第一种，通过在dfs深搜到儿子节点之前来判断是否要搜他。

void dfs(int val, int depth) {
  ans = max(ans, depth);
  if (!tree[val].left) dfs(tree[val].left, depth+1);
  if (!tree[val].right) dfs(tree[val].right, depth+1);
}

第二种，通过在搜到之后，判断这个搜到的点是否符合搜的要求。

void dfs(int val, int depth) {
  if (!val) return;
  ans = max(ans, depth);
  dfs(tree[val].left, depth+1);
  dfs(tree[val].right, depth+1);
}

AC代码：

#include <iostream>
using namespace std;
#define maxnode 1000010
struct node{
    int left, right;
}tree[maxnode];
int n, ans;

void dfs(int val, int depth) {
    ans = max(ans, depth);
    if (tree[val].left) dfs(tree[val].left, depth+1);
    if (tree[val].right) dfs(tree[val].right, depth+1);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d%d", &tree[i].left, &tree[i].right);
    dfs(1, 1);
    printf("%d\n", ans);
    return 0;
}

二叉树的前序 中序 后序 dfs序等性质 // 【给出前后，求中序】

https://www.luogu.com.cn/problem/P1229

题目：给出前序后序，不给中序，求这棵树有多少种形态。【中序有多少种】

分析：前序：根左右，中序：左根右，后序：左右根

性质：一个树有多少种形态，取决于儿子节点只有1个的节点的个数。【形态数 = pow(2, 儿子节点为1的节点个数)】

  • 如果一棵树没有只有一个儿子节点的节点=》也就是是一个完满二叉树，只要有儿子节点，就是两个，要不就没有儿子节点。
    • 此时树形态已经被确定了，例如前序abc后序bca，那这就是一个a->(b,c)的完满二叉树，在例如前序abdecfg后序debfgca，那就是一个a->(b->(d,e), c->(f,g))的完满二叉树
  • 如果一个棵树的节点都只有一个儿子节点=》和一根线一样，就例如如果就是abc往下排列的一根线，那么可以计算得到两个节点满足只有一个儿子节点，那么总共有4种，分别为左左，左右，右左，右右。
#include <iostream>
using namespace std;
string pre, post;
int ans;

int main() {
    cin>>pre>>post;
    for (int i = 0; i < pre.length()-1; ++i)
        for (int j = 0; j < post.length()-1; ++j)
            if (pre[i] == post[j+1] && post[j] == pre[i+1]) ans++;
        printf("%d\n", 1<<ans);
    return 0;
}

二叉树的前序 中序 后序 dfs序等性质 // 【给出中序+前后中的一个，求另一个】

https://www.luogu.com.cn/problem/P1030 该题是由中序+后序求前序

https://www.luogu.com.cn/problem/P1827 该题是由中序+前序求后序

思路：首先明确前：根左右 中：左根右 后：左右根

然后整体思路就是通过前或者后的根在一边的特性，直接从对应的一段提取出根，然后再在中序中找到根，根左边的就是左子树，根右边的就是右子树，然后再递归两颗子树即可。

#include <iostream>
using namespace std;
string pre, in, post;

void transform_pre(string i, string p) {
    if (i.length() > 0) {
        char root = p[p.length() - 1];
        cout << root;
        int pos = i.find(root);
        transform_pre(i.substr(0, pos), p.substr(0, pos));
        transform_pre(i.substr(pos + 1), p.substr(pos, i.size() - pos - 1));
    }
}

void transform_post(string pr, string i) {
    if (i.length() > 0) {
        char root = pr[0];
        int pos = i.find(root);
        transform_post(pr.substr(1, pos), i.substr(0, pos));
        transform_post(pr.substr(pos + 1), i.substr(pos + 1));
        cout << root;
    }
}

int main() {
//    cin >> in >> post;
//    transform_pre(in, post);
    cin >> in >> pre;
    transform_post(pre, in);
    return 0;
}



//1 2 3 4 5 6 7
//中序遍历: 3256471
//后序遍历: 3657421

//1 2 4 5 3 6 7
//中序遍历: 4251637
//后序遍历: 4526731

// 1245367 4251637 4526731
Posted on Feb 1, 2021