二叉树的创建和操作

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100

typedef struct node{
 char data; /*此例中二叉树的结点采用字符类型*/
 struct node *lchild,*rchild;
}NODE;
/*按先序遍历序列创建二叉树的二叉链表*/
NODE *crt_bt_pre(){  
 NODE *bt;
 char ch;
 flushall();
 scanf("%c",&ch);
 if(ch == '0')
  bt = NULL;
 else{
  bt = new NODE;
  bt -> data = ch;
  printf("\n\t请输入%c结点的左孩子：",bt -> data);
  bt -> lchild = crt_bt_pre();
  printf("\n\t请输入%c结点的右孩子:",bt -> data);
  bt -> rchild = crt_bt_pre();
 }
 return bt;
}
/*先序遍历二叉树*/
void Preorder(NODE *bt){
 if (bt != NULL){
  printf("%c",bt -> data);
  Preorder(bt -> lchild);
  Preorder(bt -> rchild);
 }
}
/*中序遍历二叉树*/
void Inorder(NODE *bt){
 if (bt != NULL){
  Inorder(bt -> lchild);
  printf("%c",bt -> data);
  Inorder(bt -> rchild);
 }
}
//后序遍历二叉树
void Postorder(NODE *bt){
 if (bt != NULL){
  Postorder(bt -> lchild);
  Postorder(bt -> rchild);
  printf("%c",bt -> data);
 }
}
/*统计二叉树中叶子结点的个数*/
int CountLeaf(NODE *bt){
 static int count;
 if(bt == NULL)
  return 0;
 else{
  if(bt -> lchild == NULL && bt -> rchild == NULL)
   count++;
  else{
   CountLeaf(bt -> lchild);
   CountLeaf(bt -> rchild);
  }
  return(count);
 }
}
/*统计二叉树中根结点的总数*/
int CountNode(NODE *bt){
 static int count;
 if(bt == NULL)
  return 0;
 else{
  count++;
  CountNode(bt -> lchild);
  CountNode(bt -> rchild);
  return(count);
 }
}
/*求二叉树的深度*/
int TreeDepth(NODE *bt){
 int ldep,rdep;
 if(bt == NULL)
  return 0;
 else{
  ldep = TreeDepth(bt -> lchild);
  rdep = TreeDepth(bt -> rchild);
  if(ldep > rdep)
   return(ldep+1);
  else
   return(rdep+1);     //有错误
 }
}
//求二叉树的宽度
int TreeWidth(NODE *b)
{
 struct 
 {
  int lno;
  NODE*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; //根节点的层次编号为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;  //lnum从第一层开始
  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 system(const char *string); //自动清屏代码
//char Check()
//{
// printf("是否清屏：Y|N");
// char a;
// scanf("%c",&a);
// if (a=='y'||a=='Y')
// {
//  return a;
// }
// else
//  return 'N';
//}
//void clear()
//{
// printf("是否清屏（Y|N）:");
// char a;
// scanf("%c",&a);
// if (a=='y'||a=='Y')
// {
//  system("pause");
//  system("cls");
// }
//}
//菜单函数
void shoumenu(){
 printf("\n\n\n");
 printf("  --二叉树的基本运算--\n");
 printf("*****************************************\n");
 printf("*  1------建二叉树         *\n");
 printf("*  2------先序遍历         *\n");
 printf("*  3------中序遍历         *\n");
 printf("*  4------后序遍历         *\n");
 printf("*  5------统计叶子数       *\n");
 printf("*  6------统计结点数       *\n");
 printf("*  7------求二叉树深度     *\n");
 printf("*  8------求二叉树宽度     *\n");
 printf("*                                       *\n");
 printf("*  0------退出             *\n");
 printf("*****************************************\n");
 printf("请选择菜单号(0--8):");
}
//选择功能函数
void binaryOP(){
 NODE *bt = NULL;
 int count = 0;
 char choice = 'N';
 int x;
 while(choice != '0'){
  
  shoumenu();
  flushall();
  scanf("%c",&choice);
  switch(choice){
  case '1':
   printf("\n\t请输入按先序建立二叉树的结点序列：");
   printf("\n\t 说明：逐个输入，'0'代表后继结点为空，按回车输入下一个结点");
   printf("\n\t请输入根结点：");
   bt = crt_bt_pre();/*调用创建二叉树的函数*/
   printf("\n\t二叉树成功建立！\n");
   //clear();
   break;

  case '2':
   if (bt == NULL){
    printf("\n\t空树");
   }
   else{
    printf("\n\t该二叉树的先序遍历的序列为：");
    Preorder(bt);/*调用先序遍历函数*/
   }
   printf("\n");
   //clear();
   break;

  case '3':
   if (bt == NULL){
    printf("\n\t空树");
   }
   else{
    printf("\n\t该二叉树的中序遍历序列：");
    Inorder(bt);/*调用中序遍历函数*/
   }
   printf("\n");
   //clear();
   break;

  case '4':
   if (bt == NULL){
    printf("\n\t空树");
   }
   else{
    printf("\n\t该二叉树的后序遍历序列为：");
    Postorder(bt);/*调用后序遍历函数*/
   }
   printf("\n");
   //clear();
   break;

  case '5':
   count = CountLeaf(bt);/*调用统计叶子结点个数的函数*/
   printf("\n\t该二叉树有%d个叶子结点。\n",count);
   printf("\n");
   //clear();
   break;

  case '6':
   count = CountNode(bt);/*调用统计结点总数的函数*/
   printf("\n\t该二叉树共有%d个结点 \n",count);
   printf("\n");
   //clear();
   break;

  case '7':
   x = TreeDepth(bt);/*调用求二叉树深度的函数*/
   printf("\n\t 该二叉树的深度为%d",x);
   printf("\n");
   //clear();
   break;
  case'8':
   int n;
   n=TreeWidth(bt);
   printf("\n\t 该二叉树的宽度为%d\n",n);
   //clear();
   break;

  case '0':
   printf("\n\t 程序结束!\n");
   printf("\n");
   //clear();
   break;

  default :
   printf("\n\t输入有误，请重新输入!\n");
   printf("\n");
   //clear();
  }
 }
}

void main()
{
 binaryOP();
}

时间： 2024-10-03 01:47:28

二叉树的创建和操作的相关文章

Java实现二叉树的创建和遍历操作（有更新）

博主强烈建议跳过分割线前面的部分,直接看下文更新的那些即可. 最近在学习二叉树的相关知识,一开始真的是毫无头绪.本来学的是C++二叉树,但苦于编译器老是出故障,于是就转用Java来实现二叉树的操作.但是二者原理是一致的,而且实现的方式也是大同小异! 下面就让我们来看看代码吧. 1.首先我们需要创建一个二叉树的节点类,便于我们对树的操作,当然了,你也可以在二叉树类的内部将节点类声明为内部类,但是这样会降低操作的灵活性.我才用的是单独创建一个BinaryTreeNode类,代码如下: package

关于二叉树的创建与遍历 请问哪里有问题我的代码

问题描述 关于二叉树的创建与遍历 请问哪里有问题我的代码 先输入一个字符串 然后求先中后序遍历http://paste.ubuntu.org.cn/4213378 #include #include char w[100]; struct node { char data; struct node *l; struct node *r; }; void creat(struct node *&T,char *w) { char ch;int p; ch=*w; if(ch=='') p=1; i

中序遍历二叉树-二叉树的非递归操作。。

问题描述 二叉树的非递归操作.. 如何用栈实现二叉树的非递归操作,越详细越好,谢谢各位啦.一定要详细哦 解决方案 void inOrder2(BinTree *root) //非递归中序遍历 { stack<BinTree*> s; BinTree *p=root; while(p!=NULL||!s.empty()) { while(p!=NULL) { s.push(p); p=p->lchild; } if(!s.empty()) { p=s.top(); cout<<

求助！一个二叉树程序创建和遍历的程序

问题描述 求助!一个二叉树程序创建和遍历的程序 #include #include typedef char ElementType; typedef struct BiNode{ ElementType data; struct BiNode * lchild; struct BiNode * rchild; }BiNode; void CreatBiTree2(BiNode * T); void PreTraverBiTree(BiNode const * T); int main() {

二叉树的创建、前序遍历、中序遍历、后序遍历

// BTree.cpp : Defines the entry point for the console application. /* 作者:成晓旭 时间:2001年7月2日(9:00:00-14:00:00) 内容:完成二叉树的创建.前序遍历.中序遍历.后序遍历 时间:2001年7月2日(14:00:00-16:00:00) 内容:完成二叉树的叶子节点访问,交换左.右孩子 */ #include "stdafx.h" #include "stdlib.h"

[Qt教程] 第28篇 XML（二）使用DOM创建和操作XML文档

[Qt教程] 第28篇 XML(二)使用DOM创建和操作XML文档 楼主  发表于 2013-5-21 22:00:51 | 查看: 475| 回复: 0 使用DOM创建和操作XML文档 版权声明 该文章原创于作者yafeilinux,转载请注明出处! 导语 在上一节中我们用手写的方法建立了一个XML文档,并且用DOM的方法对其进行了读取.现在我们使用代码来创建那个XML文档,并且对它实现查找.更新.插入等操作. 环境:Windows Xp + Qt 4.8.4+QtCreator 2.6.2

数据结构算法-关于二叉树的创建问题

问题描述 关于二叉树的创建问题 我想在主函数中先创建一个二叉树,然后再遍历.但我的程序调用CreateBiTree输入完要输入的数之后,还是一直在等待输入,无法停止.以致无法执行到后面的遍历二叉树函数.望高手给解答下! #include #include #include struct?BiTree { int?data; struct?BiTree?*lchild; struct?BiTree?*rchild; }; int?CreateBiTree(BiTree?*t) {??? ?????

二叉树的创建与遍历（递归版本）

非递归方式实现二叉树的创建与搜索,对于二叉树通常约定以前序遍历方式输入,若输入不正确是不会有什么显示的,这点要注意: 给出了C语言创建链表的俩种方式(不同于C++中引用传递) 一 创建二叉树方式: 方式一:输入指针 [cpp] view plain copy   void creatBT(BiTree *T)//建立一个二叉树   {       char ch;       scanf("%c",&ch);//读入字符       if(ch=='.')//.代表空子树  

c语言-有关C语言中基于全局变量对二叉树的创建和遍历的问题

问题描述 有关C语言中基于全局变量对二叉树的创建和遍历的问题 #include#include#define max 100typedef struct node{ char date; struct node lchild*rchild;}tree*TREE;tree *DLR=NULL;void creatDLR() { //先序递归方式创建树 char date; date=getchar(); if(date=='#')DLR=NULL; else { if(!(DLR=(tree)ma