#include<stdio.h>
#include<stdlib.h>
//二叉树的节点定义
typedef struct TreeNode
{
char ch; //数据域
struct TreeNode *lchild; //左孩子
struct TreeNode *rchild; //右孩子
}BTNode,*PBTNode;
//先序构造二叉树
void createBTree(PBTNode *root)
{
char ch;
ch=getchar();
if(ch=='#')
*root=NULL;
else{
*root=(PBTNode)malloc(sizeof(BTNode));
(*root)->ch=ch;
(*root)->lchild=NULL;
(*root)->rchild=NULL;
createBTree(&(*root)->lchild);
createBTree(&(*root)->rchild);
}
}
//先序遍历二叉树
void preOrder(PBTNode root)
{
if(root==NULL)
return;
printf("%-3c",root->ch);
preOrder(root->lchild);
preOrder(root->rchild);
}
//中序遍历二叉树
void inOrder(PBTNode root)
{
if(root==NULL)
return;
preOrder(root->lchild);
printf("%-3c",root->ch);
preOrder(root->rchild);
}
//后序遍历二叉树
void postOrder(PBTNode root)
{
if(root==NULL)
return;
preOrder(root->lchild);
preOrder(root->rchild);
printf("%-3c",root->ch);
}
//输出叶子结点
void displyLeaf(PBTNode root)
{
if(root==NULL)
return;
if(root->lchild==NULL&&root->rchild==NULL)
printf("%-3c",root->ch);
else{
displyLeaf(root->lchild);
displyLeaf(root->rchild);
}
}
//左结点插入
void inseartLeftNode(PBTNode root,char ch)
{
PBTNode p,newNode;
if(root==NULL)
return;
p=root->lchild;
newNode=(PBTNode)malloc(sizeof(BTNode));
newNode->ch=ch;
newNode->rchild=NULL;
newNode->lchild=p;
root->lchild=newNode;
}
//右结点插入
void inseartRightNode(PBTNode root,char ch)
{
PBTNode p,newNode;
if(root==NULL)
return;
p=root->rchild;
newNode=(PBTNode)malloc(sizeof(BTNode));
newNode->ch=ch;
newNode->lchild=NULL;
newNode->rchild=p;
root->rchild=newNode;
}
//销毁一颗二叉树
void clear(PBTNode* root)
{
PBTNode pl,pr;
if(*root==NULL)
return;
pl=(*root)->lchild;
pr=(*root)->rchild;
(*root)->lchild=NULL;
(*root)->rchild=NULL;
free((*root));
*root=NULL;
clear(&pl);
clear(&pr);
}
//删除左子树
void deleteLeftTree(PBTNode root)
{
if(root==NULL)
return;
clear(&root->lchild);
root->lchild=NULL;
}
//删除右子树
void deleteRightTree(PBTNode root)
{
if(root==NULL)
return;
clear(&root->rchild);
root->rchild=NULL;
}
//查找结点
PBTNode search(PBTNode root,char ch)
{
PBTNode p;
if(root==NULL)
return NULL;
if(root->ch==ch)
return root;
else{
if((p=search(root->lchild,ch))!=NULL)
return p;
else
return search(root->rchild,ch);
}
}
//求二叉树的高度
int BTreeHeight(PBTNode root)
{
int lchildHeight,rchildHeight;
if(root==NULL)
return 0;
lchildHeight=BTreeHeight(root->lchild);
rchildHeight=BTreeHeight(root->rchild);
return (lchildHeight>rchildHeight)?(1+lchildHeight):(1+rchildHeight);
}
//求叶子结点的个数
int countLeaf(PBTNode root)
{
if(root==NULL)
return 0;
if(root->lchild==NULL&&root->rchild==NULL)
return 1;
else{
return countLeaf(root->lchild)+countLeaf(root->rchild);
}
}
//求所有结点的个数
int countAll(PBTNode root)
{
if(root==NULL)
return 0;
return countAll(root->lchild)+countAll(root->rchild)+1;
}
//复制二叉树
PBTNode copyBTree(PBTNode root)
{
PBTNode p,lchild,rchild;
if(root==NULL)
return NULL;
lchild=copyBTree(root->lchild);
rchild=copyBTree(root->rchild);
p=(PBTNode)malloc(sizeof(BTNode));
p->ch=root->ch;
p->lchild=lchild;
p->rchild=rchild;
return p;
}
分享到:
相关推荐
二叉树 二叉树_基于C语言实现的二叉树基本操作
用C语言实现关于二叉树的初始化、插入、删除、路径、等数据结构的操作
通过阅读本文,读者将能够全面理解二叉树的基本概念和原理,并掌握其在实际问题中的应用。 二叉树是一种特殊的树形结构,它满足以下特性: 每个节点最多有两个子节点。 子节点之间没有顺序关系,即左子节点和右子...
本代码用c语言实现了平衡二叉树这一数据结构,同时实现了基本查找,插入,删除操作,都是自己精心设计的算法,花了很多功夫。。
二叉树的基本操作实现 基于C语言实现二叉树的基本操作
实现了二叉树的前向生成以及前向遍历。属于二叉树的基本操作。
本代码是描述如何构建一个二叉树,如何对二叉树进行一些基本的操作,如插入,删除,输出
。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
运用二叉链表实现二叉树的基本操作,包括:创建二叉树的存储结构、复制已有的二叉树、计算已有的二叉树的深度、先根序序列、中根序序列、后根序序列等。 输入格式:AB#C##D## 二、实验目的 掌握二叉链表及二叉树的...
以二叉链表作存储结构,编写程序,实现如下的功能: 1、根据输入的数据建立一个二叉树; 2、分别采用前序、中序、后序的遍历方式显示输出二叉树的遍历结果 3、采用非递归的编程方法,分别统计二叉树的节点个数、度为...
1. 熟悉二叉树结点的结构和对二叉树的基本操作。 2. 掌握对二叉树每一种操作的具体实现。...4. 在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法。 5. 掌握构造哈夫曼树以及哈夫曼编码的方法
二叉树 C语言实现二叉树的基本操作源码.zip
C语言实现二叉树的基本操作
二叉树的基本操作实现
本文总结了二叉树的常见操作:二叉树的构建,查找,删除,二叉树的遍历(包括前序遍历、中序遍历、后序遍历、层次遍历),二叉搜索树的构造等。 1. 二叉树的构建 二叉树的基本构建方式为:添加一个节点,如果这是一棵...
严蔚敏数据结构中关于二叉树的操作,C语言实现
要求选用顺序存储结构和二叉链表存储结构实现抽象数据类型二叉树的基本操作。有个亮点是利用字符在dos界面显示二叉树的结构形态。 里面包含了完整的源程序和实验报告文档。 实验报告包含了完整的步骤包括: 一.抽象...
cout二叉树链表存储功能演示 "; cout; cout第一种输入法:默认广义表 "; cout第二种输入法:键盘输入广义表 "; cout第三种输入法:新建树根(逐个输入)"; cout增加儿子数据 "; cout删除叶子结点或仅仅根 "; ...