二叉树查找算法

A. 二叉树算法有哪些应用场景

二叉树常被用于实现二叉查找树和二叉堆。

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。

根据不同的用途可分为：

1、完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

2、满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

3、平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

(1)二叉树查找算法扩展阅读

深度为h的二叉树最多有个结点(h>=1)，最少有h个结点。对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1。

有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系为若I为结点编号则 如果I>1，则其父结点的编号为I/2。如果2*I<=N，则其左孩子（即左子树的根结点）的编号为2*I。若2*I>N，则无左孩子。如果2*I+1<=N，则其右孩子的结点编号为2*I+1。

B. 从一棵二叉树中查找出所有结点的最大值。

#include <stdio.h>//头文件
#include <stdlib.h>
#include <malloc.h>
typedef struct BiTNode
{
int data;
struct BiTNode *lchild,*rchild;
}
BiTNode,*BiTree;//定义结点类型
int max=-100;//把max定义得足够小
BiTree CreateBiTree()//先序递归创建树
{
int p;BiTree T;
scanf("%d",&p);//注意每输入两个值的时候用空格各隔开
if(p==0)
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));//为结点开辟空间
T->data=p;
T->lchild=CreateBiTree();
T->rchild=CreateBiTree();
}
return (T);
}
int Max(BiTree T)//求最大(递归算法）
{
if(T==NULL)
return 0;
if(T!=NULL)
{
if(T->data>max)
max=T->data;
Max(T->lchild);
Max(T->rchild);

}
return max;
}
void main()//主函数
{
BiTree Ta;
Ta=CreateBiTree();
printf("最大值是：\n");
printf("%d",Max(Ta));
}
原理很简单，随便通过一种遍历(我用的是先序），先把根节点的值给max，然后在访问其他节点的时候判断那个值是否更大，如果是就赋值给max，最后就可以找到最大值了。
想了一下，如果用递归的话就不要用到栈了，这样更简单，如果你需要非递归的话可以联系我。你不会创建树可以联系。

C. 急！！求C++平衡二叉树查找的算法

俺有~~

代码的一部份：老师给的；代码有点多，要的话，给我邮箱，我发给你吧！
“
#define LH 1 //左子树高
#define EH 0 //左右子树等高
#define RH -1 //右子树高
enum BOOL{False,True};
typedef struct //定义记录的结构
{int keynum; //在本程序中只含有关键字一项
}Record;
typedef struct BSTNode //定义平衡二叉树节点结构
{Record data; //数据域
int bf; //平衡因子
struct BSTNode *lchild,*rchild; //左右孩子指针域
}BSTNode,*BSTree;
BSTree SearchBST(BSTree,int); //在平衡二叉排序树中查找元素
BOOL InsertAVL(BSTree &,Record,BOOL&); //在平衡二叉排序树中插入元素
void LeftBalance(BSTree &); //左平衡旋转处理
void RightBalance(BSTree &); //右平衡旋转处理
void InorderBST(BSTree); //中序遍历二叉排序树，即从小到大显示各元素
void R_Rotate(BSTree &); //右旋处理
void L_Rotate(BSTree &); //左旋处理
void main()”

已经发到你邮箱里了，注意查收！！完整的程序代码！！

D. 二叉树算法是什么

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。

二叉树的第i层至多有2^（i 1）个结点；深度为k的二叉树至多有2^k 1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。二叉树算法常被用于实现二叉查找树和二叉堆。

二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

(4)二叉树查找算法扩展阅读：

二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树算法有五种基本形态：

1、空二叉树——(a)

2、只有一个根结点的二叉树——(b);

3、右子树为空的二叉树——(c);

4、左子树为空的二叉树——(d);

5、完全二叉树——(e)

注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。

E. 如何实现二叉树遍历、排序、查找（小女子急须要大侠们的帮忙~~~）

如果这部分题别人给你做的话毕业了你更哭,还小女子!BS
其实你的分给的真的很少
累傻小子呢?

F. 二叉树如何用算法找到某结点的所有祖先

#include<stdio.h>

typedef char DataType;

typedef struct BinTreeNode *PBinTreeNode;
struct BinTreeNode
{
DataType info; // 数据域
PBinTreeNode llink, rlink; //左右指针
};
typedef struct BinTreeNode *BTree; //表示二叉树类型
typedef struct BinTreeNode *BNode; //表示二叉树节点类型

BTree CreateEmptyTree() //建空二叉树
{
BTree atree=(BTree)malloc(sizeof(struct BinTreeNode));
if(atree!=NULL)
{
atree->llink=NULL;
atree->rlink=NULL;
}
else
printf("Out of space! \n"); /*创建失败*/
return (atree);
}

void Parent(BTree t,BNode a,BNode &p)//t为二叉树根节点,a为目标子节点，p目标父节点
{
if(t)
{
if(t->llink == a || t->rlink == a)//a为需要查找的二叉树节点值
{
p=t;
}
else
{
Parent(t->llink, a, p);
Parent(t->rlink,a, p);
}
}
}

BTree Insert(BTree &T,char x) //构造T->info=x,T->llink=NULL
{
T=CreateEmptyTree();
T->info = x;
T->llink= CreateEmptyTree() ;
T->rlink= CreateEmptyTree() ;
return (T);
}

int main()
{
BTree atree;
atree=CreateEmptyTree() ;
Insert(atree,'a');//atree->info='a';
Insert(atree->llink,'b');//atree->llink->info='b';
Insert(atree->llink->llink,'c');//atree->llink->llink->info='c';
Insert(atree->llink->llink->llink,'d');
Insert(atree->llink->llink->rlink,'e');
Insert(atree->llink->llink->rlink->llink,'f');
BNode x; //寻找一个点的祖先
Parent(atree,atree->llink->llink->rlink->llink, x);
printf("%c ",x->info);
BNode y=x;
while(y!=atree)
{
Parent(atree,y, x);
printf("%c ",x->info);
y=x;
}
printf("\n");
return 0;
}

G. 二叉树基本算法

#include <iostream.h>
typedef struct BiTNode
{
char data;
int bit;
struct BiTNode *lchild,*rchild,*parent;
}BiTNode;

void InitBT(BiTNode *&t)//1、初始化，不带头结点
{
t=NULL;
}

/*void InitBT(BiTNode *t)//初始化，带头结点
{
t=new BiTNode;
t->lchild=t->rchild=t->parent=NULL;
}*/

int EmptyBT(BiTNode *t)//判断队空
{
if(t==0)
return 1;
else
return 0;
}

BiTNode *creatBT(BiTNode *t,int b)//2、创建二叉树
{
BiTNode *p;
char ch;
cin>>ch;
if(ch=='#')return 0;
else
{
p=new BiTNode;
p->data=ch;
p->parent=t;
p->bit=b;
t=p;
t->lchild=creatBT(t,0);
t->rchild=creatBT(t,1);
}
return t;
}

void preorder(BiTNode *t)//3、先序遍历
{
if(!EmptyBT(t))
{
cout<<t->data;
preorder(t->lchild);
preorder(t->rchild);
}
}

void inorder(BiTNode *t)//中序遍历
{
if(!EmptyBT(t))
{
inorder(t->lchild);
cout<<t->data;
inorder(t->rchild);
}
}

void postorder(BiTNode *t)//后序遍历
{
if(!EmptyBT(t))
{
postorder(t->lchild);
postorder(t->rchild);
cout<<t->data;
}
}

void coutBT(BiTNode *t,int &m,int &n,int &i)//4、计算二叉树中叶子结点、度为2的结点和度为1的结点的个数
{
if(!EmptyBT(t))
{
if((t->lchild==0) && (t->rchild==0))
m++;//叶子结点
else if((t->lchild!=0) && (t->rchild!=0))
i++;//度为2的结点
else
n++;//度为1的结点
coutBT(t->lchild,m,n,i);
coutBT(t->rchild,m,n,i);
}
}

void coutNode(BiTNode *t,int &k)//5、求二叉树中结点个数
{
if(!EmptyBT(t))
{
k++;
coutNode(t->lchild,k);
coutNode(t->rchild,k);
}
}

int BTdepth(BiTNode *t)//6、求二叉树的深度
{
int i,j;
if(EmptyBT(t))
return 0;
else
{
i=BTdepth(t->lchild);
j=BTdepth(t->rchild);
return (i>j?i:j)+1;
}
}

int Xdepth(BiTNode *t,char x)//7、查找x的层数
{
int num1,num2,n;
if(t==NULL)
return 0;
else{
if(t->data==x)
return 1;
num1=Xdepth(t->lchild,x);
num2=Xdepth(t->rchild,x);
n=num1+num2;
if(num1!=0||num2!=0)
n++;
return n;
}
}

static int flag;
void SearchChild(BiTNode *t,int k)//8、查找第k个结点的左右孩子
{
if(!EmptyBT(t))
{
if(k==0)
{
cout<<"位置不能为0!"<<endl;
return;
}
else
{
flag++;
if(flag==k)
{
if(t->lchild==0)
cout<<"无左孩子! ";
else
cout<<"左孩子为："<<(t->lchild->data)<<" ";
if(t->rchild==0)
cout<<"无右孩子!"<<endl;
else
cout<<"右孩子为："<<(t->rchild->data)<<endl;
}
else
{
SearchChild(t->lchild,k);
SearchChild(t->rchild,k);
}
}
}
}

int Xancestor(BiTNode *t,char x)//9、查找x结点祖先
{
int n,num1,num2;
if(t==NULL)
return 0;
else
{
if(t->data==x)
return 1;
num1=Xancestor(t->lchild,x);
num2=Xancestor(t->rchild,x);
n=num1+num2;
if(n!=0)
{
n++;
cout<<t->data<<" "<<endl;
}
}
}

void BTNodePath(BiTNode *t)//10、输出所有叶子结点路径
{
if(!EmptyBT(t))
{
if((t->lchild==0) && (t->rchild==0))
{
cout<<t->data<<"的路径为：";
for(BiTNode *p=t;p!=0;p=p->parent)
cout<<p->data;
cout<<endl;
}
else
{
BTNodePath(t->lchild);
BTNodePath(t->rchild);
}
}
}

void BTNodebit(BiTNode *t)//11、输出所有叶子结点编码
{
if(!EmptyBT(t))
{
if((t->lchild==0) && (t->rchild==0))
{
cout<<t->data<<"的编码为：";
for(BiTNode *p=t;p->parent!=0;p=p->parent)
cout<<p->bit;
cout<<endl;
}
else
{
BTNodebit(t->lchild);
BTNodebit(t->rchild);
}
}
}

void main()
{
BiTNode *t;
int m,n,i,d,q,k;
char x;
cout<<"1、初始化..."<<endl;
InitBT(t);

cout<<"2、创建二叉树..."<<endl;
t=creatBT(t,0);

cout<<"3.1、先序遍历..."<<endl;
preorder(t);
cout<<endl;
cout<<"3.2、中序遍历..."<<endl;
inorder(t);
cout<<endl;
cout<<"3.3、后序遍历..."<<endl;
postorder(t);
cout<<endl;

m=n=i=0;
cout<<"4、计算叶子结点，度为1的结点和度为2的结点的个数..."<<endl;
coutBT(t,m,n,i);
cout<<"叶子结点个数为："<<m<<endl;
cout<<"度为1的结点个数为："<<n<<endl;
cout<<"度为2的结点个数为："<<i<<endl;

q=0;
cout<<"5、计算结点个数..."<<endl;
coutNode(t,q);
cout<<"结点个数为："<<q<<endl;

d=0;
cout<<"6、计算深度..."<<endl;
d=BTdepth(t);
cout<<"深度为："<<d<<endl;

cout<<"7、求x的层数..."<<endl;
cout<<"输入x：";
cin>>x;
if(Xdepth(t,x)==0)
cout<<"x不存在！"<<endl;
else
cout<<Xdepth(t,x)<<endl;

cout<<"8、输入要查找孩子的结点在先序遍历中的位置k（不等于0）：";
cin>>k;
SearchChild(t,k);
if(k>flag)
cout<<"位置超出长度!"<<endl;

cout<<"9、查询结点的所有祖先，请输入结点x：";
cin>>x;
int num;
num=Xancestor(t,x);
if(num==0)
cout<<"结点不存在！"<<endl;
if(num==1)
cout<<"根结点无祖先！"<<endl;

cout<<"10、输出所有叶子结点路径（叶→根）："<<endl;
BTNodePath(t);

cout<<"11、输出所有叶子结点编码（叶→根）："<<endl;
BTNodebit(t);
}

H. 二叉树的性质有些啊怎么求它的深度

二叉树性质如下：

1 ：在二叉树的第i层上至少有2^（i-1）个结点

2：深度为k的二叉树至多有2^(k-1)个结点

3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1

4：具有n个结点的完全二叉树的深度是【log2n】+1（向下取整）

5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有：

如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2

如果2i>n，则结点i无左孩子；如果2in，则其左孩子是2i

如果2i+1>n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1

二叉树深度算法如下：

深度为m的满二叉树有2^m-1个结点；

具有n个结点的完全二叉树的深度为[log2n]+1.（log2n是以2为底n的对数）

(8)二叉树查找算法扩展阅读：

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。具有n个节点的完全二叉树的深度为log2(n+1)。深度为k的完全二叉树，至少有2k-1个节点，至多有2k-1个节点。

二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。

I. 题目3． 平衡二叉树算法查找树中某节点的时间复杂度是多少

平均查找的时间复杂度为O(log n)。

平衡树的查找过程和排序树的相同。在查找过程中和给定值进行比较关键字个数不超过树的深度。

如果二叉树的元素个数为n，那么不管是对树进行插入节点、查找、删除节点都是log(n)次循环调用就可以了。它的时间复杂度相对于其他数据结构如数组等是最优的。

是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。

(9)二叉树查找算法扩展阅读：

二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树算法有五种基本形态：

(1)空二叉树——(a)

(2)只有一个根结点的二叉树——(b);

(3)右子树为空的二叉树——(c);

(4)左子树为空的二叉树——(d);

(5)完全二叉树——(e)

注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。

J. 二叉树查找和二分查找是同一算法吗

两者的算法思路其实很像：比中间的小就在剩下的左边，大就在剩下的右边找
但是：
二叉树查找一般习惯是在链式存储上进行，为一个树形结构
二分查找一定在顺序存储上进行