精华内容
下载资源
问答
  • 平衡二叉树的创建

    2019-05-12 14:40:55
    //AVL树性质:左子树和右子树都是平衡二叉树,且左子树和右子树深度之差绝对值不超过1 #include <stdio.h> #include <stdlib.h> #define LH 1 //左子树高1 #define EH 0 //左、右子树等高 #...

    重点在于指针的运用

    //平衡二叉树又称AVL树
    //AVL树性质:左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1
    #include <stdio.h>
    #include <stdlib.h>
    #define LH 1   //左子树高1
    #define EH 0   //左、右子树等高
    #define RH -1  //右子树高1
    #define TRUE 1
    #define FALSE 0
    typedef int Status;
    typedef int Boolean;
    
    typedef struct BSTNode
    {
        int data;
        int bf;
        struct BSTNode *lchild,*rchild;
    }BSTNode,*BSTree;
    
    int EQ(int a,int b);
    int LT(int a,int b);
    void R_Rotate(BSTree *T);
    void L_Rotate(BSTree *T);
    void LeftBalance(BSTree *T);
    void RightBalance(BSTree *T);
    Status InsertAVL(BSTree *T,int e,Boolean *taller);
    int main()
    {
        BSTree *T;
    	T=(BSTree *)malloc(sizeof(BSTree));
    	*T=NULL;
        
        int e;
        Boolean *taller;
    	taller=(int *)malloc(sizeof(int));
        
        printf("请输入要插入的数--输入0退出:");
        scanf("%d",&e);
        while(e)
    	{
    		InsertAVL(T,e,taller);
    		printf("请输入要插入的数--输入0退出:");
    		scanf("%d",&e);
    	}
        return 0;
    }
    //若在平衡的二叉排序树T中不存在和e有相同关键字的结点,则插入一个数据元素为e的新结点
    //并返回1,否则返回0.若因插入而使二叉排序树失去平衡,则作平衡旋转处理
    //布尔变量taller反映T长高与否
    Status InsertAVL(BSTree *T,int e,Boolean *taller)
    {
        if(!(*T))		//如果是空树,则分配空间,生成根结点
        {
    		BSTree p;
    		p=(BSTree )malloc(sizeof(BSTNode));
            p->data=e;
            p->lchild=p->rchild=NULL;
            p->bf=EH;
            *taller=TRUE;
    		*T=p;
        }
        else
        {
            if(EQ(e,(*T)->data))
            {
                *taller=FALSE;
                return 0;
            }
            if(LT(e,(*T)->data))   //如果小于当前结点,则插入左子树
            {
                if(!InsertAVL(&(*T)->lchild,e,taller))
                    return 0;            //如果左子树插入失败,则结束,如果插入成功,则往下继续
                if(*taller)
                    switch((*T)->bf)
                    {
                        case LH:
                            LeftBalance(T);
                            *taller=FALSE;
                            break;
                        case EH:
                            (*T)->bf=LH;
                            *taller=TRUE;
                            break;
                        case RH:
                            (*T)->bf=EH;
                            *taller=FALSE;
                            break;
                    }
            }
            else
            {
                if(!InsertAVL(&(*T)->rchild,e,taller))
                    return 0;
                if(*taller)
                    switch((*T)->bf)
                    {
                        case LH:
                            (*T)->bf=EH;
                            *taller=FALSE;
                            break;
                        case EH:
                            (*T)->bf=RH;
                            *taller=TRUE;
                            break;
                        case RH:
                            RightBalance(T);
                            *taller=FALSE;
                            break;
                    }
            }
        }
        return 1;
    }
    
    //由于在T的左子树根结点的左子树上插入结点,使T的平衡因子由1增至2而失去平衡
    //则需进行一次右旋
    void R_Rotate(BSTree *T)
    {
        BSTNode *lc;
        lc=(BSTNode *)malloc(sizeof(BSTNode));
    
        lc=(*T)->lchild;
        (*T)->lchild=lc->rchild;
        lc->rchild=(*T);
        (*T)=lc;
    }
    //由于在T的右子树根结点的右子树上插入结点,使T的平衡因子由-1增至-2而失去平衡
    //则需进行一次左旋
    void L_Rotate(BSTree *T)
    {
        BSTNode *rc;
        rc=(BSTNode *)malloc(sizeof(BSTNode));
    
        rc=(*T)->rchild;
        (*T)->rchild=rc->lchild;
        rc->lchild=(*T);
        (*T)=rc;
    }
    void LeftBalance(BSTree *T)
    {
        BSTNode *lc,*rd;
        lc=(BSTNode *)malloc(sizeof(BSTNode));
        rd=(BSTNode *)malloc(sizeof(BSTNode));
    
        lc=(*T)->lchild;
        switch(lc->bf)
        {
            case LH:     //如果左子树是左高,则一定是插入在左子树的左子树才会导致失衡
                (*T)->bf=lc->bf=EH;
                R_Rotate(T);  //因此需要进行右旋
                break;
            case RH:     //如果左子树是右高,则一定是插入在左子树的右子树才会导致失衡
                rd=lc->rchild;    //左子树的右子树
                switch(rd->bf)
                {
                    case LH:       //如果左子树的右子树是左高,则是插入在左子树的右子树的左子树
                        (*T)->bf=RH;  //则旋转后,根结点将会是右高
                        lc->bf=EH; //左子树结点将会是等高
                        break;
                    case EH:        //如果是等高,则
                        (*T)->bf=lc->bf=EH;
                        break;
                    case RH:
                        (*T)->bf=EH;
                        lc->bf=LH;
                        break;
                }
                rd->bf=EH;
                L_Rotate(&(*T)->lchild);
                R_Rotate(T);
        }
    }
    void RightBalance(BSTree *T)
    {
        BSTNode *rc,*rd;
        rc=(BSTNode *)malloc(sizeof(BSTNode));
        rd=(BSTNode *)malloc(sizeof(BSTNode));
    
        rc=(*T)->rchild;
        switch(rc->bf)
        {
            case RH:     //如果右子树是右高,则一定是插入在右子树的右子树才会导致失衡
                (*T)->bf=rc->bf=EH;
                L_Rotate(T);  //因此需要进行左旋
                break;
            case LH:     //如果右子树是左高,则一定是插入在右子树的左子树才会导致失衡
                rd=rc->lchild;
                switch(rd->bf)
                {
                    case LH:
                        (*T)->bf=EH;
                        rc->bf=RH;
                        break;
                    case EH:
                        (*T)->bf=rc->bf=EH;
                        break;
                    case RH:
                        (*T)->bf=RH;
                        rc->bf=EH;
                        break;
                }
                rd->bf=EH;
                R_Rotate(&(*T)->rchild);
                L_Rotate(T);
        }
    }
    int EQ(int a,int b)
    {
    	return a==b;
    }
    int LT(int a,int b)
    {
    	return a<b;
    }
    
    展开全文
  • PAT 甲级 1066 Root of AVL Tree (25 分)平衡二叉树的创建 题目 这题主要考查了平衡二叉树的创建。除此之外还得一直保留二叉树的根节点。 由于此前对于平衡二叉树的创建比较模糊,故结合了严姥姥的教材写一篇博客...

    PAT 甲级 1066 Root of AVL Tree (25 分)平衡二叉树的创建

    题目

    这题主要考查了平衡二叉树的创建。除此之外还得一直保留二叉树的根节点。

    由于此前对于平衡二叉树的创建比较模糊,故结合了严奶奶的教材写一篇博客加深一下自己对于平衡二叉树的创建的印象。

    平衡二叉树概念

    平衡二叉树是一种二叉排序树,将其不断调整为平衡二叉树是为了提高查找的效率。平衡二叉树的递归定义条件是:

    • 对于根节点,其左子树和右子树的高度之差不得超过2,也即只能为0,1 。
    • 这棵树的左子树和右子树也是平衡二叉树。

    为什么说平衡二叉树可以提高查找效率?

    现在我们来创建一颗普通的二叉排序树。输入序列为1,2,3,4,5。

    可以看见上述的二叉排序树的查找复杂度依旧为O(n)O(n),故此种情况下排序树并没有提高查找效率。平衡二叉树的出现就是为了避免这种情况的发生。它通过调整使得最后的树左右子树高度相差不超过2 。从而让查找复杂度始终为O(log2n)O(log_2n)

    平衡二叉树的创建

    平衡二叉树的创建难在调整二叉树这个步骤上。而什么时候需要调整呢?有四种需要调整的情况。(下列图中节点上的数字并非该节点的value值,仅指编号,区分节点)

    1. LL型

      这里的LL中的L指的是Left。也即表示原本该树的左子树就比右子树高1。 这时新插入的节点还插入到了该左子树的左子树上。这时需要以1节点进行右旋

      这样就让二叉树平衡了。

    2. LR型

      这里指的是原本该树的左子树就比右子树高1,这时新插入的节点插入到了该左子树的右子树上。这时复杂一点,需要先以2节点进行左旋,再以1节点进行右旋

      从图中可以看出,先以2节点进行左旋是为了达到LL型的树,再以1节点进行右旋以达到平衡

    3. RR型

      这里指原本该树的右子树就比左子树高1 。这时新插入的节点插入到了改右子树的右子树上,这时只需要以1节点进行左旋即可达到平衡。

    4. RL型

      这里指的是原本该树的右子树就比左子树高1。 这时新插入的节点插入到了改右子树的左子树上,这时需要先以2节点进行右旋,再以1节点进行左旋

    ​ 从图中可以看出,先以2节点进行右旋是为了达到RR型树,在进行左旋。

    知道了上述的调整方法之后再利用递归函数便可完成平衡二叉树建立的代码。

    我们知道,平衡二叉树需要调节平衡,那么必须知道各个节点处的平衡因子,所以平衡二叉树的节点会多一个元素即平衡因子。左右等高时为0 ;左高为1 ;右高为-1 。

    完整代码

    #include <iostream>
    #include <cstdio>
    #include <string>
    #include <algorithm>
    #include <map>
    #include <queue>
    
    #define LH +1 //左高
    #define EH 0  //等高
    #define RH -1 //右高
    
    using namespace std;
    
    typedef struct BSTree {
        int val;
        BSTree *left, *right;
        int balance;//平衡因子
    }BSTree, *TreeNode;
    
    void leftRotate(TreeNode &node) {//左旋
        TreeNode p = node->right;
        TreeNode q = p->left;
        p->left = node;
        p->left->right = q;
        node = p;//记录根节点
    }
    
    void rightRotate(TreeNode &node) {//右旋
    	TreeNode p = node->left;
    	TreeNode q = p->right;
    	p->right = node;
    	p->right->left = q;
    	node = p;//记录根节点
    }
    
    void LeftBalance(TreeNode &node) {//L型调整
    	TreeNode lc = node->left;
    	switch (lc->balance)
    	{
    	case LH://LL型
    		node->balance = lc->balance = EH;
    		rightRotate(node); break;
    	case RH://LR型
    		TreeNode rd = lc->right;
    		switch (rd->balance)//调整平衡因子
    		{
    		case LH:
    			lc->balance = EH; node->balance = RH; break;
    		case EH:
    			lc->balance = EH; node->balance = EH; break;
    		case RH:
    			lc->balance = LH; node->balance = EH; break;
    		}
    		rd->balance = EH;
    		leftRotate(node->left);
    		rightRotate(node);
    	}
    }
    
    void RightBalance(TreeNode &node) {//R型调整
    	TreeNode rc = node->right;
    	switch (rc->balance)
    	{
    	case RH://RR型
    		node->balance = rc->balance = EH;
    		leftRotate(node); break;
    	case LH://RL型
    		TreeNode ld = rc->left;
    		switch (ld->balance)//调整平衡因子
    		{
    		case LH:
    			node->balance = EH; rc->balance = RH; break;
    		case EH:
    			node->balance = rc->balance = EH; break;
    		case RH:
    			node->balance = LH; rc->balance = EH; break;
    		}
    		ld->balance = EH;
    		rightRotate(node->right);
    		leftRotate(node);
    	}
    }
    
    bool InsertNode(TreeNode &root, int val, bool &taller) {//插入节点
        if (!root) {//当前树为空
    	root = (TreeNode)malloc(sizeof(BSTree));
    	root->val = val;
    	root->left = NULL;
    	root->right = NULL;
    	root->balance = EH;
    	taller = true;//树长高了
    	return true;
        }
        if (root->val == val) {//相同的val值不予处理
    	taller = false; return false;
        }
        else if (val < root->val) {//插入的val值小于当前节点,插入左子树
            if (!InsertNode(root->left, val, taller)) {//没有插入
    	    return false;
    	}
    	if (taller) {//只有插入完树长高了才有需要进行调整
    	    switch (root->balance)
    	    {
    	    case LH://原本左高,还插入到了左子树,那么进行L型的调整
    		LeftBalance(root); taller = false; break;
    	    case EH://原本等高,这时插入到了左子树,当前节点平衡因子变为LH,树长高了。
    		root->balance = LH; taller = true; break;
    	    case RH://原本右高,这时插入左子树变高了,说明左右平衡了。但是树并没有变高
    		root->balance = EH; taller = false; break;
    	    }
            }
        }
        else {//插入的值大于当前节点值,插入到右子树
    	if (!InsertNode(root->right, val, taller)) {//没有插入
    	    return false;
    	}
    	if (taller) {//插入后树长高了
    	   switch (root->balance)
    	   {
    	    case LH://原本左子树高,这时右子树插入后变高了,说明平衡了,但是对于当前节点为根节点来讲,树并没有长高
    		root->balance = EH; taller = false; break;
    	    case EH://原本为平衡,这时右子树变高,则对于当前节点为根节点来讲树长高了
    		root->balance = RH; taller = true; break;
    	    case RH://原本就右子树高,这时又插入到了右子树导致右子树变高,那么需要进行R型调整
    		RightBalance(root); taller = false; break;
    	   }
            }
        }
        return true;
    }
    
    void deleteTree(TreeNode n) {//释放树占用的空间
    	if (n)return;
    	deleteTree(n->left);
    	deleteTree(n->right);
    	free(n);
    }
    
    int main() {
    	int n;
    	cin >> n;
    	TreeNode root = NULL;
    	bool taller = true;
    	for (int i = 0; i < n; i++) {
    		int tmp;
    		cin >> tmp;
    		InsertNode(root, tmp, taller);
    	}
    	cout << root->val;
    	deleteTree(root);
    
    	system("pause");
    }
    展开全文
  • 平衡二叉树的创建 第一种情况,需要将2作为根节点,进行顺时针旋转; //平衡二叉树 右旋(顺时针) struct TreeNode *AVL_Right(struct TreeNode *p) { struct TreeNode *q = p -> lchild; p -> lchild =...

    平衡二叉树的创建

    1. 第一种情况,需要将2作为根节点,进行顺时针旋转;
      在这里插入图片描述
    //平衡二叉树 右旋(顺时针)
    struct TreeNode *AVL_Right(struct TreeNode *p)
    {
    	struct TreeNode *q = p -> lchild;
    	p -> lchild = q -> rchild;
    	q -> rchild = p;
    	return q;
    }
    

    2.第二种情况,需要将2作为根节点,进行逆时针旋转;
    在这里插入图片描述

    //平衡二叉树 左旋(逆时针)
    struct TreeNode *AVL_Left(struct TreeNode *p)
    {
    	struct TreeNode *q = p -> rchild;
    	p -> rchild = q -> lchild;
    	q -> lchild = p;
    	return q;
    }
    

    3.第三种情况,首先需要将1作为根节点,进行逆时针旋转,再将2作为根节点,进行顺时针旋转;
    在这里插入图片描述

    //平衡二叉树 左旋右旋(逆时针,顺时针)
    struct TreeNode *AVL_Left_Right(struct TreeNode *p)
    {
    	p -> lchild = AVL_Left(p -> lchild);
    	return AVL_Right(p);
    	
    }
    

    4.第四种情况,首先需要将3作为根节点,进行顺时针旋转,再将2作为根节点,进行逆时针旋转;
    在这里插入图片描述

    //平衡二叉树 右旋左旋(顺时针,逆时针)
    struct TreeNode *AVL__Right__Left(struct TreeNode *p)
    {
    	p -> rchild = AVL_Left(p -> rchild);
    	return AVL_Left(p);
    }
    

    完整代码

    #include<stdio.h>
    #include<stdlib.h>
    
    struct TreeNode
    {
    	char data;
    	struct TreeNode *lchild,*rchild;
    };
    //先序遍历
    void PreNode(struct TreeNode *root)
    {
    	if(!root)
    	{
    		return;
    	}
    	printf("%c ",root -> data);
    	PreNode(root -> lchild);
    	PreNode(root -> rchild);
    }
    //中序遍历
    void MidNode(struct TreeNode *root)
    {
    	if(!root)
    	{
    		return;
    	}
    	MidNode(root -> lchild);
    	printf("%c ",root -> data);
    	MidNode(root -> rchild);
    }
    //后序遍历
    void LastNode(struct TreeNode *root)
    {
    	if(!root)
    	{
    		return;
    	}
    	LastNode(root -> lchild);
    	LastNode(root -> rchild);
    	printf("%c ",root -> data);
    }
    //摧毁树
    void DstrotyTree(struct TreeNode *root)
    {
    	if(!root)
    	{
    		return;
    	}
    	DstrotyTree(root -> lchild);
    	DstrotyTree(root -> rchild);
    	free(root);
    }
    //递归求树高
    int GetTreeHeight(struct TreeNode *root)
    {
    	if(!root)
    	{
    		return 0;
    	}
    	int Lheight  = GetTreeHeight(root -> lchild);
    	int Rheight = GetTreeHeight(root -> rchild);
    	return (Lheight > Rheight ? Lheight : Rheight ) + 1;
    }
    //平衡二叉树 右旋(顺时针)
    struct TreeNode *AVL_Right(struct TreeNode *p)
    {
    	struct TreeNode *q = p -> lchild;
    	p -> lchild = q -> rchild;
    	q -> rchild = p;
    	return q;
    }
    //平衡二叉树 左旋(逆时针)
    struct TreeNode *AVL_Left(struct TreeNode *p)
    {
    	struct TreeNode *q = p -> rchild;
    	p -> rchild = q -> lchild;
    	q -> lchild = p;
    	return q;
    }
    //平衡二叉树 左旋右旋(逆时针,顺时针)
    struct TreeNode *AVL_Left_Right(struct TreeNode *p)
    {
    	p -> lchild = AVL_Left(p -> lchild);
    	return AVL_Right(p);
    	
    }
    //平衡二叉树 右旋左旋(顺时针,逆时针)
    struct TreeNode *AVL__Right__Left(struct TreeNode *p)
    {
    	p -> rchild = AVL_Left(p -> rchild);
    	return AVL_Left(p);
    }
    //递归添加节点
    struct TreeNode *AVL_DiGui_AddNode(struct TreeNode *root,struct TreeNode *p)
    {
    	//插入节点
    	if(!root)
    	{
    		return p;
    	}
    	if(root -> data > p -> data)//左边
    	{
    		root -> lchild = AVL_DiGui_AddNode(root -> lchild,p);
    	}
    	else if(root -> data < p -> data)//右边
    	{
    		root -> rchild = AVL_DiGui_AddNode(root -> rchild,p);
    	}
    	else//相等
    	{
    		return root;
    	}
    	//平衡
    	if(abs(GetTreeHeight(root -> lchild) - GetTreeHeight(root -> rchild)) > 1)
    	{
    		if(root -> data > p -> data)//左边
    		{
    			if(root -> lchild -> data > p -> data)//左左
    			{
    				root = AVL_Right(root);
    			}
    			else if(root -> lchild -> data < p -> data)//左右
    			{
    				root = AVL_Left_Right(root);
    			}
    		}
    		else if(root -> data < p -> data)//右边
    		{
    			if(root -> rchild -> data < p -> data)//右右
    			{
    				root = AVL_Left(root);
    			}
    			else if(root -> rchild -> data > p -> data)//右左
    			{
    				root = AVL__Right__Left(root);
    			}
    		}
    	}
    	return root;
    }
    //创建平衡二叉树
    struct TreeNode *CreatTree(char *str)
    {
    	struct TreeNode *root = NULL;	
    	while(*str)
    	{
    		struct TreeNode *p = malloc(sizeof(*p));
    		p -> data = *str;
    		p -> lchild = p -> rchild = NULL;
    		root = AVL_DiGui_AddNode(root,p);
    		str++;
    	}
    	return root;
    }
    
    int main()
    {
    	char str[128];
    	scanf("%s",str);
    	struct TreeNode * root = CreatTree(str);//创建平衡二叉树
    	printf("先序:");
    	PreNode(root);//先序
    	printf("\n");
    	printf("中序:");
    	MidNode(root);//中序
    	printf("\n");
    	printf("后序:");
    	LastNode(root);//后序
    	printf("\n");
    	int height = GetTreeHeight(root);//递归求树高
    	printf("Tree_Height = %d\n",height);
    	DstrotyTree(root);//摧毁树
    	return 0;
    }
    
    
    展开全文
  • 平衡二叉树的创建和插入 import java.util.Random; public class BalancedBiSearchTree { private BTreeNode root; public BTreeNode getRoot() { return root; } public void setRoot(BTreeNode root) {.....
    平衡二叉树的创建和插入 
    import java.util.Random;
    
    public class BalancedBiSearchTree {
       private BTreeNode root;
    
        public BTreeNode getRoot() {
        return root;
       }
    
        public void setRoot(BTreeNode root) {
        this.root = root;
       }
        public void creatAVL(int[] arr)
        {
            for(int i=0;i<arr.length;i++)
            {
                this.insertAVL(arr[i]);
            }
        }
        public void insertAVL(int target)
        {   
            this.insertAVL(root,target,null);
        }
        public static boolean taller=false;
        public int insertAVL(BTreeNode tempNode,int target,BTreeNode preNode)
        {
            if(tempNode==null)
            {   
                tempNode=new BTreeNode(); tempNode.setValue(target);
                tempNode.setBF(0); taller=true; 
                if(preNode==null) this.setRoot(tempNode);
                else {
                    if(preNode.getValue()>target) preNode.setLeftchild(tempNode);
                    else preNode.setRightchild(tempNode);
                }
            }
            else {
                if(tempNode.getValue()==target) {taller=false; return 0;}
                if(tempNode.getValue()>target)
                {   
                    if(this.insertAVL(tempNode.getLeftchild(), target,tempNode)==0) return 0;
                    if(taller)
                    switch(tempNode.getBF())
                    {
                     case 1:
                         leftBalance(tempNode); taller=false; break;
                     case 0:
                         tempNode.setBF(1);taller=true;break;
                     case -1:
                         tempNode.setBF(0);taller=false;break;
                    }
                }
                else {
                    if(this.insertAVL(tempNode.getRightchild(), target,tempNode)==0) return 0;
                    if(taller)
                    switch(tempNode.getBF())
                    {
                    case 1:
                        tempNode.setBF(0);taller=false;break;
                    case 0:
                        tempNode.setBF(-1);taller=true;break;
                    case -1:
                        rightBalance(tempNode); taller=false;break;
                    }
                }
            }
            return 1;
        }
        public void leftBalance(BTreeNode tempNode)
        {   
            this.searchParent(root, tempNode, null);
            BTreeNode preNode=this.preNode;
            this.preNode=null;
            BTreeNode lc=tempNode.getLeftchild();
            switch(lc.getBF())
            {
            //左左旋转
             case   1:
                 tempNode.setBF(0);lc.setBF(0);
                 this.R_Rotate(tempNode,preNode);break;
             //右左旋转
             case  -1:
                 BTreeNode rd=lc.getRightchild();
                 switch(rd.getBF())
                 {
                   case 1:tempNode.setBF(-1);lc.setBF(0);break;
                   case 0:tempNode.setBF(0);lc.setBF(0);break;
                   case -1:tempNode.setBF(0);lc.setBF(1);break;
                 }
                 rd.setBF(0);
                 this.L_Rotate(lc,tempNode);
                 this.R_Rotate(tempNode,preNode);
            }
        }
        public void rightBalance(BTreeNode tempNode)
        {   
            this.searchParent(root, tempNode, null);
            BTreeNode preNode=this.preNode;
            this.preNode=null;
            BTreeNode rc=tempNode.getRightchild();
            switch(rc.getBF())
            {
            //右右旋转
             case -1:tempNode.setBF(0);rc.setBF(0);
                   this.L_Rotate(tempNode,preNode);break;
             //左右旋转
             case 1:
                   BTreeNode ld=rc.getLeftchild();
                   switch(ld.getBF())
                   {
                   case 1:tempNode.setBF(0);rc.setBF(-1);break;
                   case 0:tempNode.setBF(0);rc.setBF(0);break;
                   case -1:tempNode.setBF(1);rc.setBF(0);break;
                   }
                   ld.setBF(0);
                   this.R_Rotate(rc,tempNode);
                   this.L_Rotate(tempNode,preNode);
            }
        }
        //右旋转
        public void R_Rotate(BTreeNode tempNode,BTreeNode preNode)
        {   
            BTreeNode lc=tempNode.getLeftchild();
            tempNode.setLeftchild(lc.getRightchild());
            lc.setRightchild(tempNode);
            tempNode=lc;
            if(preNode!=null)
            {
                if(preNode.getValue()<tempNode.getValue()) preNode.setRightchild(tempNode);
                else preNode.setLeftchild(tempNode);
            }
            else this.setRoot(tempNode);
        }
        //左旋转
        public void L_Rotate(BTreeNode tempNode,BTreeNode preNode)
        {
            BTreeNode rc=tempNode.getRightchild();
            tempNode.setRightchild(rc.getLeftchild());
            rc.setLeftchild(tempNode);
            tempNode=rc;
            if(preNode!=null)
            {
                if(preNode.getValue()<tempNode.getValue()) preNode.setRightchild(tempNode);
                else preNode.setLeftchild(tempNode);
            }
            else this.setRoot(tempNode);
        }
        public static BTreeNode preNode=null;
        public void searchParent(BTreeNode tempNode,BTreeNode targetNode,BTreeNode preNode)
        {
            if(tempNode!=null)
            {   
                if(tempNode.equals(targetNode))     
                    this.preNode=preNode;
                else {
                    this.searchParent(tempNode.getLeftchild(), targetNode, tempNode);
                    this.searchParent(tempNode.getRightchild(), targetNode, tempNode);
                }
    
            }
        }
        //中序遍历
        public void inOrderVisitBST()
        {   
            this.inOrderVisitBST(root);
            System.out.println();
        }
        private void inOrderVisitBST(BTreeNode tempNode)
        {   
    
            if(tempNode!=null)
            {   
                //System.out.println("111");
                this.inOrderVisitBST(tempNode.getLeftchild());
                System.out.print(tempNode.getValue()+" ");          
                this.inOrderVisitBST(tempNode.getRightchild()); 
            }   
        }
        //先序遍历
        public void preVisitBBST()
        {
            this.preVisitBBST(root);
            System.out.println();
        }
        public void preVisitBBST(BTreeNode tempNode)
        {
            if(tempNode!=null)
            {
                System.out.print(tempNode.getValue()+" ");
                this.preVisitBBST(tempNode.getLeftchild());
                this.preVisitBBST(tempNode.getRightchild());
            }
        }
        public static void main(String[] args)
       {
           int[] arr=new int[10];
           for(int i=0;i<10;i++)
           {
               arr[i]=new Random().nextInt(100);
               System.out.println("arr["+i+"]="+arr[i]);
           }
           BalancedBiSearchTree bbst=new BalancedBiSearchTree();
           bbst.creatAVL(arr);
           bbst.inOrderVisitBST();
           bbst.preVisitBBST();
       }
    }
    
    class BTreeNode
    {
        private int value;
        private BTreeNode leftchild,rightchild;
        private int BF;
        public int getValue() {
            return value;
        }
        public void setValue(int value) {
            this.value = value;
        }
        public BTreeNode getLeftchild() {
            return leftchild;
        }
        public void setLeftchild(BTreeNode leftchild) {
            this.leftchild = leftchild;
        }
        public BTreeNode getRightchild() {
            return rightchild;
        }
        public void setRightchild(BTreeNode rightchild) {
            this.rightchild = rightchild;
        }
        public int getBF() {
            return BF;
        }
        public void setBF(int bF) {
            BF = bF;
        }   
    }
    展开全文
  • C++ 平衡二叉树的创建

    千次阅读 2018-07-14 10:29:36
    创建AVL树过程,主要是在构建二叉树插入每个结点时都要调用一次平衡操作balance函数,而调用balance函数过程中涉及到了求结点高度,求结点的平衡因子,LL、LR、RR、RL旋转操作。(注意每次调用旋转操作时要将...
  • 平衡二叉树(AVL):是一种结构平衡二叉搜索树,即叶节点高度差绝对值不超过1,并且左右两棵子树都是一棵平衡二叉树。它能在O(log n)内完成插入、查找和删除操作,其高度h>logN (N为节点个数)。 二、创建AVL...
  • 平衡二叉树的创建,RR旋转,LL旋转,RL旋转,LR旋转,插入、删除和一些其他操作。 平衡二叉树只是一种特殊的二叉排序树,其左右子树的高度差小于1。 左旋、右旋、左旋后右旋、右旋后左旋的理解:实际就是通过左右...
  • 平衡二叉树的创建过程

    千次阅读 2017-04-15 16:16:04
    {//将X插入AVL树T中,并且返回调整后AVL树 if (!T) {//若插入空树,则新建一个包含节点树 T = (AVLTree)malloc(sizeof(struct AVLNode)); T->Data = X; T->Left = T->Right = NULL; T->Height = ...
  • 在此,主要介绍,AVL的创建,仅仅用层次遍历验证AVL树创建的正确性,想要详细了解,先序,中序,后序和层次遍历,请参考我之前的发布的一篇介绍遍历的博客---- ...amp;gt;先序-中序-后序-层次遍历 ...
  •   第一步:假设3左右子树高度为R3 、那么4左子树高度为L4 = R3+1、4右子...3的平衡因子为 R3-(1+h4) = R3-(1+R3) = -1 4的平衡因子为R3-R3 = 0 第二步:假设3左子树高度为L3、那么右子树高度为R3 ...
  • } //二叉树的创建(添加结点, 构建关系) public void addNode(AVLTreeNode node) { //左子树 if (node.value ) { if (this.leftNode == null) { this.leftNode = node; } else { this.leftNode.addNode(node); } //...
  • 平衡二叉树AVL的创建

    2019-08-24 14:01:02
    ①定义 平衡二叉树:对于二叉树...平衡二叉树的创建在于对于插入节点后,需要对插入之后的树进行维护高度。 维护高度的方法有四种:左旋,右旋,左右旋,右左旋。 树的结构 typedef struct Node *node; struct Node...
  • 平衡二叉树的建立c语言实现。详细的实现了对平衡二叉树的创建。通过这个能很好的理解平衡二叉树及其数据结构
  • 该套代码是博主在学习数据结构的平衡二叉树时总结整理的一套平衡二叉树的代码,包括平衡二叉树的创建,插入,旋转,遍历等一套完善的代码,亲自测试过,代码保证是对的。
  • 具体功能 初始平衡二叉树为空树操作界面给出创建查找插入删除合并分裂六种操作供选择每种操作均提示输入关键字每次插入或删除一个结点后更新平衡二叉树的显示 平衡二叉树的显示采用凹入表现形式 合并两棵平衡二叉树 ...
  • 平衡二叉树查找

    2021-06-19 15:24:39
    平衡二叉树的创建,以及查找算法
  • 平衡二叉树

    2013-06-24 13:08:52
    平衡二叉树操作,创建平衡二叉树,并输出创建的平衡二叉树
  • 平衡二叉树的创建图解过程: AVL树代码实现(java) package com.bingym.temp01.avl; public class AvlTreeDemo { /* * 平衡二叉树:AVL树:是由排序二叉树存在的一些问题导致的 * 它是一颗空树或者左右两个子树的...
  • 创建平衡二叉树 需要辅助函数 创建树结点 计算每个节点高度 计算每个节点平衡因子 插入新节点后对于出现LL,RR,LR,RL型子树处理问题 插入函数 构建一颗AVL平衡二叉树 本文章重点讲解第4个函数(在下文step...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 606
精华内容 242
关键字:

平衡二叉树的创建