二叉树是什么？平衡二叉树是什么

本文目录

• 二叉树是什么
• 平衡二叉树是什么
• 二叉树先根、中根、后根遍历详细访问顺序
• 什么是《平衡二叉树》
• 什么是完全二叉树
• 怎样通过判断左右子树的平衡因子去平衡二叉树
• 平衡二叉树的节点的平衡因子只可能是1 0 -1
• 完全二叉树的定义是什么
• 二叉树的遍历算法
• 二叉树先序遍历,中序遍历,后序遍历

二叉树是什么

二叉树是指计算机科学中每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树常被用于实现二叉查找树和二叉堆。 二叉树是一个连通的无环图，并且每一个顶点的度不大于3。

平衡二叉树是什么

平衡二叉树（AVL）

那对图 1 进行下改造，把数据重新节点重新连接下，图 2 如下：

图 2 可以看到以下特性：

1. 所有左子树的节点都小于其对应的父节点（4，5，6）《（7）；（4）《（5）；（8）《 （9）；

2. 所有右子树上的节点都大于其对应的父节点（8，9，10）》（7）；（6）》（5）；（10）》（9）；

3. 每个节点的平衡因子差值绝对值 《=1；

4. 每个节点都符合以上三个特征。

满足这样条件的树叫平衡二叉树（AVL）树。

问：那再次查找节点 5，需要遍历多少次呢？

由于数据是按照顺序组织的，那查找起来非常快，从上往下找：7-5，只需要在左子树上查找，也就是遍历 2 次就找到了 5。假设要找到叶子节点 10，只需要在右子树上查找，那也最多需要 3 次，7-9-10。也就说 AVL 树在查找方面性能很好，最坏的情况是找到一个节点需要消耗的次数也就是树的层数， 复杂度为 O(logN)

如果节点非常多呢？假设现在有 31 个节点，用 AVL 树表示如图 3：

图 3 是一棵高度为 4 的 AVL 树，有 5 层共 31 个节点，橙色是 ROOT 节点，蓝色是叶子节点。对 AVL 树的查找来看起来已经很完美了，能不能再优化下？比如，能否把这个节点里存放的 KEY 增加？能否减少树的总层数？那减少纵深只能从横向来想办法，这时候可以考虑用多叉树。

二叉树先根、中根、后根遍历详细访问顺序

你可以参考下这个问题
这个是中根遍历的详细过程
http://zhidao.baidu.com/question/89674628.html

理解以后应该能理解前根以及后根的遍历顺序

前根遍历顺序为根-》左子树-》右子树
那个题目前根遍历的顺序为1-2-4-5-3-6-7

后根遍历顺序为左子树-》右子树-》根
此题的后根遍历顺序为4-5-2-6-7-3-1

什么是《平衡二叉树》

平衡二叉树，又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。
常用算法有：红黑树、AVL树、Treap等。
平衡二叉树的调整方法
平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下：
　　⑴
每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；
　　⑵
若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；
　　⑶
判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；
　　⑷
如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或LR型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；
　　⑸
计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。

什么是完全二叉树

完全二叉树(Complete Binary Tree)
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。
叶子结点只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1
二叉树是一类非常重要的树形结构，它可以递归地定义如下：

二叉树T是有限个结点的集合，它或者是空集，或者由一个根结点u以及分别称为左子树和右子树的两棵互不相交的二叉树u(1)和u(2)组成。若用n,n1和n2分别表示T，u(1)和u(2)的结点数，则有n=1+n1+n2 。u(1)和u(2)有时分别称为T的第一和第二子树。
因此，二叉树的根可以有空的左子树或空的右子树，或者左、右子树均为空。
在二叉树中，每个结点至多有两个儿子，并且有左、右之分。因此任一结点的儿子不外4种情况：没有儿子；只有一个左儿子；只有一个右儿子；有一个左儿子并且有一个右儿子。

怎样通过判断左右子树的平衡因子去平衡二叉树

摘要 节点的平衡因子就是那个节点左子树的高度减去右子树的高度，

咨询记录 · 回答于2021-11-02

怎样通过判断左右子树的平衡因子去平衡二叉树

节点的平衡因子就是那个节点左子树的高度减去右子树的高度，

比如A节点的因子就是它左边的子树的高度，这里是3，减去右子树的高度，这里是2，所以=1

对于B节点，左子树高度为1，右边为2，所以1-2=-1就是B节点的平衡因子

关于需要rl型平衡的二叉树，平衡因子是多少？

rr型平衡因子与rl型平衡因子是不是一样的

您好，平衡因子指的是某个节点

rr型和rl型二叉树要根据图来看平衡因子的

我这里有一道题，选自胡学刚2009年6月版的数据结构实验教程的题目：在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为1，右孩子的平衡因子为0。则应做什么型调整以使其平衡。答案是ll

您好，有图片吗？

应该用LR左右型来调整

您稍等

能不能解释一下，准确的填空答案

好，帮您写一下

您好E节点是添加的

节点I的平衡节点变成了2，

就需要进行调整了

首先，最低的不平衡结点是A。若没有C，D结点，只有一个E结点，符合题意，怎样判断是ll还是lr

奥对，最低

抱歉，手指头画不出来有点着急没看到最低

您稍等

ll型是让a作为根节点

将i变成a右孩子

a原来的右孩子是没有的，所以i的左边就没有

a的平衡因子变成了2，还是不平衡的

平衡二叉树的节点的平衡因子只可能是1 0 -1

平衡二叉树的节点的平衡因子只可能是1 0 -1这里的0 1 -1 是说具体的0 -1 和1 ;根结点的平衡因子是指左子树的高度减右子树的高度的值

完全二叉树的定义是什么

完全二叉树的定义是一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同。

从满二叉树和完全二叉树的定义可以看出，满二叉树是完全二叉树的特殊形态，即如果一棵二叉树是满二叉树，则它必定是完全二叉树。

完全二叉树判定

1、如果树为空，则直接返回错。

2、如果树不为空：层序遍历二叉树。

3、如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列。

4、如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树。

5、如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空，且则该节点之后的队列中的结点都为叶子节点，该树才是完全二叉树，否则就不是完全二叉树。

二叉树的遍历算法

这里有二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法。
1.先序遍历非递归算法
#define
maxsize
100
typedef
struct
{

Bitree
Elem[maxsize];

int
top;
}SqStack;
void
PreOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍历左子树
{
visite(p-》data);
push(s,p);
p=p-》lchild;
}//endwhile
if
(!StackEmpty(s))
//通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p-》rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍历非递归算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
InOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍历左子树
{
push(s,p);
p=p-》lchild;
}//endwhile
if
(!StackEmpty(s))
{
p=pop(s);
visite(p-》data);
//访问根结点
p=p-》rchild;
//通过下一次循环实现右子树遍历
}//endif
}//endwhile
}//InOrderUnrec
3.后序遍历非递归算法
#define
maxsize
100
typedef
enum{L,R}
tagtype;
typedef
struct
{
Bitree
ptr;
tagtype
tag;
}stacknode;
typedef
struct
{
stacknode
Elem[maxsize];
int
top;
}SqStack;
void
PostOrderUnrec(Bitree
t)
{
SqStack
s;
stacknode
x;
StackInit(s);
p=t;
do
{
while
(p!=null)
//遍历左子树
{
x.ptr
=
p;
x.tag
=
L;
//标记为左子树
push(s,x);
p=p-》lchild;
}
while
(!StackEmpty(s)
&&
s.Elem[s.top].tag==R)
{
x
=
pop(s);
p
=
x.ptr;
visite(p-》data);
//tag为R，表示右子树访问完毕，故访问根结点
}
if
(!StackEmpty(s))
{
s.Elem[s.top].tag
=R;
//遍历右子树
p=s.Elem[s.top].ptr-》rchild;
}
}while
(!StackEmpty(s));
}//PostOrderUnrec

二叉树先序遍历,中序遍历,后序遍历

从前序的第一个结点开始确定根，中序决定左子树和右子树，如第一个结点A，根据中序可知，A的左子树是DBE，右子树是FC，再从前序中确定第二个根B，根据中序可知B的左子树是D，右子树为E，依次重复执行，直到遍历完所有结点。所以后序遍历DEBFCA