文章目录

一 数据结构二 创建树1.根据输入扩展先序序列创建二叉树2.按照前序和中序遍历结果来创建二叉树3.按照中序和后序遍历结果来创建二叉树 三 遍历二叉树1.递归遍历2.非递归遍历前序中序后序层次 四 其他操作1.交换左右子树2.寻找最近共同祖先3.根结点到叶子结点的路径4.以树的形态递归打印二叉树5.统计结点个数6.计算某层叶子结点个数7.打印叶子结点所在层8.中序输出叶子 五 栈操作六 队列操作七 主函数 二叉树树是数据结构中非常重要的组成部分，现就树的十几种基本操作在此做以小结， 都测试过，暂时没有发现什么问题，欢迎大家指正 一些代码的注释也是比较清楚了

一 数据结构

#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###

输出

C F E A D B

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