二叉树之BST、AVL和RBT
二叉查找树(Binary Search
Tree)是满足如下性质的二叉树：①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；③左、右子树本身又各是一棵二叉查找树。
通俗的讲，二叉查找树的左子树上的结点不比父结点大，右子树上的结点不比父结点小，即，设x为二叉查找树中的一个结点，如果y是x的左子树中的一个结点，则key[y]&=key[x]；如果y是x的右子树中的一个结点，则key[x]&=key[y]。此处的key[x]，key[y]表示的是x结点和y结点的关键字。
1.最小关键字元素：要查找二叉查找树中具有最小关键字的元素，只要从根节点开始，沿着各节点的left指针查找下去，直到遇到NULL为止。查找最大关键字元素情况类似。
&&& TREE-MINIMUM
while left[x] ≠ NULL
← left[x]
2.后继：如果所有的关键字均不相同，则某一结点x的后继即是具有大于key[X]中的关键字中最小者的那个结点。查找结点X的后继包含两种情况（1）如果结点X的右子树非空，结点X的后继即是右子树中具有最小关键字的结点。（2）如果结点x的右子树为空，且假设结点X的后继为Y，则Y是X的最低祖先结点，且Y的左孩子是X的祖先。前驱的情况类似。
TREE-SUCCESSOR(x)
right[x] ≠ NULL
return TREE-MINIMUM (right[x])
&&& 3 y ←
while y ≠ NULL and x =
下面是后继的C++实现：
&3.插入：根据二叉查找树的性质，我们先将要插入的元素跟根元素，如果大于根结点的key，则插入到其右子树中，如果小于根结点的key值，则插入到其左子树中。
4.删除：将给定结点Z从二叉查找树中删除的过程是以指向Z的指针作为参数。删除步骤分为三种：
(1)如果Z没有子女，则修改其父节点P[Z]，使NULL为其子女，替换Z。
(2)如果结点只有一个孩子，则通过在其子节点与父节点之间建立一条链来删除Z。
(3)最后若Z有两个子女，先删除Z的后继Y（后继Y没有左孩子，注意这时真正删除的是结点Y），再用Y的内容替换Z的内容。
TREE-DELETE(T, z)
left[z] = NULL or right[z] = NULL
else y ← TREE-SUCCESSOR(z)
left[y] ≠ NULL
x ← left[y]
else x ← right[y]
p[x] ← p[y]
p[y] = NULL
& then root[T] ← x
&&& 11 else
if y = left[p[y]]
& then left[p[y]] ←
else right[p[y]] ← x
& then key[z] ←
copy y's satellite data into z
=======================================&&
========================================
一棵AVL树是一棵平衡树，除了二叉查找树的性质外，还有这个性质：它的左子树和右子树都是AVL树，且左子树和右子树的高度之差的绝对值不超过1。这个性质保证了N个元素的AVL树的高度总为LogN，所以它查找的最坏复杂度仍然是LogN，所以说它是一种严格平衡的二叉查找树。
下面是一个Flash做的动态模拟AVL树上结点的插入与删除的过程，非常有趣，对了解AVL树也非常有用：/DataStructures/Trees/AVL/AVLTree.swf
如果在一棵原本是平衡的AVL树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。平衡化旋转有两类：单旋转（左旋和右旋）和双旋转（左平衡和右平衡）。下面先依次介绍旋转的方法。
1．左单旋转(rotate left)：
适用情况：见下图。在A的右孩子B的右子树C上插入结点，使得A结点的平衡因子从﹣1变成﹣2，需要对A进行一次左单旋转。（其中A平衡因子为left[A]-&height -
right[A]-&height）
方法：以A的右孩子结点B为轴，节点A逆时针旋转，成为节点B的左儿子，节点B原左子树成为节点A的右子树。
下面是左单旋转的C++实现：&
2．右单旋转(rotate right)：
适用情况：在C的左孩子B的左子树A上插入结点，使得C结点的平衡因子从1变成2，需要对C进行一次右单旋转。
方法：以C的左孩子结点B为轴，节点C顺时针旋转，成为节点B的右儿子，节点B原右子树成为节点C的左子树。
先左后右双旋转（rotation left
适用情况：见下图。在C的左孩子A的右子树B上插入结点，使得C结点的平衡因子从1变成2，需要对C进行先左后右双旋转。
方法：以C的左孩子A的右孩子B为轴，将节点A逆时针旋转，成为节点B的左儿子，现在C的左孩子为B(上述过程完成左旋转)；以C的左孩子B为轴，将节点C顺时针旋转，成为节点B的右儿子(上述过程完成右旋转)。
先右后左双旋转（rotation right
适用情况：在A的右孩子C的左子树上B插入结点，使得A结点的平衡因子从-1变成-2，需要对A进行先右后左双旋转。
方法：的右孩子C的左孩子B为轴，将节点C顺时针旋转，成为节点B的右儿子，现在A的右孩子为B(上述过程完成；以A的右孩子B为轴，将节点A逆时针旋转，成为节点B的左儿子(上述过程完成右旋转)。
树的插入操作与BST相同，插入后从插入结点到根节点从下到上依次检查该路径上各个结点的平衡度，按照四种情况，做出对应的旋转。
AVL树的删除操作：首先定位要删除的节点。
(1)如果该节点有左孩子，则用左子树的最大结点替换替换该节点,替换后递归删除左子树的最大结点;
(2)如果该节点没有左孩子有右孩子，则用右子树的最小结点替换替换该节点,替换后递归删除右子树的最小结点；
(3)如果该节点没有孩子，则删除该结点。
======================================= 红黑树
========================================
红黑树的定义也是它的性质，有以下五条：
性质1. 节点是红色或黑色
性质2. 根是黑色
性质3. 所有叶子都是黑色（叶子是NULL节点）
性质4. 如果一个节点是红的，则它的两个儿子都是黑的
性质5. 从任一节点到其叶子的所有简单路径都包含相同数目的黑色节点。
插入：红黑树结点的插入与二叉查找树基本一样，不一样的是红黑树把新插入的结点标记为红色，如果新插入的结点的父节点也为红色，那么就按照下面三种情况，做出调整，以维护红黑树的性质4或是2。新插入的结点为N，N的叔叔结点为U。实际情况应该有六种，下面的三种情况中P都是G的左孩子，当P是G的右孩子时，处理方法类似，旋转的方向相反。
(1)N的叔叔U为红色：将N的父节点P[N]与U标记为黑色，将P[P[Z]]标记为红色，然后把P[P[Z]]当做新插入的结点，往上循环调整。
(2) N的叔叔U是黑色的，而且N是右孩子：将P[N]做一次左旋，使P[N]成为N的左孩子，并将旋转前的P[N]作为新插入的结点N。这样情况(2)就转化成了情况(3)。
下面是红黑树插入操作的C++实现(截图部分只有上面三种情况)：
删除：红黑树结点的删除与二叉查找树基本一样，不一样的是如果删除的结点是黑色，则破坏了红黑树的性质5，需要调整，如果删除的结点是红色，那么就不需要调整。现在假设删除结点的孩子为N，如果N是红色的，那么直接将N调整成黑色就能维持红黑树的性质。否则的话，按下面的四种情况处理。实际情况应该有八种，下面的四种情况中N都是其父节点P的左孩子，当N是P的右孩子时，处理方法类似，旋转的方向相反。
(1)N的兄弟S是红色：改变P和S的颜色，对P进行一次左旋转，这样情况(1)就转换成了情况(2)、(3)、(4)；
(2)N的兄弟S是黑色，而且S的两个孩子都是黑色：将S改成红色，将P为新的X循环处理；
(3) N的兄弟S是黑色，而且S的左孩子SL是红色，S的右孩子SR是黑色：改变SL与S的颜色，并对S进行一次右旋转，这样情况(3)就转化成了情况(4)
c++完整实现：
二叉查找树：
&&&&红黑树：
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。C++一个小程序求解啊，判断两棵二叉树是否相似？_百度知道
C++一个小程序求解啊，判断两棵二叉树是否相似？
//typedef意思啊typedef struct btnode{
struct btnode*lchild,*
}typedef bitnode*
//句意思int like(bitree b1,bitree b2)//b1b2类型参数啊{
int like1,like2;
if(b1==NULL&&b2==NULL)
if(b1==NULL||b2==NULL)
like1=like(b1-&lchild,b2-&lchild);/*判断两棵二叉树左树否相等*/
like2=like(b1-&rchild,b2-&rchild); //赋值给like1 like2 值啊
return(like1&&like2);
提问者采纳
typedef int elemtype 意思int取别名名称比elemtype a
a 两用原自定义使用比较便查c++ 基本语typedef bitnode*bitree句同bitnode 自定义类型所b1b2bitnode类型即自定义类型c++面面向象语言原自定义类型看些基本书《c++ primer 》懂看至于面用递归树形结构本种递归结构建议看看递归使用溯
提问者评价
其他类似问题
为您推荐：
二叉树的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁1019人阅读
c/c++（129）
判断完全二叉树：
完全二叉树，除最后一层外，每一层上的节点树都达到了最大值；在最后一层上只缺少右边的若干节点！
算法思路：
按层次（从上到下，从左到右）遍历二叉树，当遇到一个节点的左子树为空时，则该节点右子树必须为空，且后面遍历的节点左
右子树都必须为空，否则不是完全二叉树。
bool IsCompleteBTree(BTree* pRoot)
if (pRoot == NULL)
queue&BTree *&
q.push(pRoot);
bool mustHaveNoChild =
bool result =
while (!q.empty())
BTree* pNode = q.front();
if (mustHaveNoChild)//如果一个节点没有子节点;只要出现了空子树的节点，后面出现的必须为叶子节点（左字树右子树必须为空）
if (pNode-&m_nLeft != NULL || pNode-&m_nRight != NULL)
if (pNode-&m_nLeft != NULL && pNode-&m_nRight != NULL)
q.push(pNode-&m_nLeft);
q.push(pNode-&m_nRight);
else if (pNode-&m_nLeft != NULL && pNode-&m_nRight == NULL)
mustHaveNoChild =
q.push(pNode-&m_nLeft);
else if(pNode-&m_nLeft == NULL && pNode-&m_nRight != NULL)
mustHaveNoChild =
完整测试代码：
// IsCompleteBTree.cpp : 定义控制台应用程序的入口点。
#include &stdafx.h&
#include &iostream&
#include &queue&
//节点的数据结构
class BTree
BTree(int value)
m_nValue =
//二叉树的插入实现
void Insert(int value, BTree* &root)
if (root == NULL)
root = new BTree(value);
else if(value & root-&m_nValue)
Insert(value,root-&m_nLeft);
else if(value & root-&m_nValue)
Insert(value,root-&m_nRight);
bool IsCompleteBTree(BTree* pRoot)
if (pRoot == NULL)
queue&BTree *&
q.push(pRoot);
bool mustHaveNoChild =
bool result =
while (!q.empty())
BTree* pNode = q.front();
if (mustHaveNoChild)//如果一个节点没有子节点;只要出现了空子树的节点，后面出现的必须为叶子节点（左字树右子树必须为空）
if (pNode-&m_nLeft != NULL || pNode-&m_nRight != NULL)
if (pNode-&m_nLeft != NULL && pNode-&m_nRight != NULL)
q.push(pNode-&m_nLeft);
q.push(pNode-&m_nRight);
else if (pNode-&m_nLeft != NULL && pNode-&m_nRight == NULL)
mustHaveNoChild =
q.push(pNode-&m_nLeft);
else if(pNode-&m_nLeft == NULL && pNode-&m_nRight != NULL)
mustHaveNoChild =
int _tmain(int argc, _TCHAR* argv[])
BTree* m_pRoot = new BTree(5);
Insert(6,m_pRoot);
Insert(3,m_pRoot);
Insert(4,m_pRoot);
Insert(2,m_pRoot);
cout&&&是否是完全二叉树：&&&IsCompleteBTree(m_pRoot)&&
getchar();
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：119313次
积分：3096
积分：3096
排名：第6725名
原创：186篇
评论：36条
欢迎吹水！！！
阅读：3939
文章：20篇
阅读：17263
(2)(2)(1)(4)(5)(10)(2)(20)(52)(39)(18)(17)(15)(4)(3)判断二叉树是否为满二叉树 （C++描述）_百度知道
判断二叉树是否为满二叉树 （C++描述）
#include&iostream&#include&math.h&#define TURE 1#define FALSE 0template&class T&class BTNode{ friend BTree&T&; public:
BTNode(){LChild=0;RChild=0;}; private:
BTNode&T& *LChild,*RC};template&class T&class BTree{ public:
BTree(){root=0;};
bool Judge(BTNode&T& *t)
int Height(BTNode&T& *t)
int NodesNum(BTNode&T& *t) private:
BTNode&T& *};template&class T&bool BTree&T&::Judge(BTNode&T& *t){ int h=Height(t); int n=NodesNum(t); if(n==pow(2,h)-1)
return TURE; else
return FALSE;}int BTree&T&::Height(BTNode&T& *t){ if(!t) return 0; int hl=Height(t-&LChild); int hr=Height(t-&RChild); if(hl&hr) return ++ else return ++}template&class T&int BTree&T&::NodesNum(BTNode&T& *t){ if(!t)
return 0; int numl=NodesNum(t-&LChild); int numr=NodesNum(t-&RChild); return numl+numr+1;}int main(){ BTree&int& *t; t.Judge(); return 0;}没构造二叉树步骤写判断二叉树否满二叉树 哪错误
倒觉太麻烦道初三题用做满二叉树结点数定2n-1直接判断行
就是要求写算法呢？
其他类似问题
为您推荐：
满二叉树的相关知识
其他1条回答
非确逻辑清晰
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁二叉树_百度百科
在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。
二叉树定义
二叉树在图论中是这样定义的：二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。
二叉树基本概念
二叉树是定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
(1)空二叉树——如图(a)；
(2)只有一个根结点的二叉树——如图(b)；
(3)只有左子树——如图(c)；
(4)只有右子树——如图(d)；
(5)——如图(e)。
注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。[1]
二叉树类型
(1)——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有，并且叶子结点都是从左到右依次排布，这就是。
(2)——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。[2]
二叉树相关术语
树的结点：包含一个数据元素及若干指向子树的分支；
孩子结点：结点的子树的根称为该结点的孩子；
双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；
兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上结点；
祖先结点: 从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙
结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；
树的深度：树中最大的结点层
结点的度：结点子树的个数
树的度： 树中最大的结点度。
叶子结点：也叫终端结点，是度为 0 的结点；
分枝结点：度不为0的结点；
有序树：子树有序的树，如：家族树；
无序树：不考虑子树的顺序；[3]
二叉树二叉树性质
(1) 在非空二叉树中，第i层的结点总数不超过
(2) 深度为h的二叉树最多有
个结点(h&=1)，最少有h个结点；
(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
(4) 具有n个结点的的深度为
(5)有N个结点的各结点如果用顺序方式存储，则结点之间有如下关系：
若I为结点编号则 如果I&1，则其父结点的编号为I/2；
如果2*I&=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I&N，则无左儿子；
如果2*I+1&=N，则其右儿子的结点编号为2*I+1；若2*I+1&N，则无右儿子。
(6)给定N个节点，能构成h(N)种不同的二叉树。
h(N)为的第N项。h(n)=C(2*n，n)/(n+1)。
(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i[4]
二叉树存储结构
(1）顺序存储方式
typenode=record
data:datatype
vartr:array[1..n]
(2)存储方式，如：
typebtree=^node；
node=record
lchild,rchild:
二叉树辨析
二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二
叉树有两个主要差别：
1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
2. 树的结点无左、右之分，而二叉树的结点有左、右之分。
二叉树遍历顺序
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，实质上是将二叉树的各个结点转换成为一个线性序列来表示。
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。
二叉树先序遍历
首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树，C语言代码如下：
voidXXBL(tree*root){
//DoSomethingwithroot
if(root-&lchild!=NULL)
XXBL(root-&lchild);
if(root-&rchild!=NULL)
XXBL(root-&rchild);
二叉树中序遍历
首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树，C语言代码如下
voidZXBL(tree*root)
if(root-&lchild!=NULL)
ZXBL(root-&lchild);//DoSomethingwithroot
if(root-&rchild!=NULL)
ZXBL(root-&rchild);
二叉树后序遍历
首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根，C语言代码如下
voidHXBL(tree*root){
if(root-&lchild!=NULL)
HXBL(root-&lchild);
if(root-&rchild!=NULL)
HXBL(root-&rchild);//DoSomethingwithroot
二叉树层次遍历
即按照层次访问，通常用来做。访问根，访问子女，再访问子女的子女（越往后的层次越低）（两个子女的级别相同）
二叉树线索二叉树
线索二叉树(保留遍历时结点在任一序列的前驱和后继的信息)：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其后继。还需在结点结构中增加两个标志域LTag和RTag。LTag=0时，lchild域指示结点的左孩子，LTag=1时，lchild域指示结点的前驱；RTag=0时，rchild域指示结点的右孩子，RTag=1时，rchild域指示结点的后继。以这种结点结构构成的二叉线索，链表作为二叉树的，叫做其中指向结点前驱和后继的叫做线索，加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。若对二叉树进行，则所得的线索二叉树称为中序线索二叉树，线索称为为中序线索链表。线索二叉树是一种。
线索二叉树的存储结构
在中序线索树找结点后继的规律是：若其右标志为1，则右链为线索，指示其后继，否则遍历其右子树时访问的第一个结点（右子树最左下的结点）为其后继；找结点前驱的规律是：若其左标志为1，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一个结点（左子树中最右下的结点）为其前驱。
在后序线索树中找到结点的后继分三种情况：
若结点是二叉树的根，则其后继为空；若结点是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点；若结点是其双亲的左孩子，且其双亲有右子树，则其后继为双亲右子树上按列出的第一个结点。
/*二叉线索存储表示*/typedefenum{Link,Thread}PointerT/* Link(0)：指针，Thread(1)：线索*/typedefstruct BiThrNode{ TElemTstruct BiThrNode *lchild,*/*左右孩子指针*/PointerTag LTag,RT/* 左右标志 */}BiThrNode,*BiThrT
二叉树实现演示
范例二叉树：
此树的顺序结构为：ABCD##E
creat(p,str,0)//默认根节点在str下标0的位置
//p为树的根节点（已开辟动态内存）,str为二叉树的顺序存储数组ABCD##E或其他顺序存储数组，r当前结点所在顺序存储数组位置
voidcreat(node*p,stringstr,intr)
p-&data=str[r];
if(str[r*2+1]=='#'||r*2+1&str.size()-1)p-&lch=NULL;
creat(p-&lch,str,r*2+1);
if(str[r*2+2]=='#'||r*2+2&str.size()-1)p-&rch=NULL;
creat(p-&rch,str,r*2+2);
．百度文库[引用日期]
．百度文库[引用日期]
．百度文库[引用日期]
．百度文库[引用日期]
中国电子学会（Chinese Instit...
提供资源类型：内容}