二叉树树是数据结构中非常重要的组成部分，现就树的十几种基本操作在此做以小结，
都测试过，暂时没有发现什么问题，欢迎大家指正
一些代码的注释也是比较清楚了

一数据结构

#define MAXSIZE 100

//树结点
typedef struct Bitnode{
    char data;		//数据
    int ceng;		//层数
    int flag;		//标记
    struct Bitnode *lchild;		//左子树
    struct Bitnode *rchild;		//右子树
}Bitnode,*BiTree;
 
//链栈结点
typedef struct stack{
    struct Bitnode ch;                                
    struct stack *next;
}Node;

//链栈
typedef Node *Stack;
//链队列
typedef Node *Queue;

//结点总数目
int Count = 0;
//一元结点数目
int Count_1 = 0;
//二元结点数目
int Count_2 = 0;
//叶子结点数目
int Count_0 = 0;

//按照前，中序遍历结果或中，后序遍历结果创建二叉树时，存储输入的遍历结果
char str_qian[100];
char str_zhong[100];
char str_hou[100];

二创建树

1.根据输入扩展先序序列创建二叉树

思路是采用递归，
先输入结点，
若结点数据是空的时候 T 赋值为空，之后会直接返回，
若非空，就开始创建结点，进行数据的赋值，层数的统计，也顺便放一个负责标记元素，以备以后的用处。

//根据扩展先序序列创建树
void CreatTree(BiTree *T,int num){
    char ch;
    //输入结点
    scanf("%c",&ch);
    //是空就返回空，否则建立结点
    if(ch == '#'){
        *T = NULL;
    }else{
        *T = (BiTree)malloc(sizeof(Bitnode));
        //创建失败的话，退出
        if(!*T){
            exit(1);
        }
        //赋值
        (*T)->data = ch;
        //层数
        (*T)->ceng = ++num;
        //某种神秘的标记
        (*T)->flag = 0;
        //开始创建
        CreatTree(&(*T)->lchild,num);
        CreatTree(&(*T)->rchild,num);
        //创建结束即返回，层数-1
        --num;
    }
}

样例输入

ABC##DE#G##F###

用其他方式确定并创建一个二叉树的话，我们应该清楚，必须要有中序遍历的结果，因为我们需要用它来判断我们即将创建的子树的位置（左子树还是右子树），所以，我们就有了以下两种创建二叉树的方法

2.按照前序和中序遍历结果来创建二叉树

我们还是采用的递归创建，传入参数是前序序列，中序序列和前序序列的长度，主要思想是分割中序序列
我们具体的思路是：
先利用前序序列，确定当前子树的根结点，然后在中序序列中寻找该点
之后将中序序列分成了左右子树两部分，分别传入创建左右子树的函数中
当到最后，分成的左(右)子树就剩一个结点时，就可以在创建该结点后，开始返回了

//按照前序和中序遍历结果来创建二叉树
BiTree Creat_Tree_by_qian_zhong(char *qian,char *zhong,int len_qian){
    if(!len_qian){
        return NULL;
    }
    
    //先创建当前情况下的根结点
    BiTree T = (BiTree)malloc(sizeof(Bitnode));
    T->data = qian[0];
    
    //在中序中找根
    char *p = strchr(zhong,qian[0]);

    //左子树长度
    int len = p - zhong;

    //开始创建
    T->lchild = Creat_Tree_by_qian_zhong(qian + 1,zhong,len);
    T->rchild = Creat_Tree_by_qian_zhong(qian + 1 + len,p + 1,len_qian - len - 1);

    return T;
}

样例输入

ABDECFG
DBEACGF

样例输出

DEBGFCA

3.按照中序和后序遍历结果来创建二叉树

和上一种创建方式类似，只不过，我们这次使用的是后序遍历的结果来确定根节点

BiTree Creat_Tree_by_zhong_hou(char *hou,char *zhong,int len_hou){
    if(!len_hou){
        return NULL;
    }
    
    //先建立当前情况下的根
    BiTree T = (BiTree)malloc(sizeof(Bitnode));
    T->data = hou[len_hou-1];
    
    //在中序中寻找根
    char *p = strchr(zhong,hou[len_hou - 1]);

    //计算左子树长度
    int len = p - zhong;

    //开始创建
    T->lchild = Creat_Tree_by_zhong_hou(hou,zhong,len);
    T->rchild = Creat_Tree_by_zhong_hou(hou + len,p + 1,len_hou - len - 1);

    return T;
}

样例输入

DBEACGF
DEBGFCA

样例输出

ABDECFG

三遍历二叉树

1.递归遍历

递归遍历是遍历二叉树中最简单的遍历方法了，不同的遍历方式，其实就是打印结点位置的不同，其他就是简单递归就行

//按照前中后序打印树
void print_tree(BiTree T,int n){
    if(T == NULL){
        return;
    }
    //前序
    if( n == 1)
        printf("%c",T->data);
    
    print_tree(T->lchild,n);
    
    //中序
    if( n == 2)
        printf("%c",T->data);
    
    print_tree(T->rchild,n);
    
    //后序
    if( n == 3)
        printf("%c",T->data);
}

2.非递归遍历

使用非递归遍历二叉树时，我们就要在遍历某个结点的子树时，存储之前遍历过的结点
由于栈这个数据结构先进后出的这个特点，所以我们用它来进行存储

前序

思路是先一直进左子树，遍历的同时完成打印和入栈操作，
当到达叶子结点后，就获取栈顶元素，进入上一级结点的右子树继续遍历，并且将该结点退栈

//非递归前序遍历
void Oder_qian_F(BiTree T){
    Stack S = InitStack();
    BiTree p = T;

    while(p != NULL || !StackEmpty(S)){
        while(p != NULL){
            printf("%c",p->data);
            //入栈
            Push(S,*p);
            //进入左子树
            p = p->lchild;
        }

        //退栈,进右子树
        if(!StackEmpty(S)){
            p = Findhead(S);
            p = p->rchild;
            Pop(S);
        }
    }
}

中序

思路:先遍历左子树并全部入栈，到叶子节点后，获取栈顶元素结点并打印，然后进入结点右子树，同时栈顶出栈

//非递归中序遍历
void Oder_zhong_F(BiTree T){
    Stack S = InitStack();
    BiTree p = T;
    while(p != NULL || !StackEmpty(S)){
        //先一路遍历左子树到底，全部入栈
        while(p != NULL){
            Push(S,*p);
            p = p->lchild;
        }
        //左子树到底后，开始打印结点，出栈
        if(!StackEmpty(S)){
            p = Findhead(S);
            printf("%c",p->data);
            p = p->rchild;
            Pop(S);
        }
    }
}

后序

后序稍微麻烦的一点就是多了一个要指向上一个结点的q，用来判断是否已经遍历过那个结点
因为后序遍历的顺序是 “左右根” ，所以我们要用 q 来判断是否遍历过我们即将遍历的结点，
如：我们刚遍历过“左”和“右”，回到“根”后，就要判断是否遍历过“右”，如果没有这一步的话，又会继续遍历“右”，这样就进入了一个死循环

//非递归后序遍历
void Oder_hou_F(BiTree T){
    Stack S = InitStack();
    BiTree p = T;
    BiTree q = T;
    
    while(p != NULL || !StackEmpty(S)){
        //先左子树全部入栈
        while(p != NULL){
            Push(S,*p);
            p = p->lchild;
        }
        
        if(!StackEmpty(S)){
            p = Findhead(S);
            //如果右子树为空，就打印当前
            //而右子树若等于q，即上一步的结点，说明刚从右子树返回，则打印，并出栈
            if((p->rchild == NULL) || (p->rchild->data == q->data)){
                printf("%c",p->data);
                q = p;
                p = NULL;
                Pop(S);
            }else{
                //进入右子树
                p = p->rchild;
            }
        }
    }
}

层次

层序遍历就用到了先进先出的队列

//层序遍历
void Oder_ceng(BiTree T){
    //初始化队列
    Queue q = InitQueue();
    BiTree tmp;
    //首先，根节点入队
    EnterQueue(q,*T);
    while(!QueueEmpty(q)){
        //队尾出队
        tmp = DeleteQueue(q);
        printf("%c",tmp->data);
        //入队
        if(tmp->lchild != NULL){
            EnterQueue(q,*tmp->lchild);
        }
        if(tmp->rchild != NULL){
            EnterQueue(q,*tmp->rchild);
        }
    }
}

样例输入

ABC##DE#G##F###
样例输出
ABCDEFG

四其他操作

1.交换左右子树

我们可以递归遍历每个结点，然后每一步都交换其左右子树即可

//交换指针函数
void swap(BiTree *l,BiTree *r){
    BiTree tmp;
    tmp = *l;
    *l = *r;
    *r = tmp;
}

//递归交换左右子树
BiTree ChangeLeftRightChild(BiTree T){
    if(T == NULL){
        return NULL;
    }
    
    //交换指针
    swap(&(T->lchild),&(T->rchild));

    ChangeLeftRightChild(T->lchild);
    ChangeLeftRightChild(T->rchild);
    return T;
}

交换左右子树并输出交换后，先、中、后序遍历结果
输入

ABC##DE#G##F###

输出

ABDFEGC
AFDGEBC
FGEDCBA

2.寻找最近共同祖先

用递归遍历，先遍历左子树，遇到一个符合的叶子结点的话就开始返回，
在返回的每一步都在其右子树中向下遍历，寻找另一个结点，未找到就继续向前返回，
当找到共同的祖先，就一直向上返回这个结点，直到第一层的函数最终返回给调用该函数的地方

//寻找共同祖先
BiTree Get_Same_Parent(BiTree T,BiTree node_1,BiTree node_2){

    if(T == NULL || node_1 == NULL || node_2 == NULL){
        return NULL;
    }
    
    //找到其中的某个结点就开始返回
    if(T->data == node_1->data || T->data == node_2->data){
        return T;
    }

    //进入左右子树寻找
    BiTree left = Get_Same_Parent(T->lchild,node_1,node_2);
    BiTree right = Get_Same_Parent(T->rchild,node_1,node_2);

    //到达叶子结点
    if(left != NULL && right != NULL){
        return T;
    }

    if(left == NULL){
        return right;
    }else{
        return left;
    }
}

样例输入

ABC##DE#G##F###
C F

样例输出

B

3.根结点到叶子结点的路径

这个我们可以使用后序遍历的方法，遇到叶子结点，就反向输出栈就可以了

//根结点到叶子结点的路径
void find_leaves_road(BiTree T){
    Stack S = InitStack();
    BiTree t = T;
    BiTree q = T;

    while(t != NULL || !StackEmpty(S)){
        while(t != NULL){
            Push(S,*t);
            t = t->lchild;
        }

        if(!StackEmpty(S)){
            t = Findhead(S);

            if((t->rchild == NULL) || (t->rchild->data == q->data)){
                /* printf("%c\n",t->data); */
                if((t->lchild == NULL) && (t->rchild == NULL))
                    print_stack_t(S);
                q = t;
                t = NULL;
                Pop(S);
            }else{
                t = t->rchild;
            }
        }
    }
}

样例输入

AB#DG###CE##FH###

样例输出

G:ABD
E:AC
H:ACF

4.以树的形态递归打印二叉树

要以树状形态打印树的话，我们需要按照树结点的所在层数，来控制打印空格数目，以达到打印出树状的形态

//以树的形态递归打印二叉树, h 为层数
void print_by_tree(BiTree root,int h){
    if(root == NULL){
        return;
    }

    //先打印右子树
    print_by_tree(root->rchild,h+1);
    //层次决定结点左右位置
    for(int i = 0;i < h;i++){ 
        printf("  ");        
    }
    //输出结点
    printf("%c\n",root->data);

    print_by_tree(root->lchild,h+1);
}

输入

AB#D##CE#F###

输出

5.统计结点个数

遍历的同时，根据结点左右子树情况的不同，计算结点类型的数目

//统计结点个数
void PreOrder(BiTree root){
    if(root){
        //结点数目
        Count++;
        //一元结点
        if((root->lchild == NULL && root->rchild != NULL) || (root->rchild == NULL && root->lchild != NULL)){
            Count_1++;
        } 
        //二元结点
        if(root->lchild != NULL && root->rchild != NULL){
            Count_2++;
        }
        //叶子结点
        if(root->lchild == NULL && root->rchild == NULL){
            Count_0++;
        }
        //继续递归遍历左右子树
        PreOrder(root->lchild);
        PreOrder(root->rchild);
    }
}

6.计算某层叶子结点个数

在创建时，已经在结点的数据域里存储了所在的层数，所以只需要在遍历时判断打印就行了

7.打印叶子结点所在层

就是遍历叶子结点时，采用前序遍历，然后多打印一个数据即可

//输入的层数,求所在层叶子结点个数
int quesion;
//某层叶子节点个数
int ans = 0;
//按照前中后序打印树
void print_tree(BiTree T,int n){
    if(T == NULL){
        return;
    }
    
    //打印特定层的叶子结点
    if(n == 5){
        if((T->ceng == quesion) && (T->lchild == NULL) && (T->rchild == NULL) && !T->flag){
            ans++;
            //标记已经算过这个节点
            T->flag = 1;
        }
        print_tree(T->lchild,n);
        print_tree(T->rchild,n);
    }

    //打印结点及其所在层
    if( n == 4){                                                                                                          
        printf("(%c,%d)",T->data,T->ceng);                                                                                
        print_tree(T->lchild,n);                                                                                          
        print_tree(T->rchild,n);                                                                                          
        return; 
    } 

    //前序
    if( n == 1)
        printf("%c",T->data);
    print_tree(T->lchild,n);
    //中序
    if( n == 2)
        printf("%c",T->data);
    print_tree(T->rchild,n);
    //后序
    if( n == 3)
        printf("%c",T->data);
}

8.中序输出叶子

//中序输出叶子
void InOrder(BiTree root){
    if(root){
        InOrder(root->lchild);
        if(root->lchild == NULL && root->rchild == NULL){
            printf("%c",root->data);
        }
        InOrder(root->rchild);
    }
}

五栈操作

下面是手写的一些用到的栈操作的函数，有的函数可能和标准的不太相同

//创建栈
Stack InitStack(void){
    Stack S = (Node*)malloc(sizeof(Node));
    S->next = NULL;
    return S;
}
 
//置空栈
 void NullStack(Stack S){
    S->next = NULL;
}

//出栈
void Pop(Stack S){
    Stack temp = S->next;
    S->next = temp->next;
}

//入栈
void Push(Stack S,struct Bitnode c){
    Stack temp = (Node*)malloc(sizeof(Node));
    temp->ch = c;
    temp->next = S->next;
    S->next = temp;
}

//返回栈顶
BiTree Findhead(Stack S){
    Stack temp = S->next;
    return &(temp->ch);
}

//打印栈顶
void PrintStackTop(Stack S){
    Stack temp = S->next;
    printf("%c",temp->ch.data);
}

//检验栈是否为空
int StackEmpty(Stack S){
    if(S->next == NULL){
        return 1;
    }else{
        return 0;
    }
}

//打印栈
void print_stack(Stack S){
    Stack t = S;
    printf("Stack:1\n");
    while(t){
        printf("\nt = %c %d\n",t->ch.data,t->ch.data);
        t = t->next;
    }
}

//倒序打印栈
void print_stack_t(Stack S){
    Stack t = S;
    char str[MAXSIZE];
    int i = 0;
    while(t){
        str[i++] = t->ch.data;
        t = t->next;
    }

    int j = i - 1;
    printf("%c:",str[1]);

    while(j > 1){
        printf("%c",str[j--]);
    }
    printf("\n");
}

六队列操作

下面是手写的队列操作

//创建队列
Queue InitQueue(){
    Queue p = (Node*)malloc(sizeof(Node));
    p->next = NULL;
    return p;
}

//添加元素
void EnterQueue(Queue q,struct Bitnode c){
    Queue tmp = q;
    while(tmp->next != NULL){
        tmp = tmp->next;
    }

    Queue p = (Node*)malloc(sizeof(Node));
    p->ch = c;
    p->next = NULL;

    tmp->next = p;
}

//出队列
BiTree DeleteQueue(Queue q){
    Queue tmp = q->next;
    q->next = tmp->next;
    return &(tmp->ch);
}

//判断队列是否为空
int QueueEmpty(Queue q){
    if(q->next == NULL){
        return 1;
    }else{
        return 0;
    }
}

//打印队列
void print_Queue(Queue q){
    printf("Queue:\n");
    while(q->next != NULL){
        printf("%c %d\n",q->next->ch.data,q->next->ch.data);
        q = q->next;
    }
}

七主函数

int main(){
    BiTree T;
    
    //根据扩展先序序列创建一个二叉树
    //层数
    int num = 0;
    CreatTree(&T,num);
    
    //寻找叶子结点到根结点的路径
    find_leaves_road(T);    

    /*
    //寻找最近共同祖先
    getchar();
    BiTree node_1 = (BiTree)malloc(sizeof(Bitnode));
    BiTree node_2 = (BiTree)malloc(sizeof(Bitnode));
    
    char ch,a[10];
    int i = 0;
    while((ch = getchar()) != '\n'){
        if(ch == ' '){
            continue;
        }
        a[i] = ch;
        i++;
    }
    node_1->data = a[0];
    node_2->data = a[1];

    BiTree parent = Get_Same_Parent(T,node_1,node_2);
    if(parent != NULL)
    printf("%c\n",parent->data);  
    */

    /*
    //交换左右子树
    T = ChangeLeftRightChild(T);
    for(int i = 1;i < 4;i++){
        print_tree(T,i);
        printf("\n");
    }
    */

    /*
    //按照前序和中序遍历序列创建二叉树
    scanf("%s%s",str_qian,str_zhong);
    T = Creat_Tree_by_qian_zhong(str_qian,str_zhong,strlen(str_qian));
    print_tree(T,3);
    printf("\n");
    */

    //按照中序和后序遍历序列创建二叉树
    /* scanf("%s%s",str_zhong,str_hou);
       T = Creat_Tree_by_zhong_hou(str_hou,str_zhong,strlen(str_hou));
       print_tree(T,1);    
       printf("\n");
    */

    //树状打印
    /* int h = 1; 
      print_by_tree(T,h);
    */

    //统计结点
    /* PreOrder(T); 
       printf("%d %d %d\n",Count_0,Count_1,Count_2);
    */ 

    //中序输出叶子
    /* InOrder(T); 
       printf("\n");
    */
    
    //打印树
    /*
    int i;
    for(i = 1;i < 4;i++){
        print_tree(T,i);
        printf("\n");
    }
    */

    //非递归前序遍历
    /* Oder_qian_F(T); 
       printf("\n"); 
    */
    
    //非递归中序遍历
    /* Oder_zhong_F(T); 
       printf("\n"); 
    */

    //非递归后序遍历
    /* Oder_hou_F(T); */ 
    /* printf("\n"); */ 
    

    //层序遍历
    /* Oder_ceng(T); 
       printf("\n"); 
    */
    
    //输出结点和其所在层
    /* print_tree(T,4); 
       printf("\n"); 
    */

    //计算某层叶子结点个数
    /* scanf("%d",&quesion);
       print_tree(T,5);
       printf("%d\n",ans); 
    */

    return 0;
}

数据结构——二叉树的多种操作（C语言实现）

文章目录

一数据结构

二创建树

1.根据输入扩展先序序列创建二叉树

2.按照前序和中序遍历结果来创建二叉树

3.按照中序和后序遍历结果来创建二叉树

三遍历二叉树

1.递归遍历

2.非递归遍历

前序

中序

后序

层次

四其他操作

1.交换左右子树

2.寻找最近共同祖先

3.根结点到叶子结点的路径

4.以树的形态递归打印二叉树

5.统计结点个数

6.计算某层叶子结点个数

7.打印叶子结点所在层

8.中序输出叶子

五栈操作

六队列操作

七主函数

文章目录

一 数据结构

二 创建树

1.根据输入扩展先序序列创建二叉树

2.按照前序和中序遍历结果来创建二叉树

3.按照中序和后序遍历结果来创建二叉树

三 遍历二叉树

1.递归遍历

2.非递归遍历

前序

中序

后序

层次

四 其他操作

1.交换左右子树

2.寻找最近共同祖先

3.根结点到叶子结点的路径

4.以树的形态递归打印二叉树

5.统计结点个数

6.计算某层叶子结点个数

7.打印叶子结点所在层

8.中序输出叶子

五 栈操作

六 队列操作

七 主函数

一数据结构

二创建树

三遍历二叉树

四其他操作

五栈操作

六队列操作

七主函数