【数据结构】树代码实现
目录
树
三种表示方法
- 孩子表示法
- 父亲表示法
- 孩子兄弟表示法
孩子表示法：
当前节点对应的孩子是谁
一对多：我们要存放的是所有节点存放的孩子，存放所有节点的东西是数组，由于存放的孩子的数量不固定，所以选用链表。
选用结构体数组。
#include <stdio.h>
#include <stdlib.h>
typedef struct Child{
struct Child*next;//指向下一个节点，指向孩子。
int data;//存放数据域
}Node;
Node * node_array[20];
int size;//定义当前元素个数
//若要考虑扩容的话可以考虑最大元素个数，不扩容的话可以不写，此处不写。
void Init(int key);
void Great_tree(int parent,int key);
int find_parent(int parent);
int main(){
Init(1);
Great_tree(1,2);
Great_tree(1,3);
Great_tree(1,4);
Great_tree(2,5);
Great_tree(2,6);
Great_tree(3,7);
for(int i = 0; i < size; i++){
printf("父节点为：%d",node_array[i]->data);
Node* temp = node_array[i]->next;
while(temp != NULL){
printf("子节点为：%d",temp->data);
temp = temp->next;
}
printf("\n");
}
}
/*
初始化：给一个根节点
int key根节点的值
*/
void Init(int key){
size = 0;
node_array[size] = (Node*)malloc(sizeof(Node));
node_array[size]->data = key;
node_array[size]->next = NULL:
size++;
}
/*
构建树的过程
给一个父节点，并告诉父节点的孩子是谁。
int parent：父节点
int key：当前节点对应的孩子
*/
void Great_tree(int parent,int key){
//找父亲
int index = find_parent(parent);
//父节点存在的话把孩子节点存进去
if(-1 == index){
//
}
else{
//把孩子作为新的节点加入到数组当中
node_array[size] = (Node*)malloc(sizeof(Node));
node_array[size]->data = key;
node_array[size]->next = NULL:
size++;
Node * new_node = (Node*)malloc(sizeof(Node));
new_node->data = key;
new_node->next = node_array[index]->next;//头插
node_array[index]->next = new_node;
}
}
/*
找到父亲节点的下标
*/
int find_parent(int parent){
for(int i = 0;i < size;i++){
if(node_array[i]->data == parent){
return i;
}
}else return -1;
}
/*
输出
*/
void print(){
//写到main函数里了
}
image
双亲表示法
父亲表示法
当前节点对应的父亲是谁，数据关系是一对一的。
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode{
int data;//树中存放的数组
int parent;//当前数据对应的父节点是谁 根节点的父节点不存在定义为-1
}Node;
Node* node[5];//定义一个结构体数组
/*
Node* node[5] 声明了一个数组，数组名为 node，数组大小为 5，每个元素都是指向 Node 类型的指针。这意味着这是一个指针数组，它可以保存 5 个指向结构体 Node 的指针。
*/
int size;//当前元素个数
int main(){
Init(5);
insert_child(4,5);
insert_child(3,4);
}
void Init(int key);
void insert_child(int key,int parent_node);
int find_parent(int parent);
void Init(int key){
size = 0;//父节点从0开始
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = key;
new_node->parent = -1;
node[size] = new_node;
size++;
}
/*
int key 当前节点是谁
int parent_node 当前的父节点是谁
*/
void insert_child(int key,int parent_node){
//判断是否已经满了
if(size == 5){
//满了，不插入
}
else{
//还是要先找当前节点的父节点
int parent_index = find_parent(Parent_node);
if(parent_index == -1){
return;
}else{
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = key;
new_node->parent = parent_index;
node[size] = new_node;
size++;
}
}
}
/*
找到父亲节点的下标
*/
int find_parent(int parent){
for(int i = 0;i < size;i++){
if(node_array[i]->data == parent){
return i;
}
}else return -1;
}孩子兄弟表示法
本质是二叉树
#include<stdio.h>
#include<stdlib.h>
typedef struct ChildBro{
struct ChildBro* child;//孩子指针
struct ChildBro* sibling;//兄弟指针
int key;//数据
}Node;
Node* root;//指向根节点的指针，不能动
//初始化根节点
void Init(int key){
root = (Node*)malloc(sizeof(Node));
root->key = key;
root->child = NULL;
root->sibling = NULL:
}
/*
int key 当前节点
int parent 当前节点的父亲
*/
void insert(int key,int parent){
Node* template;//先定位父节点是谁
//查找父节点的位置
//二叉树查找需要用到递归：先空着，假设已经找到了
if(tempNode == NULL){
}else{
if(tempNode->child == NULL){
Node* node = (Node*)malloc(sizeof(Node));
node->key = key;
node->child = NULL;
node->sibling = NULL;
tempNode->child = node;
}
else{
//如果孩子已经有了则插入到孩子的兄弟位置
tempNode = tempNode->child;
Node* node = (Node*)malloc(sizeof(Node));
node->key = key;
node->child = NULL;
node->sibling = NULL;
tempNode->child = node;
//插入到孩子的兄弟位置只需要头插就行
node->sibling = tempNode->sibling;
tempNode->sibling = node;
}
}
}PS：指针数组和数组指针回顾
Q:什么是数组指针，什么是指针数组?
数组指针是一种指针变量，它指向一个数组。它可以让我们通过指针来访问数组的元素。
举个例子：
int arr[5] = {1, 2, 3, 4, 5};
int *ptr = arr; // ptr 指向 arr 数组的第一个元素
printf("%d\n", *ptr); // 输出 1
ptr++; // 指向下一个元素
printf("%d\n", *ptr); // 输出 2
指针数组是一个数组，其中的每一个元素都是指针。它可以让我们存储多个指针。
举个例子：
int a = 1, b = 2, c = 3;
int *ptrArr[3] = {&a, &b, &c}; // ptrArr 数组存储三个指向 int 类型变量的指针
printf("%d\n", *ptrArr[0]); // 输出 1
printf("%d\n", *ptrArr[1]); // 输出 2
从上面例子可以看出，数组指针是指向数组的指针，而指针数组是存储指针的数组。
Q:int *[5] arr;和int (*)[5] arr;有什么区别吗？
int *[5] arr; 和 int (*)[5] arr; 这两种声明方式都声明了一个指针数组，它们的区别在于括号的位置。
int *[5] arr;表示定义了一个大小为 5 的数组，每个元素都是指向 int 类型的指针。int (*arr)[5];表示定义了一个指向大小为 5 的 int 数组的指针。
两种方式都是声明了一个指针数组，但是第一种方式指明了每个元素是指针，第二种方式指明了整个数组是指针。
在使用上也有一些差别，第一种方式可以直接通过数组下标来访问每个元素，第二种方式需要先取值在访问数组。
int a = 1, b = 2, c = 3;
int *arr[5] = {&a, &b, &c};
printf("%d\n", *arr[0]); // 输出 1
int (*ptr)[5] = &arr;
printf("%d\n", *(*ptr)[0]); // 输出 1
总之，第一种方式是定义了一个数组指针，第二种方式是定义了一个指向数组的指针。
树
二叉树顺序结构实现_BiTreeArray.c
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */
#define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int TElemType; /* 树结点的数据类型，目前暂定为整型 */
typedef TElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根结点 */
typedef struct
{
int level,order; /* 结点的层,本层序号(按满二叉树计算) */
}Position;
TElemType Nil=0; /* 设整型以0为空 */
Status visit(TElemType c)
{
printf("%d ",c);
return OK;
}
/* 构造空二叉树T。因为T是固定数组，不会改变，故不需要& */
Status InitBiTree(SqBiTree T)
{
int i;
for(i=0;i<MAX_TREE_SIZE;i++)
T[i]=Nil; /* 初值为空 */
return OK;
}
/* 按层序次序输入二叉树中结点的值(字符型或整型), 构造顺序存储的二叉树T */
Status CreateBiTree(SqBiTree T)
{
int i=0;
printf("请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≤%d:\n",MAX_TREE_SIZE);
while(i<10)
{
T[i]=i+1;
if(i!=0&&T[(i+1)/2-1]==Nil&&T[i]!=Nil) /* 此结点(不空)无双亲且不是根 */
{
printf("出现无双亲的非根结点%d\n",T[i]);
exit(ERROR);
}
i++;
}
while(i<MAX_TREE_SIZE)
{
T[i]=Nil; /* 将空赋值给T的后面的结点 */
i++;
}
return OK;
}
#define ClearBiTree InitBiTree /* 在顺序存储结构中，两函数完全一样 */
/* 初始条件: 二叉树T存在 */
/* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */
Status BiTreeEmpty(SqBiTree T)
{
if(T[0]==Nil) /* 根结点为空,则树空 */
return TRUE;
else
return FALSE;
}
/* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
int BiTreeDepth(SqBiTree T)
{
int i,j=-1;
for(i=MAX_TREE_SIZE-1;i>=0;i--) /* 找到最后一个结点 */
if(T[i]!=Nil)
break;
i++;
do
j++;
while(i>=powl(2,j));/* 计算2的j次幂。 */
return j;
}
/* 初始条件: 二叉树T存在 */
/* 操作结果: 当T不空,用e返回T的根,返回OK;否则返回ERROR,e无定义 */
Status Root(SqBiTree T,TElemType *e)
{
if(BiTreeEmpty(T)) /* T空 */
return ERROR;
else
{
*e=T[0];
return OK;
}
}
/* 初始条件: 二叉树T存在,e是T中某个结点(的位置) */
/* 操作结果: 返回处于位置e(层,本层序号)的结点的值 */
TElemType Value(SqBiTree T,Position e)
{
return T[(int)powl(2,e.level-1)+e.order-2];
}
/* 初始条件: 二叉树T存在,e是T中某个结点(的位置) */
/* 操作结果: 给处于位置e(层,本层序号)的结点赋新值value */
Status Assign(SqBiTree T,Position e,TElemType value)
{
int i=(int)powl(2,e.level-1)+e.order-2; /* 将层、本层序号转为矩阵的序号 */
if(value!=Nil&&T[(i+1)/2-1]==Nil) /* 给叶子赋非空值但双亲为空 */
return ERROR;
else if(value==Nil&&(T[i*2+1]!=Nil||T[i*2+2]!=Nil)) /* 给双亲赋空值但有叶子（不空） */
return ERROR;
T[i]=value;
return OK;
}
/* 初始条件: 二叉树T存在,e是T中某个结点 */
/* 操作结果: 若e是T的非根结点,则返回它的双亲,否则返回＂空＂ */
TElemType Parent(SqBiTree T,TElemType e)
{
int i;
if(T[0]==Nil) /* 空树 */
return Nil;
for(i=1;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e) /* 找到e */
return T[(i+1)/2-1];
return Nil; /* 没找到e */
}
/* 初始条件: 二叉树T存在,e是T中某个结点 */
/* 操作结果: 返回e的左孩子。若e无左孩子,则返回＂空＂ */
TElemType LeftChild(SqBiTree T,TElemType e)
{
int i;
if(T[0]==Nil) /* 空树 */
return Nil;
for(i=0;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e) /* 找到e */
return T[i*2+1];
return Nil; /* 没找到e */
}
/* 初始条件: 二叉树T存在,e是T中某个结点 */
/* 操作结果: 返回e的右孩子。若e无右孩子,则返回＂空＂ */
TElemType RightChild(SqBiTree T,TElemType e)
{
int i;
if(T[0]==Nil) /* 空树 */
return Nil;
for(i=0;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e) /* 找到e */
return T[i*2+2];
return Nil; /* 没找到e */
}
/* 初始条件: 二叉树T存在,e是T中某个结点 */
/* 操作结果: 返回e的左兄弟。若e是T的左孩子或无左兄弟,则返回＂空＂ */
TElemType LeftSibling(SqBiTree T,TElemType e)
{
int i;
if(T[0]==Nil) /* 空树 */
return Nil;
for(i=1;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e&&i%2==0) /* 找到e且其序号为偶数(是右孩子) */
return T[i-1];
return Nil; /* 没找到e */
}
/* 初始条件: 二叉树T存在,e是T中某个结点 */
/* 操作结果: 返回e的右兄弟。若e是T的右孩子或无右兄弟,则返回＂空＂ */
TElemType RightSibling(SqBiTree T,TElemType e)
{
int i;
if(T[0]==Nil) /* 空树 */
return Nil;
for(i=1;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e&&i%2) /* 找到e且其序号为奇数(是左孩子) */
return T[i+1];
return Nil; /* 没找到e */
}
/* PreOrderTraverse()调用 */
void PreTraverse(SqBiTree T,int e)
{
visit(T[e]);
if(T[2*e+1]!=Nil) /* 左子树不空 */
PreTraverse(T,2*e+1);
if(T[2*e+2]!=Nil) /* 右子树不空 */
PreTraverse(T,2*e+2);
}
/* 初始条件: 二叉树存在 */
/* 操作结果: 先序遍历T。 */
Status PreOrderTraverse(SqBiTree T)
{
if(!BiTreeEmpty(T)) /* 树不空 */
PreTraverse(T,0);
printf("\n");
return OK;
}
/* InOrderTraverse()调用 */
void InTraverse(SqBiTree T,int e)
{
if(T[2*e+1]!=Nil) /* 左子树不空 */
InTraverse(T,2*e+1);
visit(T[e]);
if(T[2*e+2]!=Nil) /* 右子树不空 */
InTraverse(T,2*e+2);
}
/* 初始条件: 二叉树存在 */
/* 操作结果: 中序遍历T。 */
Status InOrderTraverse(SqBiTree T)
{
if(!BiTreeEmpty(T)) /* 树不空 */
InTraverse(T,0);
printf("\n");
return OK;
}
/* PostOrderTraverse()调用 */
void PostTraverse(SqBiTree T,int e)
{
if(T[2*e+1]!=Nil) /* 左子树不空 */
PostTraverse(T,2*e+1);
if(T[2*e+2]!=Nil) /* 右子树不空 */
PostTraverse(T,2*e+2);
visit(T[e]);
}
/* 初始条件: 二叉树T存在 */
/* 操作结果: 后序遍历T。 */
Status PostOrderTraverse(SqBiTree T)
{
if(!BiTreeEmpty(T)) /* 树不空 */
PostTraverse(T,0);
printf("\n");
return OK;
}
/* 层序遍历二叉树 */
void LevelOrderTraverse(SqBiTree T)
{
int i=MAX_TREE_SIZE-1,j;
while(T[i]==Nil)
i--; /* 找到最后一个非空结点的序号 */
for(j=0;j<=i;j++) /* 从根结点起,按层序遍历二叉树 */
if(T[j]!=Nil)
visit(T[j]); /* 只遍历非空的结点 */
printf("\n");
}
/* 逐层、按本层序号输出二叉树 */
void Print(SqBiTree T)
{
int j,k;
Position p;
TElemType e;
for(j=1;j<=BiTreeDepth(T);j++)
{
printf("第%d层: ",j);
for(k=1;k<=powl(2,j-1);k++)
{
p.level=j;
p.order=k;
e=Value(T,p);
if(e!=Nil)
printf("%d:%d ",k,e);
}
printf("\n");
}
}
int main()
{
Status i;
Position p;
TElemType e;
SqBiTree T;
InitBiTree(T);
CreateBiTree(T);
printf("建立二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
i=Root(T,&e);
if(i)
printf("二叉树的根为：%d\n",e);
else
printf("树空，无根\n");
printf("层序遍历二叉树:\n");
LevelOrderTraverse(T);
printf("前序遍历二叉树:\n");
PreOrderTraverse(T);
printf("中序遍历二叉树:\n");
InOrderTraverse(T);
printf("后序遍历二叉树:\n");
PostOrderTraverse(T);
printf("修改结点的层号3本层序号2。");
p.level=3;
p.order=2;
e=Value(T,p);
printf("待修改结点的原值为%d请输入新值:50 ",e);
e=50;
Assign(T,p,e);
printf("前序遍历二叉树:\n");
PreOrderTraverse(T);
printf("结点%d的双亲为%d,左右孩子分别为",e,Parent(T,e));
printf("%d,%d,左右兄弟分别为",LeftChild(T,e),RightChild(T,e));
printf("%d,%d\n",LeftSibling(T,e),RightSibling(T,e));
ClearBiTree(T);
printf("清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
i=Root(T,&e);
if(i)
printf("二叉树的根为：%d\n",e);
else
printf("树空，无根\n");
return 0;
}
二叉树链式结构实现_BiTreeLink.c
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
/* 用于构造二叉树********************************** */
int treeIndex=1;
typedef char String[24]; /* 0号单元存放串的长度 */
String str;
Status StrAssign(String T,char *chars)
{
int i;
if(strlen(chars)>MAXSIZE)
return ERROR;
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
return OK;
}
}
/* ************************************************ */
typedef char TElemType;
TElemType Nil=' '; /* 字符型以空格符为空 */
Status visit(TElemType e)
{
printf("%c ",e);
return OK;
}
typedef struct BiTNode /* 结点结构 */
{
TElemType data; /* 结点数据 */
struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;
/* 构造空二叉树T */
Status InitBiTree(BiTree *T)
{
*T=NULL;
return OK;
}
/* 初始条件: 二叉树T存在。操作结果: 销毁二叉树T */
void DestroyBiTree(BiTree *T)
{
if(*T)
{
if((*T)->lchild) /* 有左孩子 */
DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
if((*T)->rchild) /* 有右孩子 */
DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
free(*T); /* 释放根结点 */
*T=NULL; /* 空指针赋0 */
}
}
/* 按前序输入二叉树中结点的值（一个字符） */
/* #表示空树，构造二叉链表表示二叉树T。 */
void CreateBiTree(BiTree *T)
{
TElemType ch;
/* scanf("%c",&ch); */
ch=str[treeIndex++];
if(ch=='#')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
if(!*T)
exit(OVERFLOW);
(*T)->data=ch; /* 生成根结点 */
CreateBiTree(&(*T)->lchild); /* 构造左子树 */
CreateBiTree(&(*T)->rchild); /* 构造右子树 */
}
}
/* 初始条件: 二叉树T存在 */
/* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */
Status BiTreeEmpty(BiTree T)
{
if(T)
return FALSE;
else
return TRUE;
}
#define ClearBiTree DestroyBiTree
/* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
int BiTreeDepth(BiTree T)
{
int i,j;
if(!T)
return 0;
if(T->lchild)
i=BiTreeDepth(T->lchild);
else
i=0;
if(T->rchild)
j=BiTreeDepth(T->rchild);
else
j=0;
return i>j?i+1:j+1;
}
/* 初始条件: 二叉树T存在。操作结果: 返回T的根 */
TElemType Root(BiTree T)
{
if(BiTreeEmpty(T))
return Nil;
else
return T->data;
}
/* 初始条件: 二叉树T存在，p指向T中某个结点 */
/* 操作结果: 返回p所指结点的值 */
TElemType Value(BiTree p)
{
return p->data;
}
/* 给p所指结点赋值为value */
void Assign(BiTree p,TElemType value)
{
p->data=value;
}
/* 初始条件: 二叉树T存在 */
/* 操作结果: 前序递归遍历T */
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}
/* 初始条件: 二叉树T存在 */
/* 操作结果: 中序递归遍历T */
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return;
InOrderTraverse(T->lchild); /* 中序遍历左子树 */
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}
/* 初始条件: 二叉树T存在 */
/* 操作结果: 后序递归遍历T */
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild); /* 先后序遍历左子树 */
PostOrderTraverse(T->rchild); /* 再后序遍历右子树 */
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
}
int main()
{
int i;
BiTree T;
TElemType e1;
InitBiTree(&T);
StrAssign(str,"ABDH#K###E##CFI###G#J##");
CreateBiTree(&T);
printf("构造空二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
e1=Root(T);
printf("二叉树的根为: %c\n",e1);
printf("\n前序遍历二叉树:");
PreOrderTraverse(T);
printf("\n中序遍历二叉树:");
InOrderTraverse(T);
printf("\n后序遍历二叉树:");
PostOrderTraverse(T);
ClearBiTree(&T);
printf("\n清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
i=Root(T);
if(!i)
printf("树空，无根\n");
return 0;
}
线索二叉树_ThreadBinaryTree.c
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef char TElemType;
typedef enum {Link,Thread} PointerTag; /* Link=0表示指向左右孩子指针, */
/* Thread=1表示指向前驱或后继的线索 */
typedef struct BiThrNode /* 二叉线索存储结点结构 */
{
TElemType data; /* 结点数据 */
struct BiThrNode *lchild, *rchild; /* 左右孩子指针 */
PointerTag LTag;
PointerTag RTag; /* 左右标志 */
} BiThrNode, *BiThrTree;
TElemType Nil='#'; /* 字符型以空格符为空 */
Status visit(TElemType e)
{
printf("%c ",e);
return OK;
}
/* 按前序输入二叉线索树中结点的值,构造二叉线索树T */
/* 0(整型)/空格(字符型)表示空结点 */
Status CreateBiThrTree(BiThrTree *T)
{
TElemType h;
scanf("%c",&h);
if(h==Nil)
*T=NULL;
else
{
*T=(BiThrTree)malloc(sizeof(BiThrNode));
if(!*T)
exit(OVERFLOW);
(*T)->data=h; /* 生成根结点(前序) */
CreateBiThrTree(&(*T)->lchild); /* 递归构造左子树 */
if((*T)->lchild) /* 有左孩子 */
(*T)->LTag=Link;
CreateBiThrTree(&(*T)->rchild); /* 递归构造右子树 */
if((*T)->rchild) /* 有右孩子 */
(*T)->RTag=Link;
}
return OK;
}
BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p)
{
if(p)
{
InThreading(p->lchild); /* 递归左子树线索化 */
if(!p->lchild) /* 没有左孩子 */
{
p->LTag=Thread; /* 前驱线索 */
p->lchild=pre; /* 左孩子指针指向前驱 */
}
if(!pre->rchild) /* 前驱没有右孩子 */
{
pre->RTag=Thread; /* 后继线索 */
pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */
}
pre=p; /* 保持pre指向p的前驱 */
InThreading(p->rchild); /* 递归右子树线索化 */
}
}
/* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点 */
Status InOrderThreading(BiThrTree *Thrt,BiThrTree T)
{
*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
if(!*Thrt)
exit(OVERFLOW);
(*Thrt)->LTag=Link; /* 建头结点 */
(*Thrt)->RTag=Thread;
(*Thrt)->rchild=(*Thrt); /* 右指针回指 */
if(!T) /* 若二叉树空,则左指针回指 */
(*Thrt)->lchild=*Thrt;
else
{
(*Thrt)->lchild=T;
pre=(*Thrt);
InThreading(T); /* 中序遍历进行中序线索化 */
pre->rchild=*Thrt;
pre->RTag=Thread; /* 最后一个结点线索化 */
(*Thrt)->rchild=pre;
}
return OK;
}
/* 中序遍历二叉线索树T(头结点)的非递归算法 */
Status InOrderTraverse_Thr(BiThrTree T)
{
BiThrTree p;
p=T->lchild; /* p指向根结点 */
while(p!=T)
{ /* 空树或遍历结束时,p==T */
while(p->LTag==Link)
p=p->lchild;
if(!visit(p->data)) /* 访问其左子树为空的结点 */
return ERROR;
while(p->RTag==Thread&&p->rchild!=T)
{
p=p->rchild;
visit(p->data); /* 访问后继结点 */
}
p=p->rchild;
}
return OK;
}
int main()
{
BiThrTree H,T;
printf("请按前序输入二叉树(如:'ABDH##I##EJ###CF##G##')\n");
CreateBiThrTree(&T); /* 按前序产生二叉树 */
InOrderThreading(&H,T); /* 中序遍历,并中序线索化二叉树 */
printf("中序遍历(输出)二叉线索树:\n");
InOrderTraverse_Thr(H); /* 中序遍历(输出)二叉线索树 */
printf("\n");
return 0;
}
课程代码.c
/* 树的双亲表示法结点结构定义 */
#define MAX_TREE_SIZE 100
typedef int TElemType; /* 树结点的数据类型，目前暂定为整型 */
typedef struct PTNode /* 结点结构 */
{
TElemType data; /* 结点数据 */
int parent; /* 双亲位置 */
} PTNode;
typedef struct /* 树结构 */
{
PTNode nodes[MAX_TREE_SIZE]; /* 结点数组 */
int r,n; /* 根的位置和结点数 */
} PTree;
/* 树的孩子表示法结构定义 */
#define MAX_TREE_SIZE 100
typedef int TElemType; /* 树结点的数据类型，目前暂定为整型 */
typedef struct CTNode /* 孩子结点 */
{
int child;
struct CTNode *next;
} *ChildPtr;
typedef struct /* 表头结构 */
{
TElemType data;
ChildPtr firstchild;
} CTBox;
typedef struct /* 树结构 */
{
CTBox nodes[MAX_TREE_SIZE]; /* 结点数组 */
int r,n; /* 根的位置和结点数 */
} CTree;
/* 树的孩子兄弟表示法结构定义 */
typedef struct CSNode
{
TElemType data;
struct CSNode *firstchild,*rightsib;
} CSNode,*CSTree;
/* 二叉树的二叉链表结点结构定义 */
typedef struct BiTNode /* 结点结构 */
{
TElemType data; /* 结点数据 */
struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;
/* 二叉树的前序遍历递归算法 */
/* 初始条件: 二叉树T存在 */
/* 操作结果: 前序递归遍历T */
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf("%c",T->data); /* 显示结点数据，可以更改为其它对结点操作 */
PreOrderTraverse(T->lchild);/* 再先序遍历左子树 */
PreOrderTraverse(T->rchild);/* 最后先序遍历右子树 */
}
/* 二叉树的中序遍历递归算法 */
/* 初始条件: 二叉树T存在 */
/* 操作结果: 中序递归遍历T */
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return;
InOrderTraverse(T->lchild); /* 中序遍历左子树 */
printf("%c",T->data); /* 显示结点数据，可以更改为其它对结点操作 */
InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}
/* 二叉树的后序遍历递归算法 */
/* 初始条件: 二叉树T存在 */
/* 操作结果: 后序递归遍历T */
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild); /* 先后序遍历左子树 */
PostOrderTraverse(T->rchild); /* 再后序遍历右子树 */
printf("%c",T->data); /* 显示结点数据，可以更改为其它对结点操作 */
}
/* 按前序输入二叉树中结点的值（一个字符） */
/* #表示空树，构造二叉链表表示二叉树T。 */
void CreateBiTree(BiTree *T)
{
TElemType ch;
scanf("%c",&ch);
ch=str[index++];
if(ch=='#')
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
if(!*T)
exit(OVERFLOW);
(*T)->data=ch; /* 生成根结点 */
CreateBiTree(&(*T)->lchild); /* 构造左子树 */
CreateBiTree(&(*T)->rchild); /* 构造右子树 */
}
}
/* 二叉树的二叉线索存储结构定义 */
typedef char TElemType;
typedef enum {Link,Thread} PointerTag; /* Link=0表示指向左右孩子指针, */
/* Thread=1表示指向前驱或后继的线索 */
typedef struct BiThrNode /* 二叉线索存储结点结构 */
{
TElemType data; /* 结点数据 */
struct BiThrNode *lchild, *rchild; /* 左右孩子指针 */
PointerTag LTag;
PointerTag RTag; /* 左右标志 */
} BiThrNode, *BiThrTree;
BiThrTree pre; /* 全局变量,始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p)
{
if(p)
{
InThreading(p->lchild); /* 递归左子树线索化 */
if(!p->lchild) /* 没有左孩子 */
{
p->LTag=Thread; /* 前驱线索 */
p->lchild=pre; /* 左孩子指针指向前驱 */
}
if(!pre->rchild) /* 前驱没有右孩子 */
{
pre->RTag=Thread; /* 后继线索 */
pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */
}
pre=p; /* 保持pre指向p的前驱 */
InThreading(p->rchild); /* 递归右子树线索化 */
}
}
/* T指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的*/
/* 最后一个结点。中序遍历二叉线索链表表示的二叉树T */
Status InOrderTraverse_Thr(BiThrTree T)
{
BiThrTree p;
p=T->lchild; /* p指向根结点 */
while(p!=T) /* 空树或遍历结束时,p==T */
{
while(p->LTag==Link) /*当LTag==0时循环到中序序列第一个结点 */
p=p->lchild;
printf（"%c",p->data）; /* 显示结点数据，可以更改为其他对结点操作 */
while(p->RTag==Thread && p->rchild!=T)
{
p=p->rchild;
printf（"%c",p->data）; /* 访问后继结点 */
}
p=p->rchild; /* p进至其右子树根 */
}
return OK;
}
if （a<60）
b=＂不及格＂;
else if （a<70）
b=＂及格＂;
else if （a<80）
b=＂中等＂;
else if （a<90）
b=＂良好＂;
else
b=＂优秀＂;
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022-11-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录