二叉树与二叉搜索树
概述#
二叉树是一种特殊的树型结构，它由结点的有限集合构成。
二叉树是由唯一的起始结点引出的结点集合。这个起始节点称为根（root）。二叉树中的任何非根节点都有且仅有一个前去结点，称为该结点的父结点（parent）。根节点即为二叉树中唯一没有父结点的结点。二叉树中的任何结点最多可能有两个后继结点，分别称为左子结点（left child）和右子结点（right child）。具有相同父结点的结点之间互称兄弟结点（sibling）。二叉树中的一个结点的子数树木称为该结点的度（degree）。没有子结点的结点称为叶结点（leaf），叶结点的度为0。
二叉树的基本操作有：前序、中序、后续周游二叉树，删除给定二叉树，获得深度，获得叶子数，获得总结点数等。其中，前序、中序、后续周游尤为重要，他们运用了递归算法周游二叉树，可以大幅度简化非递归的周游算法，所以接下来，我们先给出递归算法的说明，再进一步说明如何运用递归算法实现二叉树的创建和基本操作。
递归思想#
递归算法就是一种直接或间接调用自己函数的算法，即函数里嵌套函数。
就像数学里常见的函数 f(x), 递归思想可以举例为： f ( f ( f ( x ) ) )，其中，总有一个函数可以求值，类似于递归函数中，总有一个递归有结束条件，这个递归成为递归出口。比如说一个简单的例子：
int add(int &a){
char c='ABCD';
if(c=='D') return 5;
return add(a)+1;
}
递归算法实现流程
递归可以大大减少算法的复杂度，但是伴随的缺点是，需要大量的内存空间来储存每个函数中的返回值和局部变量。
每开启一个递归，则会开辟一个新的栈空间，用来储存所需数据，结束递归后会清空栈里的内容，只留下返回值返回到上层递归，再进行一次类似运算。因此，如果递归次数较多，则需要大量空间，这时会造成栈溢出等问题。
我们来看下面一个二叉树前序周游递归实现。
void PreOrder(BiTree &root){ //先序遍历二叉树
if( root!=NULL){
cout<< root -> info<<" ";
PreOrder(root->leftchild);
PreOrder(root->rightchild);
}
}
如果二叉树为：
a
b c
1.开始：根节点非空，输出a，进入到下一层，root指向leftchild的递归。
2.leftchild非空，则输出b，进入到下一层，root指向leftchild的递归。
3.leftchild为空，则不进行操作，返回到上一层（2）的递归函数继续进行操作。
4.b结点的右子树为空，则不进行操作。这时此层（2）递归函数已经执行完毕，则返回到上一层（1）root指向rightchild的递归。
5.rightchild为c，输出c，又进入一层root指向leftchild的递归。
6.leftchild为空，不进行操作，返回上一层（5）root指向rightchild的递归。
7.rightchild为空，不进行操作，（5）递归执行完毕，所有函数递归操作完毕，结束程序。
看上去很复杂，多理解，多实际操作就能懂了。
二叉树#
二叉树的创建与基本操作可以用递归方法实现，使得代码更简明。
以下给出了二叉树的递归创建、求先序中序后续周游、总结点数、叶子数、深度的算法。
-
二叉树创建
用先序方法创建二叉树。
首先申请一个结点空间，root指针指向根结点。然后将输入的数据查入结点内容中。进入下一个点，即root指向leftchild，进行递归，直到叶子结点时，指针root为空，结束递归。
操作如下：
1.先插入根结点数据为A，root指向A的左子树。
2.左子树插入B，root指向B的左子树。
3.B的左子树插入#，表示为空，root指向B的右子树
4.B的右子树插入#，表示为空，root指向A的右子树。
5.A的右子树插入#，表示为空，root指向根节点，算法结束。
void creat(BiTree &root){ //先序创建二叉树
char ch;
cin>>ch;
if (ch=='#'){
root=NULL;}
else{
root = (BiTreeNode *)malloc(sizeof(BiTree));
root -> info = ch;
creat(root -> lchild);
creat(root -> rchild);
}
}
-
二叉树周游
这里运用递归思想实现二叉树周游算法。与创建二叉树类似，具体实现过程在递归思想中已经说明过，这里不再阐述了。
void PreOrder(BiTree &root){ //先序遍历二叉树
if( root!=NULL){
cout<< root -> info;
PreOrder(root->lchild);
PreOrder(root->rchild);
}
}
void InOrder(BiTree &root){ //中序遍历二叉树
if( root!=NULL){
InOrder(root->lchild);
cout<< root -> info;
InOrder(root->rchild);
}
}
void PostOrder(BiTree &root){ //后序遍历二叉树
if( root!=NULL){
PostOrder(root->lchild);
PostOrder(root->rchild);
cout<< root -> info;
}
}
-
获取树深度
基本实现思想是：
先求左子树的深度，再求右子树的深度，求两者中较大的一方加一。采用递归的方法实现：
int GetDepth(BiTree &root) //获取树的深度
{
int lDepth;
int rDepth;
if (root == NULL)
{
return 0;
}
lDepth= GetDepth(root->lchild);
rDepth= GetDepth(root->rchild);
if (lDepth> rDepth) return lDepth+1;
else{ return rDepth +1;}
}
-
结点数与叶子数
求结点数时，可以参考周游算法，因为周游一遍二叉树也就是周游了一遍所有节点。可以每递归一次函数则总结点数加一。为了实现这一目标，我们可以先求左子树的结点数，再求右子树的结点数，再翻回他们的和外加一个根结点。
求叶子数时，当指针非空且左孩子右孩子都为NULL时，则总叶子数加一；若指针为空，则返回0值；其他情况继续进行周游算法。具体代码如下：
int NodeNum(BiTree &root){ //结点数
if( root==NULL){
return 0;}
else{
int num1=NodeNum(root->lchild);
int num2=NodeNum(root->rchild);
return num1+num2+1;
}
}
int LeafNum(BiTree &root){ //叶子树
if(root!=NULL&&root->lchild==NULL && root -> rchild ==NULL){
return 1;
}
else if(root==NULL){
return 0;}
else {
return LeafNum(root->lchild)+LeafNum(root->rchild);
}
}
总代码将在附录里给出，运行结果如下：
Paste_Image.png
二叉搜索树#
-
概述####
二叉搜索树是一类满足以下属性的特殊二叉树：二叉搜索树中的每个非空结点表示一个记录；若某结点左子树不为空，则左子树上的所有结点的值均小于该结点的关键码值；若其右子树不为空，则右子树上的所有节点的值均大于该结点的关键码值。二叉搜索树可以使一课空树，任何点的左右子树都是二叉搜索树。按照中序周游整个二叉树可得到一个由小到大的有序排列。
-
应用
在实际应用中，经常会碰到这样的操作：在一组记录中检索一个记录，向其中插入一个记录或者删除一个记录等。
对于一个无序线性表，插入记录时只需要把该记录放在表的末端，但在表中查找一个特定记录的检索时间却相对较慢。对于有序线性表，如果用二分查找法检索特定的记录，检索效率较高，但是遇到动态增减变化的情况时（如插入或删除一个元素）需要移动大量的元素。
因此，二叉搜索树的性质可以达到这一要求，运用了二分法将小于结点数的数值放入左子树，将大于结点数的数值放入右子树，可以实现便捷查找。
-
基本操作
二叉搜索树的基本操作包含：插入、删除和查找。这里我们给出插入、删除和查找最大最小值得算法。
插入结点
二叉搜索树的插入操作具体是这样：将待插入结点的关键码与根结点的关键码相比较，若待插入的关键码小于根结点的关键码，则进入左子树，否则进入右子树。按照同样的方式沿检索路径知道叶结点，确定插入位置，把待插入节点作为一个新叶节点插入到二叉搜索树中。
具体操作如下：
二叉搜索树插入
1.待插入节点为18，先与根结点关键码50比较，小于根结点关键码，则root指向左孩子。
2.与根结点关键码19比较，小于关键码，则root指向左孩子。
3.与根结点关键码5比较，大于关键码，则root指向右孩子。
4.root为NULL，将关键码为18的newpoint插入上一指针的右孩子处。
具体算法实现如下：
void InsertNode( BiTree &root,BiTree &newpoint){ //插入结点
BiTree point= NULL;
if ( root == NULL){
root= newpoint;
cout<<"已插入"<<root->info<<endl;
return;
}
else point =root;
while ( point != NULL){
if ( newpoint->info == point ->info){
cout<<"已包含的结点"<<endl;
return;}
else if( newpoint->info < point ->info ){
if(point ->leftchild == NULL){
point->leftchild = newpoint;
cout<<"已插入"<<point->info<<endl;
return;
}
else point = point ->leftchild;
}
else{
if(point -> rightchild == NULL){
point -> rightchild = newpoint;
cout<<"已插入"<<point->info<<endl;
return;
}
else point= point -> rightchild;
}
}
}
删除结点
二叉树的删除较为复杂，可以分为四种情况。假设待删除的结点为p，则：
删除结点的不同情况
1.p结点的左孩子与右孩子都为空，则删除p不对二叉树产生影响，可直接free（p）。
2.p结点的左孩子为空，则使p的父结点的右孩子改变为p的右孩子，free（p）。
3.p结点的右孩子为空，则使p的父结点的左孩子改变为p的左孩子，free（p）。
4.p结点的左右孩子都不为空，则比较复杂，应另外讨论。
由于二叉搜索树要求关键码之间满足一定地大小关系，这就使得从树中删除一个结点的算法比较复杂。从二叉搜索树中删除一个结点时，要保持二叉搜索树的性质，就不能再二叉搜索树中留下一个空位置，因此需要用另一个结点来填充这个位置并且保持性质。
设pointer，temppointer是指针变量，其中pointer为要删除的结点。首先，找到待删除的结点pointer，删除该节点的过程如下：
当待删结点有左右孩子时
代码实现过程如下：
void DeleteNode(BiTree &root, int& data) {
BiTree parent;
BiTree pointer = root;
BiTree temmpointer;
if (pointer == NULL) {
cout<<"未找到该结点"<<endl;
return;
}
if (pointer->info == data) {
if (pointer->rightchild == NULL && pointer->leftchild == NULL) { // 当没有左右孩子
root = NULL;
free(pointer);
}
else if (pointer->rightchild == NULL) { // 当没有右孩子
root = pointer->leftchild;
free(pointer);
}
else if (pointer->leftchild == NULL) { // 当没有左孩子
root = pointer->rightchild;
free(pointer);
}
else {
temmpointer = pointer->rightchild;
if (temmpointer->leftchild==NULL) //当临时结点为叶子结点，即待删结点的左子树只有一枚叶子结点
temmpointer->leftchild = pointer->leftchild;
else { //当临时结点有左孩子，则寻找左孩子里关键码值最小的点，作为tempparent
while (temmpointer->leftchild) {
parent = temmpointer; //记录tempparent的父结点信息
temmpointer = temmpointer->leftchild;
}
parent->leftchild = temmpointer->rightchild;
temmpointer->leftchild = pointer->leftchild;
temmpointer->rightchild = pointer->rightchild;
}
root = temmpointer;
free(pointer);
}
}
else if (data > pointer->info) {
DeleteNode((pointer->rightchild), data);
}
else if (data < pointer->info) {
DeleteNode((pointer->leftchild), data);
}
}
查找最大值与最小值
最大值即右孩子的右孩子的右孩子……知道右孩子为NULL时，则返回该结点关键码值。
最小值即最左孩子。
void maxmix(BiTree &root){
BiTree point;
point= root;
while(point -> leftchild){
point=point -> leftchild;
}
cout<<"最小结点值为："<<point->info<<endl;
point = root;
while(point -> rightchild){
point=point -> rightchild;
}
cout<<"最大结点值为："<<point->info<<endl;
}
总结#
因为最近事情很多，再加上对递归算法理解不深，指针运用不熟练，做了这些可能挺简单的东西却用了很长时间。大量的时间运用在理解递归算法上，然后就是指针运用。
我理解的递归算法就是类似于函数套函数；一般我们考虑算法时都是从上往下设计，但是用到递归时就需要从下往上，因为递归算法出口才是返回数的来源，再根据来源逐步往上推。现在运用还是不太熟练，以后再看看。但是递归好像运用的不多，因为我感觉在一个大程序里，疯狂的占用内存，开辟栈，对计算机硬件的要求太变态了。
对于指针，一开始不知道是什么。不过老师给我讲了讲，有了大概思路，应该就是一个指向内存数据的地址。指针运用的比较多，因此可能需要更多的练习。
附录#
总程序贴在这里：
#include <iostream>
#include<stack>
#include "malloc.h"
using namespace std;
typedef struct BiTreeNode{
int info;
struct BiTreeNode *leftchild;
struct BiTreeNode *rightchild;
}BiTreeNode, *BiTree;
BiTree Parent(BiTree& root, BiTree ¤t){
using std::stack;
stack< BiTree> aStack;
BiTree point;
if( root != NULL && current != NULL){
while( !aStack.empty()||point){
if(point != NULL){
if(current == point -> leftchild||current == point -> rightchild)
return point;
aStack.push(point);
point = point ->leftchild;
}
else{
point = aStack.top();
aStack.pop();
point = point -> rightchild;
}
}
}
}
void InsertNode( BiTree &root,BiTree &newpoint){
BiTree point= NULL;
if ( root == NULL){
root= newpoint;
cout<<"已插入"<<root->info<<endl;
return;
}
else point =root;
while ( point != NULL){
if ( newpoint->info == point ->info){
cout<<"已包含的结点"<<endl;
return;}
else if( newpoint->info < point ->info ){
if(point ->leftchild == NULL){
point->leftchild = newpoint;
cout<<"已插入"<<point->info<<endl;
return;
}
else point = point ->leftchild;
}
else{
if(point -> rightchild == NULL){
point -> rightchild = newpoint;
cout<<"已插入"<<point->info<<endl;
return;
}
else point= point -> rightchild;
}
}
}
void PreOrder(BiTree &root){ //先序遍历二叉树
if( root!=NULL){
cout<< root -> info<<" ";
PreOrder(root->leftchild);
PreOrder(root->rightchild);
}
}
void InOrder(BiTree &root){ //中序遍历二叉树
if( root!=NULL){
InOrder(root->leftchild);
cout<< root -> info<<" ";
InOrder(root->rightchild);
}
}
void PostOrder(BiTree &root){ //后序遍历二叉树
if( root!=NULL){
PostOrder(root->leftchild);
PostOrder(root->rightchild);
cout<< root -> info;
}
}
int NodeNum(BiTree &root){ //结点数
if( root==NULL){
return 0;}
else{
int num1=NodeNum(root->leftchild);
int num2=NodeNum(root->rightchild);
return num1+num2+1;
}
}
int LeafNum(BiTree &root){
if(root!=NULL && root->leftchild==NULL && root -> rightchild ==NULL){
return 1;
}
else if(root==NULL){
return 0;}
else {
return LeafNum(root->leftchild)+LeafNum(root->rightchild);
}
}
int GetDepth(BiTree &root) //获取树的深度
{
int lDepth;
int rDepth;
if (root == NULL)
{
return 0;
}
lDepth= GetDepth(root->leftchild);
rDepth= GetDepth(root->rightchild);
if (lDepth> rDepth) return lDepth+1;
else{ return rDepth +1;}
}
void maxmix(BiTree &root){
BiTree point;
point= root;
while(point -> leftchild){
point=point -> leftchild;
}
cout<<"最小结点值为："<<point->info<<endl;
point = root;
while(point -> rightchild){
point=point -> rightchild;
}
cout<<"最大结点值为："<<point->info<<endl;
}
void DeleteNode(BiTree &root, int& data) {
BiTree parent;
BiTree pointer = root;
BiTree temmpointer;
if (pointer == NULL) {
cout<<"未找到该结点"<<endl;
return;
}
if (pointer->info == data) {
if (pointer->rightchild == NULL && pointer->leftchild == NULL) { // 当没有左右孩子
root = NULL;
free(pointer);
}
else if (pointer->rightchild == NULL) { // 当没有右孩子
root = pointer->leftchild;
free(pointer);
}
else if (pointer->leftchild == NULL) { // 当没有左孩子
root = pointer->rightchild;
free(pointer);
}
else {
temmpointer = pointer->rightchild;
if (temmpointer->leftchild==NULL) //当临时结点为叶子结点，即待删结点的左子树只有一枚叶子结点
temmpointer->leftchild = pointer->leftchild;
else { //当临时结点有左孩子，则寻找左孩子里关键码值最小的点，作为tempparent
while (temmpointer->leftchild) {
parent = temmpointer; //记录tempparent的父结点信息
temmpointer = temmpointer->leftchild;
}
parent->leftchild = temmpointer->rightchild;
temmpointer->leftchild = pointer->leftchild;
temmpointer->rightchild = pointer->rightchild;
}
root = temmpointer;
free(pointer);
}
}
else if (data > pointer->info) {
DeleteNode((pointer->rightchild), data);
}
else if (data < pointer->info) {
DeleteNode((pointer->leftchild), data);
}
}
//创建一棵二叉查找树
void create(BiTree& root, int *keyArray,int length)
{
int i=0;
//逐个结点插入二叉树中
for(i=0;i<length;i++){
BiTree newpoint=(BiTree)malloc(sizeof(BiTreeNode));
newpoint ->info = keyArray[i];
newpoint ->leftchild=NULL;
newpoint ->rightchild=NULL;
InsertNode(root,newpoint);
}
}
bool PrintTree(BiTree T, int nLayer){
if(T == NULL)
return false;
PrintTree(T -> rightchild, nLayer+3);
for (int i = 0; i < nLayer; i++){
cout<<" ";
}
cout<<T ->info << endl;
PrintTree( T-> leftchild, nLayer +3);
return true;
}
int main(void)
{
int nLayer=0;
int choose=0;
int value;
BiTree root=NULL;
int nodeArray[11]={15,6,18,3,7,17,20,2,4,13,9};
create(root,nodeArray,11);
PreOrder(root);
cout<<endl;
InOrder(root);
cout<<"打印树："<<endl;
PrintTree(root,nLayer);
while(1){
cout<<endl;
cout<<"-------------------------------------------"<<endl;
cout<<"请选择操作：\n1.插入结点. 2.删除结点. 3.查找最大最小结点.\n4.获得树深. 5.获得总结点数. 6.获得总叶子数.\n7.打印树"<<endl;
cin>>choose;
switch(choose){
case(1):{
cout<<"请输入插入数据"<<endl;
cin>>value;
BiTree newpoint=(BiTree)malloc(sizeof(BiTreeNode));
newpoint ->info = value;
newpoint ->leftchild=NULL;
newpoint ->rightchild=NULL;
InsertNode(root,newpoint);
break;
}
case(2):{
cin>>value;
DeleteNode(root,value);
break;
}
case(3):{
maxmix(root);
break;
}
case(4):{
cout<<GetDepth(root)<<endl;
break;}
case(5):{
cout<<NodeNum(root)<<endl;
break;
}
case(6):{
cout<<LeafNum(root)<<endl;
break;}
case(7):{
PrintTree(root,nLayer);
break;
}
}
}
system("pause");
return 0;
}
运行如下：
运行结果
