[新手程序员]Avl树旋转代码问题

bool BiNode::LR_Balance(BiNode** T)
{
BiNode* tempNode = (*T)->lchild->rchild;
BiNode* p = (*T)->lchild;
if (tempNode == NULL)
return false;
/* 处理tempNode的子树 /
(*T)->lchild->rchild = tempNode->lchild;
(*T)->lchild = tempNode->rchild;
/
将子树根节点和根节点的有节点连接掉tempNode */
tempNode->lchild = p;
tempNode->rchild = (*T);

(*T) = tempNode;//改变了T的父节点的孩子指针的指向,从指向T变成指向tempNode
return true;

}
(*T) = tempNode;

逐行运行时发现这一行代码使T的父节点指T的指针变成了指向tempNode当前节点。

然后我又写了下面的程序,结果并没有改变。
int main()
{
BiNode* BST1= new BiNode();
BiNode* BST2 = new BiNode();
BiNode* BST3 = new BiNode();
bool change(BiNode** T);

BST1->data = 59;
BST2->data = 33;
BST3->data = 13;
BST1->lchild = BST2;

change(&BST2);
BST1->PreOrderTraverse(BST);
cout << endl;

}
bool change(BiNode** T)
{
BiNode* BST3 = new BiNode();
BST3->data = 13;
(*T) = BST3;
return true;
}
二级指针能不能这么用?如果可以,后面那个为什么不行?
如果不行,二级指针是用来做什么的 。

如果二级指针能这么用,该怎么理解?
一般说指针指向地址,可以理解为指向一个固定的内存单元吗,这个内存单元的地址也是固定的。只有这样假设我才能想明白第一个程序为什么有效果

1个回答

你在函数里new了一个结构体,还不是静态的,函数调用完它就“消失”(实际上是程序不会将这个变量的值保持住,可能又变成别的值)了

你应该了解一下函数调用的过程

局部变量是保存在栈上的,函数调用返回时会移动栈指针,然后这片区域可能随后又保存了别的东西,原来的数据是不会保存下来的

CSDN4006600
csdn4006600 完全没有想过是这里的问题,一直在查二级指针的用法。谢谢
接近 2 年之前 回复
Debug_dodge
Debug_dodge 搜索一下变量的作用域,以及static/dynamic关键字
接近 2 年之前 回复
Debug_dodge
Debug_dodge 最怕的就是自己在这里猜想程序是怎么运行的,你上网搜索一下花不了多少时间的
接近 2 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
AVL树旋转的问题
以单右旋为例:rnvoid RotateRight(BT &p) //p为左右子树深度为2的点rnrn BT t;rn t=p->left;rn p->left=t->right;rn t->right=p;rn p=t;rnrnrn我们假设p没有旋转前的父结点为q(且加入p是q的左孩子);rnrn我的问题是:在旋转之后,会有两个节点指向p,一个是q,一个是trnrn查了好多代码都没说到这个问题,是不是应该加一步 q->left=t;rn
平衡二叉树(AVL树,AVL树旋转)
1、平衡因子(BF):BF = HL - HR(其中HL和HR分别是左子树和右子树的高度)。2、平衡二叉树(AVL树):对于任一结点,左右子树的高度差的绝对值是小于1。 即 |BF|<=1。例:1、 对于3这个结点来讲,左子树高度为2,右子树高度为0,左右子树高度差为2,2>1,所以该树不是平衡二叉树。2、 对于这个树里面的每一个结点来讲,左右子树的高度差都小于等于1,所以
AVL树的旋转平衡
AVL树的旋转平衡 练习实例:1依据字典序,按照AVL树插入算法依次插入{head,he,tea,teach,twin,hot,toss}。关键:插入twin时,属于&quot;\&quot;型;插入hot时,属于&quot;&amp;gt;&quot;型。2按AVL插入算法依次插入{55, 31, 11, 37, 46, 73, 63}。关键:插入11时,属于“/”型;插入46时,属于&quot;&amp;lt;&quot;型;插入73时,属于&quot;\...
AVL树(旋转问题详解)
二叉搜索树给我们了一个搜索一个点的方法,同时,也将二叉树中的节点排序了,但是,对于一些特殊的二叉树来说,使用二叉搜索树会很费空间,比如说:左单支的这种情况,你说是二叉树,还不如说是单链表呢,还节省了一大波的空间呢(右指针域),同样的,对于右单支的情况也是如此,那么现在我们就要想能不能避免这个问题。可以,一个平衡因子就可以搞定,加了平衡因子,那么这颗二叉搜索树就是AVLTree了那么现在我们就来分析一
AVL树的插入与旋转
定义 AVL树本质上是一颗二叉查找树,但是它又具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 插入与旋转 单旋 LL型 在根结点的左子树的左子树上插入节点。 RR型 在根结点的右子树的右子树上插入节点。 解决方法 双旋 LR型 在根结点的左子树的右子树上插入节点。 RL型 在根结点的右子树的左子树...
平衡二叉树之AVL树的旋转
平衡二叉树是基于二叉排序树(或者也叫二叉搜索树)实现的一种自平衡的二叉树,实现方法有比如:AVL树、红黑树等等 二叉搜索树定义(维基百科): 二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sorted binary tree),是指一棵空树或者具有下列性质的二叉树: 1.若任意节点的左子
AVL树的旋转操作
首先,在讨论AVL树之前,我们得明白一点,那就是为什么得有AVL树? AVL树与二叉搜索树一样都是用于搜索的二叉树,也可以这么说AVL树是特殊的二叉搜索树,它与二叉搜索树的主要区别在于AVL树中给定了平衡因子(左右子树的高度差),而且明确规定,平衡因子最大不能超过1,最小不能小于-1,因此我们的AVL树中左右子树的高度差只能为0,1,-1,也就是说不会出现一段较长的单支的情况,而对于二叉搜索树而言,单支树的情况完全可能出现。 而对于单支树这种情况,我们对于其的搜索就相当于对一个单链表进行搜索,时间复杂度由原
AVL(平衡)树的旋转
在二叉搜索树中,可能会存在几种特别的情况,即左单支、右单支之类的情况,这样的情况在二叉搜索树中查询某个节点代表的内容时,依旧会达到O(N)的时间复杂度,而不能按预期达到O(lgN)的时间复杂度。   所以在树中旋转树的结构,将树调整为一个满足条件的树–AVLTree(平衡树),即右子树的高度减去左子树的高度的绝对值小于2。为了达到AVL树,有四种基本情况,所以对应四种旋转方式,左单旋,右单旋,右左
AVL树的旋转详解
       二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素也就相当于是在顺序表中搜索元素,效率低下。因此,为了解决二叉搜索树中单支树的这种情况,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了AVL(平衡树):当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差(平衡因子)的绝对值不超过1(...
AVL树的旋转!
对于AVL树的旋转不是很明白,单旋转还好,双旋转就搞不懂什么规律了!高手们给说下规律吧,或贴个连接什么的!
AVL树的旋转
通常,我们在平衡二叉树进行插入和删除的时候常常会破坏平衡二叉树,所以我们必须通过一种方法来再次平衡二叉树使之成为平衡二叉树,这种办法就是旋转。 旋转可以分为四种,分别为: 1.左单旋转 2.右单旋转 3.先左后右双向旋转 4.先右后左双向旋转 接下来我们去分析这四种旋转并且依次用代码实现 1.左单旋转 旋转过程:     在原有的平衡树中插入20这个节点,导致不平衡,通过旋转
AVL树旋转及代码实现
    AVL树是带有平衡条件的二叉查找树,它允许每个节点的左子树与右子树的高度差未1。这样的平衡树深度是O(log N)。而要维持这种平衡,就必须在每次对AVL树删除节点或新增节点后,检查AVL树的平衡是否被打破,即是否存在节点的左右子树高度差大于1,在判断AVL树失去平衡后,就必须旋转失去平衡的节点,已再次达到平衡。AVL树旋转:    旋转的目的就是减小树的高度,节点未空时,节点的高度未-1...
AVL树的旋转和插入
包含了AVL树的单旋转和双旋转的算法,以及AVL树的递归插入和非递归插入算法。单旋转也叫“一”字形旋转,又可分为左-左型旋转和右-右型旋转;双旋转也叫“之”字形旋转,又可分为左-右型旋转和右-左型旋转。 #includeiostream> #includestack> using namespace std; class AVLNode{ public: int element;
AVL树的平衡化旋转
左单旋:右单旋: 左右双旋: 右左双旋:
平衡二叉树中的AVL树的旋转
树的旋转字树的根节点向下进行,且在子树的重挂载时,将较浅的一棵树挂到另一边。
jquery插件-自动布局-masonry
  示例:
显示旋转过程的AVL树
这是我第一次在csdn上面写博客。以前遇到不会的问题时,csdn总有一片博文能为我解惑,今天我也打算上传一些代码来为这个社区做贡献。笔者不才,代码常有纰漏之处,愿有幸读到这篇博文的同学不吝赐教。 下面的代码是一颗AVL树的插入代码,随着插入的进行,树会根据左右子树的高度来进行调整,并且会把步骤显示出来,不过步骤的显示并没有独立做成函数,而是嵌在代码中,这在一定程度上影响了程序的可读性,读者可以先
数据结构-----AVL树的旋转操作
本文主要讲解AVL的旋转操作,供自己复习用,如有不对之处请指出。另外图片是从链接处的大神那复制的,感觉文章写的很好,可以去学习。 http://www.cnblogs.com/QG-whz/p/5167238.html具体内容可以参考链接处的讲解。 AVL树定义:一颗空的二叉树是AVL树;如果T是一棵非空的二叉树,TL和TR分别是其左子树和右子树,那么当T满足以下条件时,T是一棵AVL
AVL树旋转图形记录
AVL树旋转图形记录
AVL树平衡旋转详
https://blog.csdn.net/howardemily/article/details/79543892 本文整理的很好,不搬了
AVL树旋转的一点理解
AVL树的定义: 每一个节点的子树都是一棵AVL树; 每一个节点的左右子树的高度差不超过1 图示说明:圈代表树的节点,三角形代表子树,编号按值的大小进行排序。 以下讨论基于的前提:从图示的最顶层的节点开始平衡才被打破,它的子树都是平衡的。 本身这个前提在代码实现时也是可以保证的,正常我们在插入一个树节点时都是从root开始层层遍历直到找到节点可插入的地方。由于节点的新插入
avl树的基本概念与节点旋转
基本概念avl树也是一颗二叉搜索数,所以也遵循二叉搜索树的定义,根节点的左子树永远比节点小,右子树永远比节点大。 - 树深根节点的最大的层次 平衡因子 某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子(BF,Balance Factor)。 平衡二叉树上所有结点的平衡因子只可能是 -1,0 或 1。否则这棵树就是不平衡的。 旋转 节点的平衡因子大于1或者小于-1的时候就要对节点进行旋
平衡二叉树(AVL树)的平衡旋转
在复习DS的查找时,为了弄明白平衡旋转,搜了一下,发现四张不错的图,觉得比课本的图做得好,分享一下。看这些图的时候,注意A、B、C三个结点的变化。 LL旋转 RR旋转 LR旋转 RL旋转
AVL树的单双旋转解析
【0】README0.0) 本文部分idea 转自:http://blog.csdn.net/collonn/article/details/20128205 0.1) 本文专注于 解析 AVL 树的 单旋转(左左单旋转和右右单旋转) 和 双旋转(左右双旋转和右左单旋转)的内部核心技巧(历时一天吧,估计); 0.2) 不得不提的是, 旋转有两个属性: 轴 和 旋转方向;【1】 如何判断进行单
AVL树的插入与旋转算法解析
1、AVL树的基本概念:AVL树又称为平衡二叉排序(搜索)树,AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis,他们在 1962 年的论文 “An algorithm for the organization of information” 中发表了它。分解开来看:AVL树是一棵二叉树进一步是一棵二叉排序树、并且AVL树涉及平衡因子这个概念。节点的平衡因子
AVL树的旋转与插入操作
AVL树是一种最原始的二叉查找树,它的各个节点的左右子树高度不超过1,因此能保证树的高度最大值为Olog(N),从而大大提高查找、插入、删除等操作的效率。在插入和删除元素时通过旋转操作使得AVL保持原有特性。本文给出了AVL树四种旋转操作和插入操作的C语言程序。 四种旋转操作参考《数据结构与算法分析——C语言描述第二版》。 插入操作则是在BST树查找函数框架的基础上进行改进,如果插入完成后AV
AVL树 四种旋转的场景
以下图的平衡因子统一为左子树高度减去右子树高度。 1 左单旋 (右右 - 在较高右子树的右侧插入节点)     附上:单个节点声明的代码 struct AVLTreeNode { AVLTreeNode(const K& key, const V& value) : _pLeft(NULL) , _pRight(NULL) , _pParent(NULL) , _key(key)
AVL树的旋转、插入、 详解
AVL树或者空树,或者它的左右子树的高度之差的绝对值不超过1;详情的平衡因子请看小编上篇博客。 AVL的平衡旋转可是转晕了不少同学啊,其实理清思路还是很简单的,那么小雷同学就开始show time! **************************************************************************************************
【AVL树】AVL树的插入操作以及旋转
在讲解AVL树之前必须了解二叉搜索树, 可以看我之前的博客:二叉搜索树AVL树是在二叉搜索树的基础上,在向二叉树排序树中插入新的结点,如果保证每个结点的左右子树的高度差的绝对值不超过1,即需要在插入的时候判断是否满足条件,然后对树进行旋转,从而可减低树的高度,减少平均搜索长度。AVL树:(1)它的左右子树都是AVL树 (2)右子树和左子树的高度差(平衡因子)的绝对值不能
AVL树完整代码
avl树代码,欢迎大家学习交流
AVL 旋转
[code=C/C++]rnNode_t RightRotate(Node_t a) rn b = a->left;rn a->left = b->right;rn b->right = a;rn a->height = Max(Height(a->left), Height(a->right));rn b->height = Max(Height(b->left), Height(b->right));rn return b;rnrn[/code]rnrn上面是AVL 的LL 旋转操作,小弟 看不明白, 请高手解释下。
AVL tree AVL树
AVL tree AVL树 完全平衡树基本操作
AVL树自平衡的几种旋转
标注: AVL树的基本题,仔细想想动手画画RS, LS,LRS,RLS!!code 04-树5 Root of AVL Tree   (25分) An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node
AVL树的四种旋转--初步解析
> AVL树也叫作平衡树,它的每个节点 都有平衡因子: 平衡因子=右子树的高度-左子树的高度 AVL树的性质: 平衡因子大小为(-2,2),即-1,0,1 当一个节点插入后可能导致AVL树的不平衡,因此需要经过旋转,让这棵树满足AVL树的性质: 一共有四种旋转方式,分别对应插入节点后的四种情况: 1.左单旋: 2.右单旋: 3.左右双旋: 先进行左单旋,再进行右单旋
AVL树的旋转的一点新理解
题目 Click the AVL tree that results when 5, 3, 2, 6, 8, 9, 10, 17, 15, 14, 12 are inserted, in that order, into an initially empty tree. 解题过程如下(字丑,方框表示异常点): 在完成此题时,由于对AVL树的重平衡不熟悉,参考了网上一些文章,对AVL的旋转有了新的...
AVL树的插入与删除,重点是四种旋转
本文不是入门篇,零基础请绕过。 先用维基上的话来介绍一下基本概念。        在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G.M. Adelson-Velsky和E.M.
数据结构:关于AVL树的平衡旋转详解
前言 本文是基于你已经有一定的二叉排序树知识。如果你还是小白,可以参考我之前的博客:《数据结构:二叉搜索树(BST)的基本操作》。所以,在本文中不会再出现关于BST树的基本知识。 版权说明 著作权归作者所有。 商业转载请联系作者获得授权,非商业转载请注明出处。 作者:Q-WHai 发表日期: 2015年12月28日 链接:https://qwhai.blog.csdn.net/ar...
【数据结构】AVL树及平衡化旋转
   二叉搜索树可以缩短查找的效率,但是如果数据有序或接近有序时二叉搜索树将退化为单支树,查找效率将会下降。因此,我们通过向二叉搜索树种插入结点后,保证左右子树的高度之差的绝对值不超过1来调节结点,降低树的高度。 一. AVL树概念:   一颗AVL树是一颗空树或者具有如下性质的二叉搜索树: 1.它的左右子树都是AVL树; 2.左子树和右子树高度之差(简称平衡因子)的绝对值不超过1; ...
AVL树的基本旋转和调平
AVL树的基本旋转和调平    概念:什么是AVL树,简单的来说,就是一颗排序并且是高度平衡的一棵二叉树。    那么二叉树是怎么做到的呢?肯定是不断的插入不断调节。    结构: struct AVLNode { AVLNode *parent; AVLNode *leftchild; AVLNode *rightchild; int balance;
AVL树的插入以及四种旋转解析
什么是AVL树呢?(概念)一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:1、它的左右子树都是AVL树2、左子树和右子树高度之差(简称平衡因子)的绝对值不超过1(-1、0、1)3、如果一棵二叉搜索树是高度平衡的,它就是AVL树。4、时间复杂度:如果它有n个结点,其高度可保持在O(lgn),平均搜索时间复杂度O(lg(n))首先,创建AVL树template&amp;lt;class K, clas...
相关热词 c#检测非法字符 c#双屏截图 c#中怎么关闭线程 c# 显示服务器上的图片 api嵌入窗口 c# c# 控制网页 c# encrypt c#微信网页版登录 c# login 居中 c# 考试软件