樹的相關演算法
❶ 二叉樹演算法
二叉樹是沒有度為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操作。
❿ 樹形結構演算法有哪些
你說的是遍歷樹形結構的演算法吧。如果這是一棵不規則的樹，可以分為廣度和深度搜索。如果是二叉樹，一般有三種：先序遍歷，中序遍歷，後序遍歷。如果裡面的數據是有規則的存儲，如紅黑樹，根據需要可以有不同的演算法。