C/C++二叉树详解(顺序、链式、线索树)

概述

二叉树是n个节点的有限集合,它或者是空树(n=0),或者是由一个根节点加上两棵分别称左子树和右子树的二叉树组成。即使在结点只有一颗子树的情况下,也要明确指定该子树是左子树还是右子树。

二叉树特点:

  1. 二叉树第i层 (i>=1)上最多有2^(i-1)。二叉树每层最大结点数计算满足等比数列(从第二项起,每一项与它的前一项的比值等于同一个常数的一种数列。通项公式:An=A1*2^(n-1)。)
  2. 高度为k的二叉树最多有2^k-1
    根据等比数列求和公式可得。
  3. 对于任何一颗二叉树,若终端节点为n0,度为2的结点为n2。则n0=n2+1设度为0的结点数为n0,度为1的结点数为n1,度为2的结点数为n2,则结点总数n=n0+n1+n2。
    除根结点外,每个结点对应一个边,边数T=n-1。
    度为1的结点生成一个边,度为2的结点生成两个边,则有T=n1+2*n2
    联立等式,则有T=n1+2*n2=n0+n1+n2-1,得到n0=n2+1
    结论:任意一颗二叉树 度为0的结点数目总是比度为2的结点数目多一个。
    本内容需要 登录 后才能查看
  4. 具有n个结点的完全二叉树的深度为floor(log₂N)+1

    floor(log₂(2^k-1))+1

二叉树类型:

完全二叉树:约定编号从根结点起,自上而下,自左至右依次编号。叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树 。

 

满二叉树:若深度为k的二叉树有2^k-1个结点,则称之为满二叉树。满二叉树属于完全二叉树的一种。

顺序存储

特点

假设有编号为i的结点

若i>1,则该节点的双亲结点为floor(i/2)。

若2i<=n,则该节点的左孩子编号为2i。否则无左孩子。

若2i+1<=n,则该节点的左孩子编号为2i+1。否则无右孩子。

完全二叉树采用顺序结构简单又节省空间,对于不完全二叉树来说若是采取顺序存储结构也必须按照完全二叉树形式存储,也就是要添加不存在的空节点,无疑造成了空间浪费。在最坏的情况下,一个单枝树结构的二叉树需要2^k-1个存储单元。

实现

添加结点

template<typename ElementType>
void Sequence_BTree<ElementType>::Add(ElementType elem)
{
    if (tree==nullptr)
    {
        return;
    }
    length+=1;
    tree=(ElementType*)realloc(tree,sizeof(ElementType)*length);//执行remalloc函数时,自动free(原空间)了
    *(tree+length-1)=elem;
}

获取树的深度

template<typename ElementType>
int Sequence_BTree<ElementType>::GetTreeDepth()
{
    return (int)floorf(log2f(length))+1;//完全二叉树
}

遍历方式

以ABCDEFGHI字符集依次加入树中,创建一颗完全二叉树。如图所示:

层序遍历

由于顺序存储结构的二叉树地址是连续的。所以它的层序遍历就是按照其在数组的地址顺序直接输出结点。

for (size_t i = 0; i < length; i++)
        {
            std::cout<<*(tree+i)<<std::ends;
        }
        cout<<endl;

 

 

【递归】先序遍历

先输出当前结点,再遍历左子树,直到左子树遍历到底。最后向上往回遍历右子树,继续重复以上操作。输出序列:ABDHIECFG

特点:每个结点的输出一定先于其左右孩子。

template<typename ElementType>
void Sequence_BTree<ElementType>::PreorderTraverseByRecursion(int index)
{
    //遍历到空结点,则递归-回归,往回走。
    if (index>=length)
    {
        return ;
    }
    int nodeNum = index+1;//index>=0 nodeNum>=1
    int leftChild=nodeNum*2-1;//计算左孩子在数组上的索引
    int rightChild=leftChild+1;//计算右孩子在数组上的索引
    printf("NodeNumber:%d Value:%d\n",nodeNum,tree[index]);//先输出当前结点
    //递归
    PreorderTraverseByRecursion(leftChild);//再遍历左子树
    PreorderTraverseByRecursion(rightChild);//再遍历右子树
}
过程图
递归-中序遍历
先遍历当前结点的左子树,直到左子树遍历到底再往回依次输出结点并遍历右子树,继续重复以上操作。输出序列:HDIBEAFCG
特点:每个结点的输出一定晚于其左孩子,早于其右孩子。
template<typename ElementType>
void Sequence_BTree<ElementType>::InorderTraverseByRecursion(int index)
{
    if (index>=length)
    {
        return ;
    }
    int nodeNum = index+1;
    int leftChild=nodeNum*2-1;
    int rightChild=leftChild+1;
    InorderTraverseByRecursion(leftChild);
    printf("NodeNumber:%d Value:%d\n",nodeNum,tree[index]);
    InorderTraverseByRecursion(rightChild);
}
递归-后序遍历
先遍历当前结点的左右子树, 直到左右子树遍历到底再往回依次输出结点,继续重复以上操作。输出序列:HIDEBFGCA
特点:每个结点的输出一定晚于其左右孩子。
template<typename ElementType>
void Sequence_BTree<ElementType>::PostorderTraverseByRecursion(int index)
{
    if (index>=length)
    {
        return ;
    }
    int nodeNum = index+1;
    int leftChild=nodeNum*2-1;
    int rightChild=leftChild+1;
    PostorderTraverseByRecursion(leftChild);
    PostorderTraverseByRecursion(rightChild);
    printf("NodeNumber:%d Value:%d\n",nodeNum,tree[index]);
}

其实不管是哪种遍历方式,我们最终的目的就是访问所有的树(子树)的根节点,左孩子,右孩子。在打印过程中需要按一定顺序一定逻辑来暂存我们的元素。在需要的时候将其打印出来即可。而这正是递归的核心思想。

但递归相对比较抽象。为了更清晰理解执行顺序,笔者对三种遍历方式都编写了非递归的循环遍历方式来遍历树。
以左孩子节点为基准,先序遍历是在访问左孩子节点之前打印节点,中序遍历是在左孩子节点压栈之后打印节点,后序遍历是在访问完左右孩子节点之后打印节点。
非递归-先序遍历
template<typename ElementType>
void Sequence_BTree<ElementType>::PreorderTraverseByLogicAnalysis()
{
    int nodeNum = 1;
    stack_Sequence<ElementType> stack_Sequence;
    while (nodeNum<=length)
    {
        //先输出当前结点
        printf("NodeNumber:%d Value:%d\n",nodeNum,tree[nodeNum-1]);
        //计算左右孩子在树中的编号。
        int leftChild=nodeNum*2;
        int rightChild=leftChild+1;
        //说明该节点没有左右子节点了  则将栈顶元素出栈即可。
        if (leftChild-1>=length)
        {
            if (stack_Sequence.isEmpty())
                break;
            nodeNum = stack_Sequence.Pop();
        }
        else
        {
            //前序遍历 先遍历所有节点的左子树。将节点的右孩子压入栈中。
            stack_Sequence.Push(rightChild);
            //左孩子交给下一次遍历
            nodeNum = leftChild;
        }
    }
}

先遍历所有节点的左子树。再将节点的右孩子压入栈中。左孩子交给下一次遍历。等遇到终端节点,则将栈顶元素出栈再交给下一次遍历。重复以上操作,直到遇到了先序遍历输出序列中的最后一个结点,则退出循环。

非递归-中序遍历
template<typename ElementType>
void Sequence_BTree<ElementType>::InorderTraverseByLogicAnalysis()
{
    int nodeNum = 1;
    stack_Sequence<ElementType> stack_Sequence;
    while (1)
    {
        int leftChild=nodeNum*2;
        int rightChild=leftChild+1;
        if (nodeNum-1>=length)
        {
            if (stack_Sequence.isEmpty())
                break;
            nodeNum = stack_Sequence.Pop();//出栈
            printf("NodeNumber:%d Value:%d\n",nodeNum,tree[nodeNum-1]);
            nodeNum = nodeNum*2+1; //访问右子树
        }
        else
        {
            //压入当前节点,并尝试下次将其左子树放入栈中。
            stack_Sequence.Push(nodeNum);
            //即使为空也可占用一次循环 使栈顶元素 即此时循环中节点的父节点出栈并遍历。
            nodeNum=leftChild;
        }
    }
}

压入当前节点,并尝试下次将其左子树放入栈中。即使为空也可占用一次循环 使栈顶元素即此时循环中节点的父节点出栈并遍历。

假设树或某子树度为n, 则一个完全二叉树至多有2^n-1个节点,第i层至多有2i个叶子节点,根节点的左子树至多有2i/2个叶子节点。2i/2个叶子节点有2i个空孩子。又因为每一层节点都等于之前所有节点总和数+1。 所以若由根节点的左子树与根节点组成一颗树,这棵树的叶子节点的下一层空节点总数正好等于其树的所有节点

正因为如此可令左子树全部出栈。每次遇到叶子节点就会操作栈出栈,左空节点使自身出栈,右空节点使左子树祖宗节点出栈。右子树同理,当最后一个叶子节点的空节点进入下一层循环。则此时栈必然为空,退出循环。

非递归-后序遍历
template<typename ElementType>
void Sequence_BTree<ElementType>::PostorderTraverseByLogicAnalysis()
{
    int nodeNum = 1;
    stack_Sequence<ElementType> stack_Sequence;
    int lastnode= -1;//保存上一次出栈的元素
    while (1)
    {
        int leftChild=nodeNum*2;
        int rightChild=leftChild+1;
        if (nodeNum > length)
        {
            if (stack_Sequence.isEmpty())
                break;
            int temp = stack_Sequence.Top();
            stack_Sequence.Pop();
            nodeNum=temp;
            printf("NodeNumber:%d Value:%d\n", nodeNum, tree[nodeNum - 1]);
            //上次从栈顶取出的上一条数据不是该节点的左右孩子节点 。
            if (lastnode!=-1&&lastnode>nodeNum&&nodeNum!=(int)lastnode/2)
            {
                nodeNum = nodeNum * 2;
            }
            else
            {
                //栈中上一条数据是该节点的左右孩子节点 
                //若该节点为左子树则将右子树添加进栈中
                // 否则说明该节点的父节点下的左右子树已经遍历完成 则将nodenum置为大于长度,让下一次循环继续出栈。
                if (nodeNum % 2 == 0)
                {
                    nodeNum += 1;
                }
                else
                {
                    
                    nodeNum=length+1;//让下一次循环继续出栈,下一次出栈的元素就该是父亲节点了。
                }
            }
            //如果该节点的左右孩子为空 若该节点为左子树则将相邻的右节点添加进栈中
            // if (nodeNum > length)
            // {
            //     if (temp % 2 == 0)
            //     {
            //         nodeNum = temp+1;
            //     }
            // }
            lastnode=temp;
        }
        else
        {
            //先将左子树全部压入栈中  右子树在相邻的左节点遍历时,在进行考虑。
            stack_Sequence.Push(nodeNum);
            nodeNum=leftChild;
        }
        
    }
}

 

思想:首先将左子树全部压入栈中  右子树在相邻的左节点遍历时,在进行考虑。当遍历到空节点,则需要判断上次从栈顶取出的上一条数据是不是该节点的左右孩子节点 。若不是左右孩子节点,则遍历其左孩子。若栈中上一条数据是该节点的左右孩子节点

那么若该节点为左子树则将相邻的右节点添加进栈中。如果不是左子树则说明该节点的父节点下的左右子树已经遍历完成 则将nodenum置为大于长度,让下一次循环继续出栈,下一次出栈的元素就该是父亲节点了。((nodeNum % 2 == 0))判断是否属于左孩子。

链式存储

对于那些非完全二叉树,由于顺序存储结构的空间利用率低,因此二叉树一般都采用链式存储结构,用链表结点来存储二叉树中的每一个结点。在链式二叉树中,结点结构通常包括数据域和若干个指针域。

链式二叉树的结构一般分为两种,一种是二叉链,另一种是三叉链。二叉链的结点包含存储数据的变量,存储左孩子的指针以及存储右孩子的指针。而三叉链的结点除了包含存储数据的变量,存储左孩子的指针以及存储右孩子的指针,还包含存储双亲的指针。特别的在二叉链中,若有n个结点,则一定会有n+1个空指针。(通过边与结点关系可推出)

实现

添加结点

template<typename ElementType>
void LinkList_BTree<ElementType>::CreateTree(ElementType *array,int length)
{
    this->length=0;
    for (size_t i = 0; i < length; i++)
    {
        this->Add(*(array+i));
    }
}
template<typename ElementType>
void LinkList_BTree<ElementType>::Add(ElementType elem)
{
    BTreeNode<ElementType> *newNode=new BTreeNode<ElementType>();
    newNode->elemValue=elem;
    lastAdd_Node=newNode;//记录最后一次添加的结点
    if (node==nullptr)
    {
        //树若为空,直接初始化。
        node=newNode;
        length=1;
        return;
    }
    BTreeNode<ElementType> *tar_node=node;
    queue_Sequence<BTreeNode<ElementType>*> queue;
    queue.Enqueue(node);
    //层序遍历 找到为空且编号能够连续的结点。
    while (!queue.isEmpty())
    {
        //每访问一个结点,就将其左右节点进队。先进先出,符合层序遍历。
        tar_node=queue.Dequeue();
        if (tar_node->lchild!=nullptr)
        {
            queue.Enqueue((tar_node->lchild));
        }
        else
        {
            tar_node->lchild=newNode;
            break;
        }
        if (tar_node->rchild!=nullptr)
        {
            queue.Enqueue((tar_node->rchild));
        }
        else
        {
            tar_node->rchild=newNode;
            break;
        }
        
    }

    length+=1;
}

遍历方式

层序遍历

 

每访问一个结点,就将其左右节点进队。先进先出,符合层序遍历

void LayerorderTraverse()
    {
        queue_Sequence<BTreeNode<ElementType>> queue;
        BTreeNode<ElementType> cur_Node;
        queue.Enqueue(*(node));
        while (!queue.isEmpty())
        {
            cur_Node=queue.Dequeue();
            printf("%d ",cur_Node.elemValue);
            if (cur_Node.lchild)
            {
                queue.Enqueue(*(cur_Node.lchild));
            }
            if (cur_Node.rchild)
            {
                queue.Enqueue(*(cur_Node.rchild));
            }
        }
        
    }

 

 

前序遍历
template<typename ElementType>
void LinkList_BTree<ElementType>::PreorderTraverseByRecursion(BTreeNode<ElementType> *_node)
{
    if (_node==nullptr)
    {
        return;
    }
    printf("Value:%d\n",_node->elemValue);
    PreorderTraverseByRecursion(_node->lchild);
    PreorderTraverseByRecursion(_node->rchild);
}
 中序遍历

 

template <typename ElementType>
void LinkList_BTree<ElementType>::InorderTraverseByRecursion(BTreeNode<ElementType> *_node)
{
    if (_node == nullptr)
    {
        return;
    }
    
    InorderTraverseByRecursion(_node->lchild);
    printf("Value:%d\n", _node->elemValue);
    InorderTraverseByRecursion(_node->rchild);
    
}
 后序遍历

 

template <typename ElementType>
void LinkList_BTree<ElementType>::PostorderTraverseByRecursion(BTreeNode<ElementType> *_node)
{
    if (_node == nullptr)
    {
        return;
    }
    
    PostorderTraverseByRecursion(_node->lchild);
    PostorderTraverseByRecursion(_node->rchild);
    printf("Value:%d\n", _node->elemValue);
    
}

运行

主入口程序测试:

#include "IBTree.h"
#include "math.h"
#include <iostream>
using namespace std;
#include "istack.h"
#include "stack_Sequence.h"
#include "Sequence_BTree.h"
#include "queue_Sequence.h"
#include "LinkList_BTree.h"
#include "seq_LinkList.h"
#include "ClueBTree.h"
int main()
{
    int a[]={1,2,3,4,5,6,7,8,9};
    IBTree<int>* tree=new Sequence_BTree<int>(a,9);
    a[0]=1;

    tree->OutPutArray();
    tree->PostorderTraverse();
    
    IBTree<int>* linkListTree=new LinkList_BTree<int>(a,9);
    cout<<"LinkList_BTree:"<<endl;
    linkListTree->Add(10);
    linkListTree->OutPutArray();
    linkListTree->InorderTraverse();
    
    ClueBTree<int>* clueTree=new ClueBTree<int>(a,9);  
    cout<<"ClueBTree:"<<endl;

    clueTree->OutPutArray();
    clueTree->CreateClueTree();
    clueTree->OutputNext(clueTree->linkList.get(4)); 
    system("pause");
    return 0;
}

测试结果:

 

线索二叉树下篇文章再写,先睡了。

线索二叉树 见文章:C/C++线索二叉树(二叉树线索化)

示例下载

来源:诚通网盘 | 提取码:unitymake

 

    作者:Miracle
    来源:麦瑞克博客
    链接:https://www.unitymake.com/archives/programming-life/cpp/3026
    本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0许可协议,转载请注明!
    THE END
    分享
    打赏
    海报
    C/C++二叉树详解(顺序、链式、线索树)
    概述 二叉树是n个节点的有限集合,它或者是空树(n=0),或者是由一个根节点加上两棵分别称左子树和右子树的二叉树组成。即使在结点只有一颗子树的情况下,也……
    <<上一篇
    下一篇>>
    文章目录
    关闭
    目 录