pascal算法问题
发布网友
发布时间：2024-10-12 01:29
共4个回答
热心网友
时间：2024-11-17 20:24
定义：
BST 待遍历的二叉树；
postorder 后序遍历规则；
first_node 按后序遍历规则遍历时将访问的第一个结点；
current_node 当前将要访问的结点；
next_node 根据postorder规则，在current_node之后即将访问的后继结点；
parent(node) 结点node的父结点；
lchild(node) 结点node的左孩子；
rchild(node) 结点node的右孩子。
算法步骤：
1 找到BST中以postorder方式遍历时将访问的第一个结点，即first_node；
2 令current_nodeçfirst_node；
3 查找current_node的后继结点next_node：
3.1 若current_node之父结点为空，算法结束；
3.2 若current_node为其父结点的左孩子，且其父结点无右子树，则next_nodeçparent(current_node)；
3.3 若current_node为其父结点的左孩子，且其父结点有右子树，则令pçparent(current_node)，于是next_node为结点p之右子树中以postorder方式遍历时将访问的第一个结点；
3.4 若current_node为其父结点之右子树，则next_nodeçparent(current_node)；
4 访问current_node；
5 令current_nodeçnext_node，转到3。
满二叉树时之复杂度
不妨令满二叉树的深度为k（二叉树的层数记为i=1, 2, …, k-1），则总的结点数n=2k-1。对于一棵深度为k的满二叉树，按后序遍历规则查找第一个结点的操作步骤数为k-1。对满二叉树的第i层结点(i=1, 2, …, k-1)，有2i-1个结点是其父结点的左孩子，有2i-1个结点是其父结点的右孩子。对于第i层的每个左孩子结点，需要按后序遍历规则查找其后继结点，此时父结点之右子树的深度为k-i，根据前述说明，则每个左孩子结点需要执行k-i-1次查找后继结点的操作，总的操作次数为2i-1 * (k-i-1)次。对于第i层的每个右孩子结点，其父结点即为其后继结点，因此对每个右孩子结点所需要执行的操作为1，因此第i层右孩子总的操作数为2i-1 * 1。由此，第i层总的操作数为2i-1 * (k-i-1) + 2i-1 * 1=2i-1 * (k-i)。将以上所有层累加起来即得到除根结点之外的所有层上的操作数(i=1, 2, …, k-1)，不妨设为α：
α= 21-1 * (k-1) + 22-1 * (k-2) + … + 2k-2 * 1 = 20 * (k-1) + 21 * (k-2) + … + 2k-2 * 1
则有
α= 2α-α= … = 2k – k – 1
以上就是除根结点之外所有结点上的操作总数。当处理根结点时，实际上只需要做一次判断即可。于是算法总的操作次数T = α+1 = 2k – k。又由前面的假设可知n=2k-1，因此2k=n+1，k=lg(n+1)。故可得算法总的操作数为：
T = n+1-lg(n+1)
故，该算法的复杂度为O(n)。
热心网友
时间：2024-11-17 20:23
其实很简单，就是插入，删除，查找三个操作。理想复杂度都是log2(n)
这个算法书上都有。
bst没什么意义，因为如果退化成一条链复杂度就变成n了。
建议去看一看平衡树，类似于splay之类的。
热心网友
时间：2024-11-17 20:18
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
查找：
步骤：若根结点的关键字值等于查找的关键字，成功。
否则，若小于根结点的关键字值，递归查左子树。
若大于根结点的关键字值，递归查右子树。
若子树为空，查找不成功。
插入算法：
首先执行查找算法，找出被插结点的父亲结点。
判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。
若二叉树为空。则首先单独生成根结点。
注意：新插入的结点总是叶子结点。
void InsertBST(t，key)
//在二叉排序树中插入查找关键字key
{
if(t==NULL){
t=new BiTree;
t->lchild=t->rchild=NULL;
t->data=key;
return; }
if(key<t->data ) InsertBST(t->lchild,key);
else InsertBST (t->rchild, key );
}
void CreateBiTree(tree,d[ ],n）
//n个数据在数组d中，tree为二叉排序树根
{ tree=NULL;
for(i=0;i<n;i++)
InsertBST(tree,d);
}
题目嘛 我推荐
Poj 2418 2482 2352
初学的话可以先看看2418的题解顺便体会一下BST的使用，然后后面两题独立地做
热心网友
时间：2024-11-17 20:21
BST可以动态的进行插入,删除,找第k大,找某个节点操作
例如插入某个节点,那么就从根开始递归,比根小就递归到左子树,否则递归到右子树,一直到递归到叶子为止,再插入.
其它的操作都类似.这些操作复杂度都是O(h),h树的高度.期望情况下h=O(logn),不过最坏的话h=O(n).为了保持H=O(logn),需要加强bst使之平衡,叫做平衡树,例如avltree,rbtree,sbt,splay,treap等.
例题嘛......noi2004 cashier以及刚结束的ioi 2009的hiring都是用到平衡树的.
