二叉排序树的构造_二叉排序树唯一吗_二叉排序树的建立(3)

（1）设二叉树共有N个结点（N为大于1的正整数），我们按照还原方法给中序序列中的这N个结点分别赋予权值1,2…N，设根结点的权值为M（1

（2）由二叉树的遍历规则可知，权值为1,2…M-1的结点为根结点的左子树中的结点，而权值为M+1,…N的结点为根结点的右子树中的结点。

（3）将这N个结点划分成3个子集AA＝（1,2…M-1）BB＝（M）CC＝（M+1,…N），由于前序序列第一个读入的结点必定为二叉根的根结点，所以BB为根结点，AA集为左子树，CC集为右子树。

（4）同理不断读入前序序列中的结点，依次递归还原BB对应的左子树和CC对应的右子树，最后将三棵子树合并成以BB为根结点、AA的根结点为BB的左子树、CC的根结点为BB的右子树的一棵二叉排序树。

（5）同理可以得出，由中序序列和后序序还原二叉树的规则也成立。

（6）在还原过程中，读入序列的顺序也遵循也先根结点，后子树的规律。

3总结

在二叉树的一些应用中，如平衡二叉树、红黑树等，常常要观察二叉树的形态，对其进行判断并调整。根据遍历序列和二叉排序树的性质快速还原出二叉树对于研究相关的问题有很大的帮助。二叉排序树的建立

上面可以得出前序扩展序列 ABD/E///C//FG//H

后序为 ED##B###G##HFCA

void PreCreate(Node* p)

{

if(line == end)

return;

if(line == “/”)

p = NULL;

else{

p = new NOde();

p->data = line;

PreCreate(p->Left);

PreCreate(p->Right);

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-31416-3.html