C语言数据结构——二叉树

- 日理万妓 2021-12-03 16:43 310阅读 0赞

## 链式存储 ##

**定义结构体**

typedef struct tree
    {
        char data;
        struct tree *Lchild,*Rchild;
    }Tree;

**创建二叉树（采用先序遍历创建，也可采用中序或后序遍历创建）**

> **1.扫描字符序列，输入字符ch**
> 
> **2.如果ch是一个'\#'字符，则表明该二叉树为空树，即T为NULL；否则执行以下操作：**
> 
>  *  **申请一个节点空间**
>  *  **将ch赋给T->data**
>  *  **递归创建T的左子树**
>  *  **递归创建T的右子树**

void CreateTree(Tree *&T)   //先序遍历创建二叉树
    {
        char ch;
        scanf(" %c",&ch);       //输入数据
        if(ch=='#')
            T=NULL;     //ch=='#',节点的度为0或1时
        else
        {
            T = (Tree*)malloc(sizeof(Tree));
            T->data = ch;
            CreateTree(T->Lchild);
            CreateTree(T->Rchild);
        }
    }

## 二叉树的遍历 ##

**1.先序递归遍历**

>  *  **若二叉树为空树，则什么都不做，否则执行以下操作：**
>  *  **访问根节点**
>  *  **先序遍历左子树**
>  *  **先序遍历右子树**

void PreOrder(Tree *T)
    {
        if(T)
        {
            printf("%c\t",T->data);
            PreOrder(T->Lchild);
            PreOrder(T->Rchild);
        }
    }

**2.先序非递归遍历**

> **使用栈的先进后出特性来模拟二叉树的先序遍历，由于非递归遍历使用的自定义栈而非系统栈，所以非递归算法的执行效率更高**
> 
> **先序非递归遍历的主要思想为：**
> 
> 1.  **先让根节点入栈**
> 2.  **再让根节点出栈，并打印数据域，然后压入右子树的根节点，再压入左子树的根节点**
> 3.  **重复执行2步骤，因为先出栈的是左子树的根节点，所以之后的操作会不断的左子树的右孩子（右子树）的根节点，和左孩子的根节点。此步骤相当于递归遍历的递归遍历左子树**
> 4.  **左子树遍历完成，右子树根节点出栈，开始继续2步骤，直至右子树遍历完成**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70][]

void PreOrderTreaverse(Tree *T)    //非递归先序遍历
    {
        if(T)                   //T非空
        {
            Tree *Stack[SIZE];  //初始化栈
            int top = -1;
            Tree *p;
            Stack[++top] = T; //根节点入栈
            while(top!=-1)
            {
                p = Stack[top--];   //出栈并输出栈顶节点
                printf(" %c\t",p->data);
                if(p->Rchild)          //栈顶节点的右孩子存在，则右孩子入栈
                    Stack[++top] = p->Rchild;
                if(p->Lchild)           //栈顶节点的左孩子存在，则左孩子入栈
                    Stack[++top] = p->Lchild;
            }
        }
    }

**3.中序递归遍历**

>  *  **若二叉树为空树，则什么都不做，否则执行以下操作：**
>  *  **中序遍历左子树**
>  *  **访问根节点**
>  *  **中序遍历右子树**

void InOrder(Tree *T)
    {
        if(T)
        {
            InOrder(T->Lchild);
            printf("%c\t",T->data);
            InOrder(T->Rchild);
        }
    }

**4.中序遍历非递归遍历**

> **步骤：**
> 
>  *  **开始根节点入栈**
>  *  **循环执行以下操作：如果栈顶节点左孩子存在，则左孩子入栈；如果栈顶节点左孩子不存在，则出栈并输出栈顶节点，然后检查其右孩子是否存在，如果存在，则右孩子入栈**
>  *  **栈空时结束**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1][]

void InOrderTraverse(Tree *T)
    {
        if(T)
        {
            Tree *Stack[SIZE];
            int top = -1;
            Tree *p = T;
            while(top!=-1||p)
            {
                while(p)            //左孩子存在，则左孩子入栈
                {
                    Stack[++top] = p;
                    p = p->Lchild;
                }
                if(top!=-1)         //在栈不空的情况下出栈并输出出栈节点
                {
                    p = Stack[top--];
                    printf(" %c\t",p->data);
                    p = p->Rchild;
                }
            }
        }
    }

**5.后序递归遍历**

>  *  **若二叉树为空树，则什么都不做，否则执行以下操作：**
>  *  **后序遍历左子树**
>  *  **后序遍历右子树**
>  *  **访问根节点**

void LastOrder(Tree *T)
    {
        if(T)
        {
            LastOrder(T->Lchild);
            LastOrder(T->Rchild);
            printf("%c\t",T->data);
        }
    }

**6.后序非递归遍历**

> **使用两个栈来完成此操作，后序非递归 = 逆后序遍历+逆序**
> 
> **逆后序遍历：先序遍历过程中左右子树遍历顺序交换**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 2][]

void LastOrderTraverse(Tree *T)
    {
        //后序遍历等于先序遍历左右子树交换再逆序
        if(T)
        {
            //定义两个栈，一个用来完成逆后序遍历，另一个用来完成逆序
            Tree *Stack1[SIZE],*Stack2[SIZE];
            int top1 = -1,top2 = -1;
            Tree *p = NULL;
            Stack1[++top1] = T; //根节点入栈
            while(top1!=-1)
            {
    
                p = Stack1[top1--];     //栈顶节点出栈
                Stack2[++top2] = p;     //第二个栈入栈
                if(p->Lchild)
                    Stack1[++top1] = p->Lchild;  //左子树不为空时，入栈
                if(p->Rchild)
                    Stack1[++top1] = p->Rchild;  //右子树不为空时，入栈
            }
            while(top2!=-1)
            {
                p = Stack2[top2--];         //出栈序列即为后序遍历序列
                printf(" %c\t",p->data);
            }
        }
    }

**7.层次遍历**

> **建立循环队列，先将二叉树头节点入队列，然后出队列，访问该节点，如果他有左子树，则将左子树的根节点入队；如果他有右子树，则将右子树的根节点入队。然后出队列，对出队节点访问，如此反复，知道队列为空**

/*
        1.建立一个循环队列
        2.先将二叉树头节点入队，然后出队;
        3.如果它有左子树，则将左子树的根节点入队;如果它有右子树，则将右子树的根节点入队;
        4.出队，对出队节点进行访问，以此反复，直到队列为空
    */
    void Level(Tree *T)             //层次遍历
    {
        Tree *Queue[SIZE];          //定义一个循环队列，用来记录将要访问层次上的节点
        int front = 0,rear = 0;
        Tree *p;
        if(T)
        {
            rear = (rear+1)%SIZE;   //队尾指针+1
            Queue[rear] = T;        //根节点入队
            while(front!=rear)      //当队列不为空时进行循环
            {
                front = (front+1)%SIZE;     //队头指针+1
                p = Queue[front];           //跟节点出队
                printf("%c\t",p->data);
                if(p->Lchild)               //若根节点的左子树不为空
                {
                    rear = (rear+1)%SIZE;
                    Queue[rear] = p->Lchild;    //根节点左子树入队
                }
                if(p->Rchild)
                {
                    rear = (rear+1)%SIZE;
                    Queue[rear] = p->Rchild;    //根节点右子树入队
                }
            }
        }
    }

# 代码实现 #

#include <stdio.h>
    #include <stdlib.h>
    #include <iostream>
    #define ERROR 0
    #define OK 1
    #define SIZE 20
    using namespace std;
    typedef char TElemType;
    typedef struct tree
    {
        TElemType data;
        struct tree *Lchild,*Rchild;
    } Tree;
    typedef struct
    {
        Tree *p;
        int lno;
    } St;
    void CreateTree(Tree *&T);
    void CopyTree(Tree *T,Tree *&Tp);
    int Depth(Tree *T);
    void PreOrder(Tree *T);
    void InOrder(Tree *T);
    void LastOrder(Tree *T);
    void PreOrderTreaverse(Tree *T);
    void InOrderTraverse(Tree *T);
    void LastOrderTraverse(Tree *T);
    void SearchElem(Tree *T,Tree *&q,TElemType n);
    void Trave(Tree *T,int n);
    void Level(Tree *T);
    void MaxWidth(Tree *T,int &w);
    int k = 0;
    int main()
    {
        Tree *T,*Tp = NULL;
        printf("-----二叉树创建成功！-----\n");
        CreateTree(T);
        char ch;
        int n,n1,n2;
        while(true)
        {
            printf("\n请选择你想要执行的操作:\n1.复制二叉树\n2.计算树深度\n3.先序遍历\n4.非递归先序遍历\n5.中序遍历\n6.非递归中序遍历\n7.后序遍历\n8.非递归后序遍历\n9.查找节点\n10.获取指定节点的值\n11.层次遍历\n12.计算二叉树深度\n");
            scanf("%d",&n2);
            switch(n2)
            {
            case 1:
            {
                CopyTree(T,Tp);
                PreOrder(T);
                printf("\n");
                PreOrder(Tp);
                break;
            }
            case 2:
            {
                n = Depth(T);
                printf("该二叉树的深度为:%d\n",n);
                break;
            }
            case 3:
            {
                PreOrder(T);
                break;
            }
            case 4:
            {
                PreOrderTreaverse(T);
                break;
            }
            case 5:
            {
                InOrder(T);
                break;
            }
            case 6:
            {
                InOrderTraverse(T);
                break;
            }
            case 7:
            {
                LastOrder(T);
                break;
            }
            case 8:
            {
                LastOrderTraverse(T);
                break;
            }
            case 9:
            {
                printf("请输入你想要查找的节点值:\n");
                scanf(" %c",&ch);
                SearchElem(T,Tp,ch);
                if(Tp)
                {
                    printf("该节点存在!\n");
                }
                else
                {
                    printf("该节点不存在!\n");
                }
                break;
            }
            case 10:
            {
                printf("请输入查询的位置:\n");
                scanf("%d",&n1);
                Trave(T,n1);
                break;
            }
            case 11:
            {
                Level(T);
                break;
            }
            case 12:
            {
                MaxWidth(T,n1);
                printf("该二叉树的最大宽度为%d\n",n1);
                break;
            }
            default:
            {
                exit(0);
            }
            }
        }
    }
    void CreateTree(Tree *&T)   //先序遍历创建二叉树
    {
        char ch;
        scanf(" %c",&ch);       //输入数据
        if(ch=='#')
            T=NULL;     //ch=='#',节点的度为0或1时
        else
        {
            T = (Tree*)malloc(sizeof(Tree));
            T->data = ch;
            CreateTree(T->Lchild);
            CreateTree(T->Rchild);
        }
    }
    void CopyTree(Tree *T,Tree *&Tp)
    {
        if(T==NULL)
        {
            Tp = NULL;
            return;
        }
        else
        {
            Tp = (Tree*)malloc(sizeof(Tree));
            Tp->data = T->data;
            CopyTree(T->Lchild,Tp->Lchild);
            CopyTree(T->Rchild,Tp->Rchild);
        }
    }
    int Depth(Tree *T)
    {
        int LD,RD;
        if(T==NULL)
        {
            return 0;
        }
        else
        {
            LD = Depth(T->Lchild);
            RD = Depth(T->Rchild);
            return (LD>RD?LD:RD)+1;
        }
    }
    void PreOrder(Tree *T)
    {
        if(T)
        {
            printf("%c\t",T->data);
            PreOrder(T->Lchild);
            PreOrder(T->Rchild);
        }
    }
    void PreOrderTreaverse(Tree *T)    //非递归先序遍历
    {
        if(T)                   //T非空
        {
            Tree *Stack[SIZE];  //初始化栈
            int top = -1;
            Tree *p;
            Stack[++top] = T; //根节点入栈
            while(top!=-1)
            {
                p = Stack[top--];   //出栈并输出栈顶节点
                printf(" %c\t",p->data);
                if(p->Rchild)          //栈顶节点的右孩子存在，则右孩子入栈
                    Stack[++top] = p->Rchild;
                if(p->Lchild)           //栈顶节点的左孩子存在，则左孩子入栈
                    Stack[++top] = p->Lchild;
            }
        }
    }
    void InOrder(Tree *T)
    {
        if(T)
        {
            InOrder(T->Lchild);
            printf("%c\t",T->data);
            InOrder(T->Rchild);
        }
    }
    void InOrderTraverse(Tree *T)
    {
        if(T)
        {
            Tree *Stack[SIZE];
            int top = -1;
            Tree *p = T;
            while(top!=-1||p)
            {
                while(p)            //左孩子存在，则左孩子入栈
                {
                    Stack[++top] = p;
                    p = p->Lchild;
                }
                if(top!=-1)         //在栈不空的情况下出栈并输出出栈节点
                {
                    p = Stack[top--];
                    printf(" %c\t",p->data);
                    p = p->Rchild;
                }
            }
        }
    }
    void LastOrder(Tree *T)
    {
        if(T)
        {
            LastOrder(T->Lchild);
            LastOrder(T->Rchild);
            printf("%c\t",T->data);
        }
    }
    void LastOrderTraverse(Tree *T)
    {
        //后序遍历等于先序遍历左右子树交换再逆序
        if(T)
        {
            //定义两个栈，一个用来完成逆后序遍历，另一个用来完成逆序
            Tree *Stack1[SIZE],*Stack2[SIZE];
            int top1 = -1,top2 = -1;
            Tree *p = NULL;
            Stack1[++top1] = T; //根节点入栈
            while(top1!=-1)
            {
    
                p = Stack1[top1--];     //栈顶节点出栈
                Stack2[++top2] = p;     //第二个栈入栈
                if(p->Lchild)
                    Stack1[++top1] = p->Lchild;  //左子树不为空时，入栈
                if(p->Rchild)
                    Stack1[++top1] = p->Rchild;  //右子树不为空时，入栈
            }
            while(top2!=-1)
            {
                p = Stack2[top2--];         //出栈序列即为后序遍历序列
                printf(" %c\t",p->data);
            }
        }
    }
    /*
        采用先序遍历依次访问每个节点并比较数值，数值相等时将该节点的地址赋值给q
    */
    void SearchElem(Tree *T,Tree *&q,TElemType n)
    {
        if(T)
        {
            if(T->data==n)              //如果T所指节点的data域值等于n，则将T赋值给q
            {
                q = T;
            }
            else
            {
                SearchElem(T->Lchild,q,n);  //遍历左子树查找
                if(!q)              //如果左子树中没有找到，才去右子树查找
                {
                    SearchElem(T->Rchild,q,n);
                }
            }
        }
    }
    /*
        1.定义全局变量k,记录当前访问的节点位置
        2.遍历
    */
    void Trave(Tree *T,int n)       //查找第n个节点的值
    {
        if(T)
        {
            ++k;
            if(k==n)
            {
                printf("第%d个节点的值为:%c\n",n,T->data);
                return ;
            }
            else
            {
                Trave(T->Lchild,n);
                Trave(T->Rchild,n);
            }
        }
    }
    /*
        1.建立一个循环队列
        2.先将二叉树头节点入队，然后出队;
        3.如果它有左子树，则将左子树的根节点入队;如果它有右子树，则将右子树的根节点入队;
        4.出队，对出队节点进行访问，以此反复，直到队列为空
    */
    void Level(Tree *T)             //层次遍历
    {
        Tree *Queue[SIZE];          //定义一个循环队列，用来记录将要访问层次上的节点
        int front = 0,rear = 0;
        Tree *p;
        if(T)
        {
            rear = (rear+1)%SIZE;   //队尾指针+1
            Queue[rear] = T;        //根节点入队
            while(front!=rear)      //当队列不为空时进行循环
            {
                front = (front+1)%SIZE;     //队头指针+1
                p = Queue[front];           //跟节点出队
                printf("%c\t",p->data);
                if(p->Lchild)               //若根节点的左子树不为空
                {
                    rear = (rear+1)%SIZE;
                    Queue[rear] = p->Lchild;    //根节点左子树入队
                }
                if(p->Rchild)
                {
                    rear = (rear+1)%SIZE;
                    Queue[rear] = p->Rchild;    //根节点右子树入队
                }
            }
        }
    }
    /*
        注：要求出最大节点数的层数，可以分别求出每层的节点数，然后从中选出最大的
        1.对于非空树，树根所在的层为第一层，并且从层次遍历算法可知，有一个由当前节点找到左右孩子节点的操作。则如果知道当前节点的层号，就可以推出其左右孩子的层号
        即为当前节点层号+1，进而可以求出所有节点的层号，从而可以求出二叉树的最大层数
        2.遍历每个节点的层号，初始值设为max，则遍历结束后max即为二叉树的最大的宽度
    */
    void MaxWidth(Tree *T,int &w)
    {
        St que[SIZE];           //定义非循环队列
        int front = 0,rear = 0; //队列置空
        int Lno,i,j,n,max;
        Tree *q;
        if(T)                   //队列非空
        {
            ++rear;             //队尾指针+1
            que[rear].p = T;    //根节点入队
            que[rear].lno = 1;  //树根所在层次设置为1
            while(front!=rear)  //当队列不为空时
            {
                ++front;        //队头指针+1
                q = que[front].p;   //根节点出队
                Lno = que[front].lno;   //用Lno存储当前节点的层次
                if(q->Lchild)           //如果左子树不为空
                {
                    ++rear;
                    que[rear].p = q->Lchild;    //左子树根节点入队
                    que[rear].lno = Lno+1;      //根据当前节点的层次可推知其孩子节点的层次
                }
                if(q->Rchild)
                {
                    ++rear;
                    que[rear].p = q->Rchild;
                    que[rear].lno = Lno+1;
                }
            }       //循环结束，Lno中保存的是二叉树的最大层数
            //找出含有节点最多的层中的节点数
            max = 0;
            for(i=1; i<=Lno; i++)
            {
                n = 0;
                for(j=1; j<=rear; j++)
                {
                    if(que[j].lno==i)
                        ++n;
                    if(max<n)
                        max = n;
                }
    
            }
            w = max;
        }
        else
            w = 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70]: /images/20211203/5783b206fa9949caad5df8531a3ccbc8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1]: /images/20211203/01d381a3d60e42cb8de288e3c4dab290.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 2]: /images/20211203/fa82bead690942548eea8b059d3ff96e.png