数据结构基础之树与二叉树各种遍历、思想与实现

我就是我 2022-08-02 01:52 139阅读 0赞

【摘要】

本文首先阐述树的基本概念与特点，二叉树的基本概念与特点；然后，给出二叉树的代码实现，包括二叉树的创建、三序遍历+层序遍历、深度求解和平衡二叉树判断的源码，最后将给出常见OJ树题目的实现思想。

【基本概念】

树的定义

> 指任意两个节点间有且只有一条路径的无向图。只有是没有回路的连通无向图就是树。

树的特征

> 1.一棵树中的任意两个节点有且仅有唯一的一条路径连通；
> 
> 2.一棵树如果有n个节点，那么它一定恰好有n-1条边；
> 
> 3.在一棵树中加一条边将会构成一个回路。

树的深度

> 从根到这个节点的层数（根为第一层）。

根节点

> 一棵树有且只有一个根节点。
> 
> 没有子节点的节点称为叶节点。

二叉树

> 二叉树特点：每个节点最多有两个儿子，左儿子，右儿子，或者说每个节点最多有两颗子树。

> 二叉树要么为空，要么由根节点，左子树和右子树组成。

满二叉树

> 二叉树中每个内部节点（既不是根节点也不是叶节点）都有两个儿子，或者说满二叉树中所有的叶节点都有同样的深度。
> 
> 深度为 h 的满二叉树，有 2^h-1 个节点。

完全二叉树

> 除了最右边位置上有一个或者几个叶子节点缺少外，其它是满的。
> 
> 完全二叉树高度为 h，除第 h 层外，其他各层（1~h-1）的节点数都达到最大个数。
> 
> 若完全二叉树的某一个节点有右儿子，那它一定也有左儿子。

> 完全二叉树中，一个父节点编号为k，那么左儿子编号是2\*k，右儿子编号是2\*k+1.如果已知儿子（不管是左还有右）编号为x，那么它父节点编号就是x/2。

> 完全二叉树有N个节点，那么这个完全二叉树的高度就是log2N，或者为logN，即最多有logN层节点。

二叉查找树

> 二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

【二叉树的实现】

*  二叉树的创建

// 二叉树结构体
    typedef struct BiTNode  
    {
        char data;
        struct BiTNode *lchild,*rchild;
    }BiTNode;
    
    // 创建二叉树
    int CreateBiTree( BiTree *T )  
    {
        char ch;
        ch=getchar();
        if( ch == '#' )
            T=NULL;
        else
        {
            if( ! ( T = ( BiTree* )malloc( sizeof( BiTNode ) ) ) )
                exit( 0 );
            T->data = ch;
            CreateBiTree( T->lchild );
            CreateBiTree( T->rchild );
        }
        return 0;
    }

*  二叉树的遍历

// 二叉树输出
    void Visit(BiTree *T)    
    {  
        if(T->data != '#')
        {  
            printf("%c ",T->data);  
        }  
    } 
    // 先序遍历  
    void PreOrder(BiTree *T)
    {  
        if( T!=NULL )
        {   
            Visit(T);   
            PreOrder(T->lchild); 
            PreOrder(T->rchild);  
        }  
    }
    // 中序遍历    
    void InOrder(BiTree *T)
    {    
        if( T!=NULL )
        {       
            InOrder(T->lchild);    
            Visit(T);       
            InOrder(T->rchild);    
        }    
    } 
    // 后序遍历  
    void PostOrder(BiTree *T)
    {  
        if( T!=NULL )
        {    
            PostOrder(T->lchild);   
            PostOrder(T->rchild);  
            Visit(T);  
        }  
    }

> >   
> >

【二叉树的层序遍历】

#include <queue>  
    #include <assert.h> 
    void PrintInLayer(Node* head)  
    {  
        assert(p!=NULL);
        Node* p = head；
        queue<Node*> MyQueue;  
        int MyQueue_size;  
        int MyQueue_pos;  
        MyQueue.push(p);  
        while(p!=NULL||!MyQueue.empty())  
        {  
            MyQueue_size=MyQueue.size();  
            MyQueue_pos=0;  
            while(MyQueue_pos<MyQueue_size)  
            {  
                cout<<p->num<<" ";  
                MyQueue.pop();  
                if(p->pLeft!=NULL)  
                    MyQueue.push(p->pLeft);  
                if (p->pRight!=NULL)  
                    MyQueue.push(p->pRight);  
                if(!MyQueue.empty())  
                {  
                    p=MyQueue.front();  
                    //MyQueue.pop();  
                }  
                else  
                p=NULL;  
                MyQueue_pos++;  
            }  
            cout<<endl;        
        }  
    }

> >   
> >

【二叉树相关操作】

*  求二叉树的叶子数

// 求二叉树叶子数
    int sumleaf( BiTree *T )  
    {
        if( T!=NULL )
        {
            if( T->lchild || T->rchild )
                return( sumleaf( T->lchild ) + sumleaf( T->rchild ) );
            else
                return 1;
        }
        return 0;
    }

*  求解二叉树的深度

// 返回两个整数中较大的一个
    int themax( int a, int b )  
    {
        if( a>b )
            return a;
        else 
            return b;
    }
    // 求二叉树的深度
    int Depth( BiTree *T )  
    {
        if( T!=NULL )
            return( 1 + themax( Depth( T->lchild ), Depth( T->rchild ) ) );
        return 0;
    }

*  平衡二叉树的判断

// 判断二叉树是否为平衡二叉树
    // 平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
    bool bebalance( BiTree *T )
    {
        if ( T==NULL )
            return true;
    
        int ld=Depth(T->lchild);
        int lr=Depth(T->rchild);
    
        int di=abs(ld-lr);
        if (di>1)                 //根节点平衡
            return false;
        // 不仅仅是高度差小于1，就够了，还有子树也要平衡，这很重要！！！
        return bebalance(T->lchild) && bebalance(T->rchild);  //左右子树平衡
    }

> >   
> >