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);//再遍历右子树
}

递归-中序遍历

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);
}

递归-后序遍历

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;
        }
    }
}

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;
        }
        
    }
}

链式存储

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

链式二叉树的结构一般分为两种，一种是二叉链，另一种是三叉链。二叉链的结点包含存储数据的变量，存储左孩子的指针以及存储右孩子的指针。而三叉链的结点除了包含存储数据的变量，存储左孩子的指针以及存储右孩子的指针，还包含存储双亲的指针。特别的在二叉链中，若有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++线索二叉树(二叉树线索化)

示例下载

DS5.二叉树（顺序、链表）.zip:

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

立即下载