树的定义及其相关概念
树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合
树型结构在现实世界中广泛存在，比如组织关系图。
树型结构在计算机领域中也有广泛应用，如在编译系统中，用树表示源程序的语法结构。
在数据库系统中，树型结构是数据库层次模型的基础，也是各种索引和目录的主要组织形式。
在许多算法中，经常用树型结构描述问题的求解过程、所有解的状态和求解对策。
在树型结构中，二叉树是最常用的结构，分治个数确定，又可以为空，有良好的递归特性，特别适宜于程序设计。一般树会转换成二叉树进行处理。
树的父亲表示法，数组
// 优缺点：利用了树中除根结点外每个结点都有唯一的父结点这个性质// 很容易找到树根，但找孩子时需要遍历整个线性表struct node{int data, parent;}tree[110];
二叉树的定义及其基本性质
二叉树（Binary Tree, BT）是一种特殊的树型结构，每个结点最多有两个子节点。
5种基本形态
- 空二叉树
- 仅有根结点的二叉树
- 右子树为空的二叉树
- 左右子树均非空的二叉树
-
性质
在二叉树的第 i 层上最多有
个结点- 深度为 depth 的二叉树，至多有
个结点 - 对任意一棵二叉树，如果叶子结点数为
，度为 2 的结点数为
，一定满足
证明：
，算两次
- 具有 n 个结点的完全二叉树，深度为
。注意，根的深度，有的定义是0，有的定义是1 - 对于一棵具有 n 个结点的完全二叉树，对于任意一个结点，编号为 i
if (i > 1) 父结点编号 i / 2
if (2 i > n) 没有左儿子 else 左儿子编号为 2 i
if (2 i + 1 > n) 没有右儿子 else 右儿子编号为 2 i + 1
Catalan数
- 具有 n 个结点的不同形态的二叉树，有多少棵 ```cpp 一棵具有 n(n > 1) 个结点的二叉树
可以看成是, 由 一个根结点， 一棵具有 i 个结点的左子树， 一棵具有 n - i - 1个结点的右子树组成
i 的取值范围[0, n - 1]
<br /><br /><br /><a name="UkfY1"></a># 二叉树的孩子表示法，链式存储结构+顺序存储结构```cpp// 链式存储结构struct node{int data;node *lchild, *rchild; //左儿子，右儿子};node *root;// 顺序存储结构const int N = 110;int data[N]；int lchild[N], rchild[N]; // int child[N][2]; 也可以这样写int root;
https://www.cnblogs.com/tarbitrary/p/4030652.html
二叉树的遍历：前序、中序、后序遍历，递归
性质：
- 已知先序和中序，可以确定出二叉树
- 已知中序和后序，可以确定出二叉树
- 已知先序和后序，不可以确定出二叉树
// 链式存储结构#include <bits/stdc++.h>using namespace std;struct node{char data;node *lchild, *rchild;};node *root;// 按先序输入二叉树的结点，输入$表示空树void build(node* &p){char c;scanf("%c", &c);if (c == '$') p = NULL;else{p = new node();p->data = c;build(p->lchild); build(p->rchild);}}void pre_order(node *p){if (p == NULL) return;if (p->data != '$') cout << p->data;pre_order(p->lchild);pre_order(p->rchild);}void in_order(node *p){if (p == NULL) return;in_order(p->lchild);if (p->data != '$') cout << p->data;in_order(p->rchild);}void post_order(node *p){if (p == NULL) return;post_order(p->lchild);post_order(p->rchild);if (p->data != '$') cout << p->data;}int main(){build(root);pre_order(root);puts("");in_order(root);puts("");post_order(root);puts("");return 0;}/*输入：AB$$C$$输出：ABCBACBCA*/
表达式树
二叉树是表达式处理的常用工具。例如，表达式
a+b*(c-d)-e/f
其中，每个非叶子结点表示一个运算符，左子树是第一个运算数对应的表达式，而右子树则是第二个运算数对应的表达式。如何给一个表达式简历表达式树呢？方法有很多，这里只介绍一种：找到“最后计算”的运算符（它是整颗表达式树的根），然后递归处理。
#include <bits/stdc++.h>using namespace std;const int N = 1010;int lch[N], rch[N], idx, root;char op[N], s[N];int build_tree(char *s, int x, int y){int c1 = -1, c2 = -1, p = 0;int u;if (y - x == 1){ // 只有一个字符了u = ++idx;lch[u] = rch[u] = -1;op[u] = s[x];return u;}for (int i = x; i < y; i++){if (s[i] == '(') p++;if (s[i] == ')') p--;if (s[i] == '+' || s[i] == '-')if (!p) c1 = i;if (s[i] == '*' || s[i] == '/')if (!p) c2 = i;}// 找不到括号外的加减，就用乘除if (c1 < 0) c1 = c2;// 整个表达式被一对括号括起来，往里缩一位if (c1 < 0) return build_tree(s, x + 1, y - 1);u = ++idx;lch[u] = build_tree(s, x, c1);rch[u] = build_tree(s, c1 + 1, y);op[u] = s[c1];return u;}void in_order(int u){if (lch[u] == -1 && rch[u] == -1){cout << op[u];return ;}in_order(lch[u]);cout << op[u];in_order(rch[u]);}void pre_order(int u){if (lch[u] == -1 && rch[u] == -1){cout << op[u];return ;}cout << op[u];pre_order(lch[u]);pre_order(rch[u]);}int main(){scanf("%s", s);root = build_tree(s, 0, strlen(s));in_order(root);puts("");pre_order(root);return 0;}/*a+b*(c-d)-e/f*/
上述代码是如何寻找“最后一个运算符”的呢？代码用了一个变量p，只有当p=0时才考虑这个运算符。为什么呢？因为括号里的运算符一定不是最后计算的，应当忽略。例如，(a+b)*c中虽然有一个加号，但却是在括号里的，实际上比它优先级高的乘号才是最后计算的。由于加减和乘除号都是左结合的，最后一个运算符才是最后计算的，所以用两个变量c1和c2分别记录“最右”出现的加减号和乘除号。
再接下来的代码就不难理解了：如果括号外有加减号，它们肯定最后计算；但如果没有加减号，就需要考虑乘除号（if(c1 < 0) c1 = c2）；如果全都没有，说明整个表达式外面被一对括号括起来，把它去掉后递归调用。这样，就找到了最后计算的运算符s[c1]，它的左子树是区间[x, c1]，右子树是区间[c1+1, y]。
例题
例题，【例3-1】找树根和孩子
//fa[N]维护每个结点的父亲，如果一个节点没有fa，他就是根//son[N]维护孩子个数
例题，【例3-4】求后序遍历
//给出先序和中序，求后续void dfs(int l1, int r1, int l2, int r2)//根据先序l1位置的根，去找中序中根的位置
例题，【例3-5】扩展二叉树
//给出扩展二叉树的先序序列，输出中序和后序//题解给出的是指针写法【指针】
例题，二叉树遍历(flist)
//给出中序序列和按层序列，求先序序列//在按层遍历序列中先遇到根，在中序序列中，找到根的位置，break出来//进行递归处理void dfs(int l1, int r1, int l2, int r2)
大纲要求
•【3】树的定义及其相关概念
•【4】树的父亲表示法
•【3】二叉树的定义及其基本性质
•【4】二叉树的孩子表示法
•【4】二叉树的遍历：前序、中序、后序遍历
若有收获，就点个赞吧
0 人点赞
