本文共 4298 字,大约阅读时间需要 14 分钟。
二叉查找树
,要么为空树,要么满足下列条件: 1)若左子树非空,则左子树上的所有结点的值均小于根节点的值
; 2)若右子树非空,则右子树上的所有节点的值均大于根节点的值
; 3)左、右子树分别也是一棵二叉排序树。 void BST_Creat(BTree &T, int k[], int len){ T=NULL; int i=0; while(i
二叉排序树的查找是从根节点开始,沿某个分支逐层向下比较的过程
。 1)若二叉树非空,先用给定值与根节点值比较,若相等,则查找成功; 2)若不等,若小于根节点值,则在根节点左子树上查找; 3)若不等,若大于根节点值,则在根节点右子树上查找; 4)重复以上步骤,直到查找成功或遍历完所有节点返回查找失败。BSTNode *BST_Search(BTree T, int key){ while(T!=NULL&&key!=T->data) { if(keydata) T=T->lchild; else T=T->rchild; } return T;}
插入的结点一定是一个新添加的叶结点,且是查找失败时的査找路径上访问的最后一个结点的左孩子或右孩子
。 int BST_Insert(BTree &T, int k){ if(T==NULL) { T = new BTree; T->key=k; T->lchild=T->rchild=NULL; return 1; } else if(k==T->key) return 0; else if(kkey) return BST_Insert(T->lchild,k); else return BST_Insert(T->rhild, k);}
(1+2+3+4+5+6+7+8+9+10)/10=5.5
。(1+2*2+3*4+4*3)/10=2.9
.(层号*层宽)。任意节点的左、右子树高度差的绝对值不超过1
,则将这种二叉树称为平衡二叉树(Balanced Binary Tree)
,简称平衡树,并定义节点左右子树高度差为该节点的平衡因子(-1, 0, 1)
。右单旋转
。 将A的左孩子B向右上旋转代替A成为根结点,将A结点向右下旋转成为B的右子树的根结点,而B的原右子树则作为A结点的左子树
。又称为左单旋转
。
由于在结点4的右孩子(R)的右子树(R)上插入了新结点,A的平衡因子由-1减至-2,导致以A为根的子树失去平衡,需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点,将A结点向左下旋转成为B的左子树的根结,而B的原左子树则作为A结点的右子树
。
先左后右双旋转
。 先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置,然后再把该C结点向右上旋转提升到A结点的位置
。先右后左双旋转
。 先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置,然后再把该C结点向左上旋转提升到A结点的位置
。权
。而与此对于的,从根节点出发到任意节点路径长度与该节点权值的乘积称为带权路径长度
,而所有节点的带权路径长度之后就是树的带权路径长度,即为: WPL最小的二叉树就是最优带权二叉树,简称最优二叉树
,还叫哈夫曼树,这是因为构造最优二叉树经典算法就是哈夫曼算法。typedef struct HTNode{ int weight; int parent, lchild, rchild;}*HuffmanTree;void Select(HuffmanTree HT, int n, int &S1, int &S2){ int min1=min2=0; for(int j=1;j<=n;j++) { if(HT[j].parent=0) { min1=min2=HT[j].wieght; break; } } int i=1,k=1; while(i<=n) { if(min1>HT[i].weight&&HT[i].parent==0) { min1=HT[i].weight; S1=i; } i++; } while(k<=n&&j!=S1) { if(min2>HT[k].weight&&HT[j].parent==0) { min2=HT[k].weight; S2=k; } k++; }}void CreateHT(HuffmanTree &HT, int n){ if(n<=1) return; int m = 2*n-1; HT = new HTNode[m+1]; for(int i=1;i>HT[i].weight; int s1=s2=0; for(int i=n+1; i
转载地址:http://eqqgn.baihongyu.com/