二叉树与二叉搜索树

概述#

二叉树是一种特殊的树型结构，它由结点的有限集合构成。

二叉树是由唯一的起始结点引出的结点集合。这个起始节点称为根（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 &current){
    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;  
}

运行如下：

运行结果

最后编辑于：2017.12.06 06:29:28

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,080评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,422评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,630评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,554评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,662评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,856评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,014评论 3赞 408
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,752评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,212评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,541评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,687评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,347评论 4赞 331
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,973评论 3赞 315
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,777评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,006评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,406评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,576评论 2赞 349

二叉树与二叉搜索树

概述#

递归思想#

二叉树#

二叉搜索树#

概述####

应用

基本操作

总结#

附录#

推荐阅读更多精彩内容