树的相关算法
❶ 二叉树算法
二叉树是没有度为1的结点。
完全二叉树定义：
若设二叉树的高度为h，除第
h
层外，其它各层
(1～h-1)
的结点数都达到最大个数，第
h
层从右向左连续缺若干结点，这就是完全二叉树。
完全二叉树叶子结点的算法：
如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。
可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0＝n2＋1，则n=
n0＋n1＋n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n=
2n0+n1－1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合并成一个公式：n0＝（n＋1）/2
，就可根据完全二叉树的结点总数计算出叶子结点数。
因此叶子结点数是(839+1)/2=420
❷ java构建二叉树算法
//******************************************************************************************************//
//*****本程序包括简单的二叉树类的实现和前序,中序,后序,层次遍历二叉树算法,*******//
//******以及确定二叉树的高度,制定对象在树中的所处层次以及将树中的左右***********//
//******孩子节点对换位置,返回叶子节点个数删除叶子节点,并输出所删除的叶子节点**//
//*******************************CopyRight By phoenix*******************************************//
//************************************Jan 12,2008*************************************************//
//****************************************************************************************************//
public class BinTree {
public final static int MAX=40;
private Object data; //数据元数
private BinTree left,right; //指向左,右孩子结点的链
BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点
int front;//层次遍历时队首
int rear;//层次遍历时队尾
public BinTree()
{
}
public BinTree(Object data)
{ //构造有值结点
this.data = data;
left = right = null;
}
public BinTree(Object data,BinTree left,BinTree right)
{ //构造有值结点
this.data = data;
this.left = left;
this.right = right;
}
public String toString()
{
return data.toString();
}//前序遍历二叉树
public static void preOrder(BinTree parent){
if(parent == null)
return;
System.out.print(parent.data+" ");
preOrder(parent.left);
preOrder(parent.right);
}//中序遍历二叉树
public void inOrder(BinTree parent){
if(parent == null)
return;
inOrder(parent.left);
System.out.print(parent.data+" ");
inOrder(parent.right);
}//后序遍历二叉树
public void postOrder(BinTree parent){
if(parent == null)
return;
postOrder(parent.left);
postOrder(parent.right);
System.out.print(parent.data+" ");
}// 层次遍历二叉树
public void LayerOrder(BinTree parent)
{
elements[0]=parent;
front=0;rear=1;
while(front<rear)
{
try
{
if(elements[front].data!=null)
{
System.out.print(elements[front].data + " ");
if(elements[front].left!=null)
elements[rear++]=elements[front].left;
if(elements[front].right!=null)
elements[rear++]=elements[front].right;
front++;
}
}catch(Exception e){break;}
}
}//返回树的叶节点个数
public int leaves()
{
if(this == null)
return 0;
if(left == null&&right == null)
return 1;
return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());
}//结果返回树的高度
public int height()
{
int heightOfTree;
if(this == null)
return -1;
int leftHeight = (left == null ? 0 : left.height());
int rightHeight = (right == null ? 0 : right.height());
heightOfTree = leftHeight<rightHeight?rightHeight:leftHeight;
return 1 + heightOfTree;
}
//如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层
public int level(Object object)
{
int levelInTree;
if(this == null)
return -1;
if(object == data)
return 1;//规定根节点为第一层
int leftLevel = (left == null?-1:left.level(object));
int rightLevel = (right == null?-1:right.level(object));
if(leftLevel<0&&rightLevel<0)
return -1;
levelInTree = leftLevel<rightLevel?rightLevel:leftLevel;
return 1+levelInTree;
}
//将树中的每个节点的孩子对换位置
public void reflect()
{
if(this == null)
return;
if(left != null)
left.reflect();
if(right != null)
right.reflect();
BinTree temp = left;
left = right;
right = temp;
}// 将树中的所有节点移走,并输出移走的节点
public void defoliate()
{
String innerNode = "";
if(this == null)
return;
//若本节点是叶节点，则将其移走
if(left==null&&right == null)
{
System.out.print(this + " ");
data = null;
return;
}
//移走左子树若其存在
if(left!=null){
left.defoliate();
left = null;
}
//移走本节点，放在中间表示中跟移走...
innerNode += this + " ";
data = null;
//移走右子树若其存在
if(right!=null){
right.defoliate();
right = null;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinTree e = new BinTree("E");
BinTree g = new BinTree("G");
BinTree h = new BinTree("H");
BinTree i = new BinTree("I");
BinTree d = new BinTree("D",null,g);
BinTree f = new BinTree("F",h,i);
BinTree b = new BinTree("B",d,e);
BinTree c = new BinTree("C",f,null);
BinTree tree = new BinTree("A",b,c);
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
System.out.println("--------------------------------------");
tree.reflect();
System.out.println("交换每个节点的孩子节点后......");
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
}
❸ 求二叉树的基本算法和各种遍历算法
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef char TElemType;
typedef int Status;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree &T) //按先序次序输入二叉树中结点的值，构造二叉树链表
{
char ch;
ch=getchar();
if(ch==' ')
T=NULL;
else
{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
Status PreOrder(BiTree T) //先序遍历的递归算法
{
if(T)
{
cout<<T->data;
PreOrder(T->lchild);
PreOrder(T->rchild);
}
return OK;
}
Status InOrder(BiTree T) //中序遍历的递归算法
{
if(T)
{
InOrder(T->lchild);
cout<<T->data;
InOrder(T->rchild);
}
return OK;
}
Status PostOrder(BiTree T) //后续遍历的递归函数
{
if(T)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
cout<<T->data;
}
return OK;
}
Status BiTreeLevelOrder(BiTree T) //层序遍历的非递归函数
{
int front=0,rear=0;
BiTree p,Q[20];
if(T)
{
rear++;
Q[rear]=T;
}
while(front!=rear)
{
front++;
p=Q[front];
cout<<p->data;
if(p->lchild)
{
rear++;
Q[rear]=p->lchild;
}
if(p->rchild)
{
rear++;
Q[rear]=p->rchild;
}
}
return OK;
}
Status BiTreeNodeSum(BiTree T) //计算二叉树的结点数
{
if(T==NULL)
return 0;
else
return 1+BiTreeNodeSum(T->lchild)+BiTreeNodeSum(T->rchild);
}
Status BiTreeLeafSum(BiTree T) //计算二叉树的叶子结点数
{
if(T==NULL)
return 0;
else
if(T->lchild==NULL&&T->rchild==NULL)
return 1;
else
return BiTreeLeafSum(T->lchild)+BiTreeLeafSum(T->rchild);
}
Status BiTreeDeep(BiTree T) //计算二叉树的深度
{
if(T==NULL)
return 0;
else
return (BiTreeDeep(T->lchild)>BiTreeDeep(T->rchild))?(BiTreeDeep(T->lchild)+1):(BiTreeDeep(T->rchild)+1);
}
void main() //主函数
{
BiTree T;
cout<<"input Bitree char:"<<endl;
CreateBiTree(T);
cout<<"先序遍历为："<<endl;
PreOrder(T);
cout<<endl;
cout<<"中序遍历为："<<endl;
InOrder(T);
cout<<endl;
cout<<"后序遍历为："<<endl;
PostOrder(T);
cout<<endl;
cout<<"层序遍历为："<<endl;
BiTreeLevelOrder(T);
cout<<endl;
BiTreeNodeSum(T);
cout<<"二叉树的结点数："<<BiTreeNodeSum(T)<<endl;
BiTreeLeafSum(T);
cout<<"二叉树的叶子结点数为："<<BiTreeLeafSum(T)<<endl;
BiTreeDeep(T);
cout<<"二叉树的深度为："<<BiTreeDeep(T)<<endl;
}
❹ 二叉树相关算法的实验验证 [ 实验目的] 验证二叉树的链接存储结构及其上的基本操作。（c++）
浅谈数据结构-二叉树
二叉树是树的特殊一种，具有如下特点：1、每个结点最多有两颗子树，结点的度最大为2。2、左子树和右子树是有顺序的，次序不能颠倒。3、即使某结点只有一个子树，也要区分左右子树。
一、特殊的二叉树及特点
1、斜树
所有的结点都只有左子树（左斜树），或者只有右子树（右斜树）。这就是斜树，应用较少
基本思想：先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点即左—右—根。
图中后序遍历结果是：4，8，7，5，2，6，3，1。
后序递归遍历代码实现，如下所示。
后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问，并且左孩子在右孩子之前访问才能访问根结点，这就为流程控制带来了难题。下面介绍一种思路。
要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点p，先将其入栈。若p不存在左孩子和右孩子，则可以直接访问它，或者p存在左孩子或右孩子，但是其左孩子和右孩子都已经被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将p的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子之前别访问，左孩子和右孩子都在根结点前面被访问。
五、二叉树的建立
其实而二叉树的建立就是二叉树的遍历，只不过将输入内容改为建立结点而已，比如，利用前序遍历建立二叉树
❺ 关于二叉树的算法.C++
#include<vector>
#include<iostream>
usingnamespacestd;
structTreeNode
{
intval;
TreeNode*left;
TreeNode*right;
TreeNode(intx):val(x),left(NULL),right(NULL){} //constructionfunction
};
voidfun(TreeNode*root,vector<TreeNode*>&vt)
{
if(root==nullptr)
return;
vt.push_back(root);
fun(root->left,vt);
fun(root->right,vt);
for(autoele:vt)
cout<<ele->val<<"";
cout<<endl;
vt.pop_back();
}
intmain()
{
TreeNode*root=newTreeNode(0);
root->left=newTreeNode(1);
root->right=newTreeNode(2);
root->left->right=newTreeNode(3);
root->left->right->left=newTreeNode(4);
root->right->left=newTreeNode(5);
root->right->right=newTreeNode(6);
vector<TreeNode*>vt;
fun(root,vt);
}
❻ 有关二叉树递归的算法
靠，缩进全被网络搞乱了，自己排版
#include <iostream>
using namespace std;
//二叉树节点
struct BiTreeNode{
int data;
BiTreeNode *left;
BiTreeNode *right;
};
//写一个类，方便二叉树的建立和删除
class BiTree{
private:
void deleteAllNode(BiTreeNode *root);
public:
BiTreeNode *root;
BiTree();
~BiTree();
void CreateTree();
void deleteLeaves(BiTreeNode *root);
bool DepthOfTheNode(BiTreeNode *currentNode,BiTreeNode *p, int depthOfFather);
void FindMaxValue(BiTreeNode *currentNode, int *maxValue);
void ExchangeLeftAndRight(BiTreeNode *currentNode);
void OutputValueAndDepthByQIANXU(BiTreeNode *currentNode, int depthOfFather); //不好意思，用了拼音
};
BiTree::BiTree()
{
root = NULL;
}
BiTree::~BiTree()
{
deleteAllNode(root);
}
void BiTree::deleteAllNode(BiTreeNode *root)
{
if (root == NULL) return;
deleteAllNode(root->left);
deleteAllNode(root->right);
cout << root->data << ' '; //用来查看当前节点是不是被删除。
delete root;
}
//手动建立一个二叉树用于测试
// 1
// / \
// 2 3
// \ /
// 4 5
void BiTree::CreateTree()
{
if (root) return;
root = new BiTreeNode;
root->data = 1;
root->left = new BiTreeNode;
root->left->data = 2;
root->right = new BiTreeNode;
root->right->data = 3;
BiTreeNode *p;
p = root->left;
p->left = NULL;
p->right = new BiTreeNode;
p->right->data = 4;
p->right->left = p->right->right = NULL;
p= root->right;
p->left = new BiTreeNode;
p->left->data = 5;
p->left->left = p->left->right = NULL;
p->right = NULL;
}
//用递归算法删除叶子
void BiTree::deleteLeaves(BiTreeNode *root)
{
if (root == NULL) return;
if (!root->left && !root->right) return; //表示是根节点(或者出错，跑到叶子节点了，这种情况应该不会)，不删除
if (root->left) //当前节点有左子树
{
if (root->left->left || root->left->right) //左子树不是叶子
deleteLeaves(root->left);
else //当前节点的左子节点是叶子
{
delete root->left;
root->left = NULL;
}
}
if (root->right)
{
if (root->right->left || root->right->right)
deleteLeaves(root->right);
else //当前节点的右子节点是叶子
{
delete root->right;
root->right = NULL;
}
}
}
int depth = 0; //一个用来存储深度的全局变量，虽然在实际编程中这样用不好
//但一切为了方便。
//节点p的深度,递归法
bool BiTree::DepthOfTheNode(BiTreeNode *currentNode,BiTreeNode *p, int depthOfFather)
{
if (currentNode == NULL) return false;
if (currentNode == p) //当前节点为要找的节点
{
depth = depthOfFather + 1;
return true;;
}
if (DepthOfTheNode(currentNode->left, p, depthOfFather+1)) //找当前节点的左子树
return true;
else
return DepthOfTheNode(currentNode->right, p, depthOfFather+1);
}
//用递归找最大值，最大值存储在maxValue所指的内存 ,这里使用前序遍历
void BiTree::FindMaxValue(BiTreeNode *currentNode, int *maxValue)
{
if (currentNode == NULL) return;
*maxValue = *maxValue > currentNode->data ? *maxValue : currentNode->data;
FindMaxValue(currentNode->left, maxValue); //遍历左子树
FindMaxValue(currentNode->right, maxValue);
}
//交换左右，用前序遍历
void BiTree::ExchangeLeftAndRight(BiTreeNode *currentNode)
{
if (currentNode == NULL) return;
BiTreeNode *temp;
temp = currentNode->left;
currentNode->left = currentNode->right;
currentNode->right = temp;
ExchangeLeftAndRight(currentNode->left);
ExchangeLeftAndRight(currentNode->right);
}
//以前序次序输出一棵二叉树所有结点的数据值及结点所在层次
void BiTree::OutputValueAndDepthByQIANXU(BiTreeNode *currentNode, int depthOfFather)
{
if (currentNode == NULL) return;
cout << "节点：" << currentNode->data;
cout << "\t深度：" << depthOfFather+1 << endl;
OutputValueAndDepthByQIANXU(currentNode->left, depthOfFather+1);
OutputValueAndDepthByQIANXU(currentNode->right, depthOfFather+1);
}
int main()
{
BiTree bt;
bt.CreateTree();
//求p的深度
bt.DepthOfTheNode(bt.root, bt.root->left->right, 0);
cout << "深度:" << depth << endl;
//找最大值
int maxValue;
bt.FindMaxValue(bt.root, &maxValue);
cout << "最大值为：" << maxValue << endl;
//交换左右节点
bt.ExchangeLeftAndRight(bt.root);
//以前序次序输出一棵二叉树所有结点的数据值及结点所在层次
bt.OutputValueAndDepthByQIANXU(bt.root, 0);
//删除叶子节点
bt.deleteLeaves(bt.root);
return 0;
}
❼ 平衡树的主要算法
红黑树的平衡是在插入和删除的过程中取得的。对一个要插入的数据项，插入程序要检查不会破坏树一定的特征。如果破坏了，程序就会进行纠正，根据需要更改树的结构。通过维持树的特征，保持了树的平衡。
红黑树有两个特征：
(1) 节点都有颜色
(2) 在插入和删除过程中，要遵循保持这些颜色的不同排列的规则。
红黑规则：
1. 每一个节点不是红色的就是黑色的
2. 根总是黑色的
3. 如果节点是红色的，则它的子节点必须是黑色的（反之不一定成立）
4. 从根到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点。
（空子节点是指非叶节点可以接子节点的位置。换句话说，就是一个有右子节点的节点可能接左子节点的位置，或是有左子节点的节点可能接右子节点的位置） AVL树，它或者是一颗空二叉树，或者是具有下列性质的二叉树：
(1) 其根的左右子树高度之差的绝对值不能超过1；
(2) 其根的左右子树都是二叉平衡树。
AVL树查找的时间复杂度为O(logN)，因为树一定是平衡的。但是由于插入或删除一个节点时需要扫描两趟树，依次向下查找插入点，依次向上平衡树，AVL树不如红黑树效率高，也不如红黑树常用。
AVL树插入的C++代码： template<classT>ResultCodeAVLTree<T>::Insert(AVLNode<T>*&p,T&x,bool&unBalanced)...{ResultCoderesult=Success;if(p==null)...{//插入新节点p=newAVLNode<T>(x);unBalanced=true;}elseif(x<p->element)...{//新节点插入左子树result=Insert(p->lChild,x,unBalanced);if(unBanlanced)...{switch(p->bF)...{case-1:p->bF=0;unBalanced=false;break;case0:p->bF=1;break;case1:LRotation(p,unBalanced);}}}elseif(x==p->element)...{//有重复元素，插入失败unBalanced=false;x=p->element;result=Duplicate;}else...{//新节点插入右子树result=Insert(p->rChild,x,unBalanced);if(unBalanced)...{switch(p->bF)...{case1:p->bF=0;unBalanced=false;break;case0:p->bF=-1;break;case-1:RRotation(p,unBalanced);}}}returnresult;}template<classT>voidAVLTree<T>::LRotation(AVLNode<T>*&s,bool&unBalanced)...{AVLNode<T>*u,*r=s->lChild;if(r->bF==1)...{//LL旋转s->lChild=r->rChild;r->rChild=s;s->bF=0;s=r;//s指示新子树的根}else...{//LR旋转u=r->rChild;r->rChild=u->lChild;u->lChild=r;s->lChild=u->rChild;u->rChild=s;switch(u->bF)...{case1:s->bF=-1;r->bF=0;break;case0:s->bF=r->bF=0;break;case-1:s->bF=0;r->bF=1;}s=u;//s指示新子树的根}s->bF=0;//s的平衡因子为0unBalanced=false;//结束重新平衡操作}通常我们使用二叉树的原因是它可以用O（logn）的复杂度来查找一个数，删除一个数，对吧？？可是有时候会发现树会退化，这个就可能使O（logn）->O（n）的了，那么还不如用直接搜一次呢！！所以我们就要想办法使一棵树平衡。而我仅仅看了（AVL）的那个，所以也仅仅能说（AVL）的那个，至于（TREAP），我还不懂，如果你们知道算法的话，欢迎告诉我~！谢谢~
首先引入一个变量，叫做平衡因子（r），节点X的r就表示x的左子树的深度-右子树的深度。然后我们要保证一棵树平衡，就是要保证左右子树的深度差小于等于1.所以r的取值能且仅能取0，-1，1.
其次，我要介绍旋转，旋转有两种方式，就是左旋（顺时针旋转）和右旋（逆时针旋转）。
左旋（左儿子代替根）：即用左儿子取代根，假设我们要旋转以X为根，LR分别为X的左右儿子，那么我们只需要把L的右儿子取代X的左儿子，然后把更新后的X赋值为L的右儿子，就可以了。
右旋（右儿子代替根）：即用右儿子取代根，假设我们要旋转以X为根，LR分别为X的左右儿子，那么我们只需要把R的左儿子取代X的右儿子，然后把更新后的X赋值为R的左儿子，就可以了。 Size Balanced Tree(SBT平衡树）是2007年Winter Camp上由我国着名OI选手陈启峰发布的他自己创造的数据结构。相比于一般的平衡树，此平衡树具有的特点是：快速（远超Treap，超过AVL)、代码简洁、空间小（是线段树的1/4左右）、便于调试和修改等优势。
与一般平衡搜索树相比，该数据结构只靠维护一个Size来保持树的平衡，通过核心操作Maintain(修复）使得树的修改平摊时间为O(1)。因而大大简化代码实现复杂度、提高运算速度。
参见网络SBT。 平衡树的一种，每次将待操作节点提到根，每次操作时间复杂度为O(logn)。见伸展树。 constintSPLAYmaxn=200005;constintSPLAYinf=100000000;structSplay_Node{intl,r,fa,v,sum;};structSplay{Splay_Nodet[SPLAYmaxn];introot,tot;voidcreate(){root=1,tot=2;t[1].v=-SPLAYinf;t[2].v=SPLAYinf;t[1].r=t[1].sum=2;t[2].fa=t[2].sum=1;}voipdate(intnow){t[now].sum=t[t[now].l].sum+t[t[now].r].sum+1;}voidleft(intnow){intfa=t[now].fa;t[now].fa=t[fa].fa;if(t[t[fa].fa].l==fa)t[t[fa].fa].l=now;if(t[t[fa].fa].r==fa)t[t[fa].fa].r=now;t[fa].fa=now;t[fa].r=t[now].l;t[t[now].l].fa=fa;t[now].l=fa;up(fa);}voidright(intnow){intfa=t[now].fa;t[now].fa=t[fa].fa;if(t[t[fa].fa].l==fa)t[t[fa].fa].l=now;if(t[t[fa].fa].r==fa)t[t[fa].fa].r=now;t[fa].fa=now;t[fa].l=t[now].r;t[t[now].r].fa=fa;t[now].r=fa;update(fa);}voidsplay(intnow,intFA=0){while(t[now].fa!=FA){intfa=t[now].fa;if(t[fa].fa==FA)if(t[fa].l==now)right(now);elseleft(now);elseif(t[t[fa].fa].l==fa)if(t[fa].l==now)right(fa),right(now);elseleft(now),right(now);elseif(t[fa].l==now)right(now),left(now);elseleft(fa),left(now);}update(now);if(!FA)root=now;}intlower_bound(intv){intans=0,la=0;for(intnow=root;now;){la=now;if(t[now].v>=v)ans=now,now=t[now].l;elsenow=t[now].r;}splay(la);returnans;}voidinsert(intv){for(intnow=root;;){++t[now].sum;if(t[now].v>=v)if(t[now].l)now=t[now].l;else{t[now].l=++tot;t[tot].sum=1;t[tot].fa=now;t[tot].v=v;splay(tot);return;}elseif(t[now].r)now=t[now].r;else{t[now].r=++tot;t[tot].sum=1;t[tot].fa=now;t[tot].v=v;splay(tot);return;}}}intget_lower(inta){splay(a);for(a=t[a].l;t[a].r;a=t[a].r);returna;}intget_upper(inta){splay(a);for(a=t[a].r;t[a].l;a=t[a].l);returna;}intget_rank(inta){splay(a);returnt[t[a].l].sum;}voiddel(intl,intr){l=get_lower(l);r=get_upper(r);splay(l);splay(r,l);t[r].l=0;update(r);update(l);}intget_kth(intk){++k;for(intnow=root;;){if(t[t[now].l].sum==k-1)returnnow;if(t[t[now].l].sum>=k)now=t[now].l;elsek-=t[t[now].l].sum+1,now=t[now].r;}}};
❽ 树的递归算法
答案是正确的啊。
if(root)就是如果root!=0，这里root是一个指针，指向结构体struct node的指针，第一次进入函数它就是指向根节点A的指针
运行步骤：
如果指向A的指针不为空(不为0),打印'A',
递归调用函数指向A的左孩子节点
如果指向B的指针不为空(不为0),打印'B',
递归调用函数指向B的左孩子节点
如果指向C的指针不为空(不为0),打印'C',
递归调用函数指向C的左孩子节点
由于C的左孩子节点为空，所以本次递归traversal(root->lchild)结束，回到上一层递归中即从C的左孩子节点回到C中，然后执行traversal(root->lchild)这一句下面一句，打印出'C'
然后递归调用traversal(root->rchild);指向C的右孩子节点
如果指向E的指针不为空(不为0),打印'E',
然后再递归指向E的左孩子节点，为空再返回到E中，再次打印出'E',然后再指向E的右孩子节点，为空，E的递归结束返回上一层递归即C中，然后C也到达末尾结束返回上一层递归B中，然后执行traversal(root->lchild)这一句下面一句，打印出'B'
然后递归调用traversal(root->rchild);指向B的右孩子节点
......
如此不断进入某个节点的子节点操作后再从子节点返回父节点，层层进入再层层向上返回，从而遍历树中各个节点，最终得出结果：
A B C C E E B A D F F D G G
❾ 平衡二叉树的算法
Size Balanced Tree（简称SBT）是一自平衡二叉查找树，是在计算机科学中用到的一种数据结构。它是由中国广东中山纪念中学的陈启峰发明的。陈启峰于2006年底完成论文《Size Balanced Tree》，并在2007年的全国青少年信息学奥林匹克竞赛冬令营中发表。由于SBT的拼写很容易找到中文谐音，它常被中国的信息学竞赛选手和ACM/ICPC选手们戏称为“傻B树”、“Super BT”等。相比红黑树、AVL树等自平衡二叉查找树，SBT更易于实现。据陈启峰在论文中称，SBT是“目前为止速度最快的高级二叉搜索树”。SBT能在O(log n)的时间内完成所有二叉搜索树（BST）的相关操作，而与普通二叉搜索树相比，SBT仅仅加入了简洁的核心操作Maintain。由于SBT赖以保持平衡的是size域而不是其他“无用”的域，它可以很方便地实现动态顺序统计中的select和rank操作。
❿ 树形结构算法有哪些
你说的是遍历树形结构的算法吧。如果这是一棵不规则的树，可以分为广度和深度搜索。如果是二叉树，一般有三种：先序遍历，中序遍历，后序遍历。如果里面的数据是有规则的存储，如红黑树，根据需要可以有不同的算法。