1、二叉树的基本运算
#define MaxSize 100
typedef char ElemType;
typedef struct node{
ElemType data;
struct node *lchild;
struct node *rchild;
}BTNode;
void CreateBTNode(BTNode *&b,char *str){
BTNode *St[MaxSize],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while(ch!='\0'){
switch (ch) {
case '(':top++,St[top]=p;k=1;break;
case ')':top--;break;
case ',': k=2;break;
default:p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;p->lchild=p->rchild=NULL;
if(b==NULL){
b=p;
}else{
switch (k) {
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}
BTNode *FindNode(BTNode *b,ElemType x){
BTNode *p;
if(b==NULL){
return NULL;
}
else if(b->data==x){
return b;
}else{
p=FindNode(b->lchild, x);
if(p!=NULL){
return p;
}else{
return FindNode(b->rchild, x);
}
}
}
BTNode *LchildNode(BTNode *p){
return p->lchild;
}
BTNode *RchildNode(BTNode *p){
return p->rchild;
}
int BTNodeDepth(BTNode *b){
int lchilddep,rchilddep;
if(b==NULL){
return 0;
}else{
lchilddep=BTNodeDepth(b->lchild);
rchilddep=BTNodeDepth(b->rchild);
return lchilddep>rchilddep?lchilddep+1:rchilddep+1;
}
}
void DispBTNode(BTNode *b){
if(b!=NULL){
printf("%c ",b->data);
if(b->lchild!=NULL||b->rchild!=NULL){
printf("(");
DispBTNode(b->lchild);
if(b->rchild!=NULL){
printf(",");
DispBTNode(b->rchild);
}
printf(")");
}
}
}
int BTWidth(BTNode *b){
struct{
int lno;
BTNode *p;
}Qu[MaxSize];
int front,rear;
int lnum,max,i,n;
front=rear=0;
if(b!=NULL){
rear++;
Qu[rear].p=b;
Qu[rear].lno=1;
while(rear!=front){
front++;
b=Qu[front].p;
lnum=Qu[front].lno;
if(b->lchild!=NULL){
rear++;
Qu[rear].p=b->lchild;
Qu[rear].lno=lnum+1;
}
if(b->rchild!=NULL){
rear++;
Qu[rear].p=b->rchild;
Qu[rear].lno=lnum+1;
}
}
max=0;lnum=1;i=1;
while(i<=rear){
n=0;
while(i<=rear&&Qu[i].lno==lnum){
n++;
i++;
}
lnum=Qu[i].lno;
if(n>max){
max=n;
}
}
return max;
}else{
return 0;
}
}
int Nodes(BTNode *b){
if(b==NULL){
return 0;
}else if(b->lchild==NULL&&b->rchild==NULL){
return 1;
}else{
return Nodes(b->lchild)+Nodes(b->rchild)+1;
}
}
int LeafNodes(BTNode *b){
if(b==NULL){
return 0;
}else if(b->lchild==NULL&&b->rchild==NULL){
return 1;
}else{
return LeafNodes(b->lchild)+LeafNodes(b->rchild);
}
}
2、二叉树的遍历
2.1递归遍历
void PreOrder(BTNode *b)
{
if(b!=NULL){
printf("%c",b->data);
PreOrder(b->lchild);
PreOrder(b->rchild);
}
}
void InOrder(BTNode *b){
if(b!=NULL){
InOrder(b->lchild);
printf("%c",b->data);
InOrder(b->rchild);
}
}
void PostOrder(BTNode *b){
if(b!=NULL){
PostOrder(b->lchild);
PostOrder(b->rchild);
printf("%c",b->data);
}
}
2.2非递归遍历
void ProOrder1(BTNode *b)
{
BTNode *p;
struct {
BTNode *pt;
int tag;
}St[MaxSize];
int top=-1;
top++;
St[top].pt=b;
St[top].tag=1;
while(top>-1){
if(St[top].tag==1){
p=St[top].pt;
top--;
if(p!=NULL){
top++;
St[top].pt=p->rchild;
St[top].tag=1;
top++;
St[top].pt=p->lchild;
St[top].tag=1;
top++;
St[top].pt=p;
St[top].tag=0;
}
}
if(St[top].tag==0){
printf("%c",St[top].pt->data);
top--;
}
}
}
void InOrder1(BTNode *b){
BTNode *p;
struct {
BTNode *pt;
int tag;
}St[MaxSize];
int top=-1;
top++;
St[top].pt=b;
St[top].tag=1;
while(top>-1){
if(St[top].tag==1){
p=St[top].pt;
top--;
if(p!=NULL){
top++;
St[top].pt=p->rchild;
St[top].tag=1;
top++;
St[top].pt=p;
St[top].tag=0;
top++;
St[top].pt=p->lchild;
St[top].tag=1;
}
}
if(St[top].tag==0){
printf("%c",St[top].pt->data);
top--;
}
}
}
void PostOrder1(BTNode *b){
BTNode *p;
struct {
BTNode *pt;
int tag;
}St[MaxSize];
int top=-1;
top++;
St[top].pt=b;
St[top].tag=1;
while(top>-1){
if(St[top].tag==1){
p=St[top].pt;
top--;
if(p!=NULL){
top++;
St[top].pt=p;
St[top].tag=0;
top++;
St[top].pt=p->rchild;
St[top].tag=1;
top++;
St[top].pt=p->lchild;
St[top].tag=1;
}
}
if(St[top].tag==0){
printf("%c",St[top].pt->data);
top--;
}
}
}
3、从叶子节点到根结点的路径
void AllPath(BTNode *b)
{
struct snode {
BTNode *node;
int parent;
}Qu[MaxSize];
int front,rear,p;
front=rear=-1;
rear++;
Qu[rear].node=b;
Qu[rear].parent=-1;
while(front<rear){
front++;
b=Qu[front].node;
if(b->lchild==NULL&&b->rchild==NULL){
printf("%c到根结点的路径： ",b->data);
p=front;
while(Qu[p].parent!=-1){
printf(" %c",Qu[p].node->data);
p=Qu[p].parent;
}
printf(" %c\n",Qu[p].node->data);
}
if(b->lchild!=NULL){
rear++;
Qu[rear].node=b->lchild;
Qu[rear].parent=front;
}
if(b->rchild!=NULL){
rear++;
Qu[rear].node=b->rchild;
Qu[rear].parent=front;
}
}
}
void AllPath1(BTNode *b,ElemType path[],int pathlen){
int i;
if(b!=NULL){
if(b->lchild==NULL&&b->rchild==NULL){
printf(" %c到根接的路径： %c",b->data,b->data);
for(i=pathlen-1;i>=0;i--){
printf(" %c",path[i]);
}
printf("\n");
}else{
path[pathlen]=b->data;
pathlen++;
AllPath1(b->lchild, path, pathlen);
AllPath1(b->rchild, path, pathlen);
pathlen--;
}
}
}
void LongPath(BTNode *b,ElemType path[],int pathlen,ElemType longpath[],int &longpathlen){
int i;
if(b==NULL){
if(pathlen>longpathlen){
for (i=pathlen-1; i>=0; i--) {
longpath[i]=path[i];
}
longpathlen=pathlen;
}
}else{
path[pathlen]=b->data;
pathlen++;
LongPath(b->lchild, path, pathlen, longpath, longpathlen);
LongPath(b->rchild, path, pathlen, longpath, longpathlen);
pathlen--;
}
}
void DispLeaf(BTNode *b){
if(b!=NULL){
if(b->lchild==NULL&&b->rchild==NULL){
printf("%c ",b->data);
}else{
DispLeaf(b->lchild);
DispLeaf(b->rchild);
}
}
}
分享到：
相关推荐
C语言数据结构实现二叉树的建立与遍历.cpp
这个压缩包文件"数据结构——二叉树的实现.zip"显然包含了关于二叉树实现的详细内容，特别是二叉链表和左子右兄弟两种不同的实现方法。 首先，我们来探讨二叉链表的实现。二叉链表是最基础的二叉树存储方式，每个...
在计算机科学领域，数据结构是组织和存储数据的方式，它对于高效算法的设计至关重要。...在进行数据结构课程设计时，这种实现方式能帮助学生深入理解二叉树和广义表的内在联系，提高问题解决能力。
### 数据结构之二叉树实现知识点详解 #### 一、二叉树基本概念与特性 - **定义**：二叉树是一种特殊的树形结构，其中每个节点最多有两个子节点，通常被称为左子节点和右子节点。 - **类型**：二叉树包括满二叉树、...
本实验的主题是“二叉树”，这是数据结构中一个基础且重要的概念。二叉树是一种非线性的数据结构，由节点（或称为顶点）组成，每个节点最多有两个子节点，通常称为左子节点和右子节点。这个实验旨在帮助学生深入理解...
"数据结构--二叉树--思维导图" 二叉树是一种常见的数据结构，它是一种树形结构，每个节点最多有两个孩子节点，分别是左子树和右子树。二叉树可以用来存储大量数据，并且可以快速地查找、插入和删除数据。 二叉树的...
本主题聚焦于“数据结构算法二叉树实现”，这是一个关于如何在编程中实际操作和管理二叉树的实践性课题。二叉树是一种特殊的数据结构，它由节点构成，每个节点最多有两个子节点，通常分为左子节点和右子节点。 ...
本文将深入探讨“C语言数据结构实现二叉树的各种操作”，包括前序遍历、先序遍历、后序遍历以及查找等关键操作。 首先，我们来理解二叉树的基本概念。二叉树是由节点（或称为顶点）组成的有限集合，每个节点最多有...
在IT领域，数据结构是计算机科学中的核心概念之一，它涉及到如何有效地组织和存储数据，以便于算法的高效执行。二叉树作为一种重要的数据结构，是数据结构实验中常见的研究对象。在这里，我们将深入探讨二叉树的概念...
在IT领域，数据结构是计算机...总之，学习二叉树的C++实现不仅是掌握数据结构知识的一部分，也是提升编程能力的重要步骤。通过深入研究提供的源码，可以进一步理解二叉树的原理和操作，从而在实际问题解决中游刃有余。
在IT领域，数据结构是计算机科学的基础，而二叉树作为一种重要的数据结构，被广泛应用于算法设计、数据库系统、编译器等领域。本教程将详细阐述如何使用JAVA语言实现二叉树的相关操作。 首先，我们要了解二叉树的...
用二叉树实现简单的姓氏图谱管理系统本课程设计主要解决在一个家族中，对姓氏图谱进行管理的问题，通过建立一个相容，一致，易查和全面的姓氏图谱管理系统，实现对家族姓氏的插入，删除，显示和查询。在本课程设计中...
一、问题描述 运用二叉链表实现二叉树的基本操作，包括：创建二叉树的存储结构、复制...1、构造二叉树的二叉链表数据结构。 2、实现二叉树的创建、复制、计算二叉树的深度、先根序序列、中根序序列、后根序序列等操作。
二叉树作为数据结构的一种，具有重要的理论和实际应用价值。本程序旨在通过实现二叉树的创建、遍历、查找以及删除等基本操作，帮助学生深入理解和掌握二叉树的相关知识。 首先，我们要理解什么是二叉树。二叉树是一...
在C++中实现二叉树可以帮助我们更好地理解和应用这些数据结构，从而解决各种计算问题。本项目提供了一套完整的二叉树算法实现，对于学习数据结构和C++编程的朋友们非常有价值。 首先，我们来讨论二叉树的基本操作：...
本次实验的主题是“数据结构实验”，重点关注二叉树这一特殊的数据结构，并结合MFC（Microsoft Foundation Classes）框架进行实现。二叉树是一种非线性的数据结构，每个节点最多有两个子节点，通常分为左子节点和右...
数据结构 课设 二叉树 C++ // 获取二叉树的高度 int TreeHeight(Node *root) { if (root == NULL) return 0; else return 1 + max(TreeHeight(root->lchild), TreeHeight(root->rchild)); } //建立二叉树……...
该文件包括二叉树的头文件（BitTree开头）和堆栈的头文件（Seq开头），另外还实现了编写按层次顺序（同一层自左至右）遍历二叉树的算法、后序递归遍历计算二叉树的深度的算法、判断给定二叉树是否为完全二叉树（通过...
数据结构二叉树家谱：文件操作功能，家谱操作功能
数据结构二叉树实验报告 本实验报告的主要内容是设计和实现一个二叉树的抽象数据类型（ADT），包括二叉树的建立、遍历、叶子结点、显示和销毁等操作。本报告将从需求分析、概要设计、详细设计、测试数据几个方面来...