赞
踩
仅由先序序列无法确定一棵二叉树,但是我们可以由拓展二叉树的先序序列可以唯一确定一棵二叉树。
拓展二叉树:将原二叉树每个结点的空指针都引出一个“虚结点”,令其值为 ‘#’
,表示为空结点,这样处理的二叉树称为原二叉树的拓展二叉树。
拓展二叉树的先序序列:"124###3#5##"
void PreCreate(BiTree &T) {
char n;
cin >> n;
if (n != '#') { //终止条件
T = new BiNode;
T->data = n;
PreCreate(T->lchild); //当输入第一个/ /前,建立的是一路向左的单叉树
PreCreate(T->rchild); //输入第一个/ / ,开始回溯到上一个结点的,右子树
}
else
T = NULL;
}
已知由先序、中序我们可以唯一确定一棵二叉树。具体的方法:先序序列第一个即是树的根,在中序序列中查找根结点所在位置,中序序列中根结点左边即是左子树,右边即是右子树,我们就利用中序序列划分了左右子树。
对于左右子树,我们再去先序中顺序寻找子树的根,根据根再去划分左右子树…直到为空。
每一次pre[L1]
为根,mid[k]
为根则
pre的划分边界是
L
1
,
[
L
1
+
1
,
.
.
.
,
k
−
L
2
+
L
1
]
,
[
k
−
L
2
+
L
1
+
1
,
.
.
.
,
H
1
]
L1,[L1+1,...,k-L2+L1],[k-L2+L1+1,...,H1]
L1,[L1+1,...,k−L2+L1],[k−L2+L1+1,...,H1]
mid的划分点是
[
L
2
,
.
.
,
k
−
1
]
,
k
,
[
k
+
1
,
.
.
.
,
H
2
]
[L2,..,k-1],k,[k+1,...,H2]
[L2,..,k−1],k,[k+1,...,H2]
char pre[] = "#12435"; //先序序列
char mid[] = "#42135"; //中序序列
void PreInCreate(BiTree& T, int L1, int H1, int L2, int H2) {
if (L2 > H2)
T = NULL;
else {
T = new BiNode;
T->data = pre[L1];
int k;
for (k = L2; mid[k] != pre[L1]; k++); //中序中找到根的位置,记得加:
PreInCreate(T->lchild, L1 + 1, k + L1 - L2, L2, k - 1); //k-L2+1是左子树结点数量,对应pre中下标为L1+(k-L2+1)-1=L1+k-L2
PreInCreate(T->rchild, k + L1 - L2 + 1, H1, k + 1, H2);
}
}
法2:由长度确定终止条件:
void PreInOrder(BiTree &T, int l1, int h1, int l2, int h2) {
T = new BiNode;
T->data = pre[l1];
int k = l2;
for (; mid[k] != pre[l1]; k++);
int len1 = k - l2;
int len2 = h2 - k;
if (len1) //左边
PreInOrder(T->lchild, l1 + 1, l1 + len1, l2, l2 + len1 - 1); //必须是len1
else
T->lchild = NULL;
if (len2)
PreInOrder(T->rchild, h1 - len2 + 1, h1, h2 - len2 + 1, h2); //必须是len2
else
T->rchild = NULL;
}
因为if(len1)
、if(len2)
的作用域问题,其相应的表达式中 只能出现len1
、len2
不可再if(len2)
下面出现len1
,if(len1)
下面也不可出现len2
规定结点的编号为对二叉树做层次遍历从1开始的编号。
如果一棵二叉树不是完全二叉树,可以用添加虚结点的方式将其扩展为一棵完全二叉树。虚结点的值设为'#'
,表示该结点不存在,把这样处理后的二叉树称为原二叉树的扩展完全二叉树。
完全二叉树中,对于第i
个节点,他的左子节点为第2i
个,右子结点为第2i+1
个(如果都有的话)。
已知拓展完全二叉树层次遍历得到的节点数组(#表空):
"#ABC#D#####E"
递归生成二叉树,递归生成左右结点,直到不存在置空返回。
char s[] = "#1234#5#6###7"; //从1开始,层次遍历
void Create(BiTree& T, int i, int n) { //n为结点数量(包括#) ,i初始为1,即根的位置
if (s[i] == '#')
T = NULL;
else {
T = new BiNode;
T->data = s[i];
int j = 2 * i; //生成左子结点2i
if (j <= n)
Create(T->lchild, j, n);
else
T->lchild = NULL;
j++; //生成右子结点2i+1
if (j <= n)
Create(T->rchild, j, n);
else
T->rchild = NULL;
}
}
假设先序为pre[1..n]
,中序为mid[1..n]
,n是指二叉树结点的个数,pre[1]是指二叉树的根。
每次取出pre[1…n]一个结点进行插入,插入时判断,若T
是空,直接让s
为根结点T=s
若T
不是同,就去比较T
和s
在中序序列中的位置
若find(T->data) > find(s->data)
,说明应该插入T的左子树上,向下递归到T的左子结点Insert_Node(T->lchild,s)
继续比较,直到最后一个结点,其s为其左/右子,且其lchild/rchild=NULL,就插入。
若find(T->data) < find(s->data)
,说明应该插入T的右子树上,向下递归到T的右子结点Insert_Node(T->rchild,s)
继续比较…
对于先序序列的每一个,通过中序序列不断划分左右结点,向下递归找到正确位置,直到所有结点都找到即成功。
/*4. 由先序、中序,利用排序二叉树的性质*/
char pre[] = "#12435"; //先序序列
char mid[] = "#42135"; //中序序列
int find(char x) { //返回x在中序序列中的位置(下标)
int i=1;
for (; mid[i] != x; i++);
return i;
}
void Insert_Node(BiTree& T, BiNode* s) { //将s插入到以T为根的二叉树中
if (T == NULL)
T = s; //T每次开始调用的时候都指向根,最好一次调用指向空(T的值不变)
else{
if (find(T->data) > find(s->data)) //s在T的左子树上,向下递归
Insert_Node(T->lchild, s);
else //s在T的右子树上,向下递归
Insert_Node(T->rchild, s);
}
}
void Create(BiTree& T, int n) {
T = NULL;
for (int i = 1; i <= n; i++) {
BiNode* s = new BiNode;
s->data = pre[i]; //每次顺序取出先序序列的值
s->lchild = NULL;
s->rchild = NULL;
Insert_Node(T, s); //进行比较位置的插入
}
}
综上所水:
1.拓展先序建立 | 数据:拓展二叉树的先序序列 参数:T 递归:先序遍历,将访问结点变成了生成结点 |
2.先序、中序建立 | 数据:先序、中序序列 参数:T,L1,H1,L2,H2 递归:左右子树递归 |
3.拓展完全二叉树 | 数据:拓展完全二叉树的顺序存储(层次遍历) 参数:T,i,n 递归:左右结点2i,2i+1 |
4.二叉排序树的性质 | 数据:先序、中序序列 参数:T,n / T,s 递归:一直向下划分左右子树,然后插入 |
1最简单,但要手动输入(太累)
2较为简单,仅需先序+中序
3最直观,由填充完全的层序数组构建
4.最麻烦,排序方法插入结点
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。