none
下面这段双叉树的程序要怎么改才满足我的要求?? RRS feed

  • 问题

  • 下面是我在网上找到的一段代码(基本没错,输入的时候请输一个数字就按一次回车)
    当我输入一下这个双叉树的时候并没有错误
                 1
          2              0
        0   3          0    0      ( 其中 0表示空)

    但是我要输入下面这个双叉树的时候,就有错了
                                 1
                    2                     0
                0      3              0         0
              0    0 5    6         0    0    0    0
    为什么呢??
    ///////////////////////////////////////////////////////////////////////////////
     #include<malloc.h> // malloc()等
     #include<stdio.h> // 标准输入输出头文件,包括EOF(=^Z或F6),NULL等
     #include<stdlib.h> // atoi(),exit()
     #include<math.h> // 数学函数头文件,包括floor(),ceil(),abs()等


    #define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样

    typedef struct BiTNode
     {  
     int data; // 结点的值
      BiTNode *lchild,*rchild; // 左右孩子指针
     }BiTNode,*BiTree;

    int Nil=0; // 设整型以0为空
    void visit(int e)
     { printf("%d ",e); // 以整型格式输出
     }
     void InitBiTree(BiTree &T)
     { // 操作结果:构造空二叉树T
      T=NULL;
     }

     void CreateBiTree(BiTree &T)
     { // 算法6.4:按先序次序输入二叉树中结点的值(可为字符型或整型,在主程中定义),
      // 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
      int number;
      scanf("%d",&number); // 输入结点的值
      if(number==Nil) // 结点的值为空
      T=NULL;
      else // 结点的值不为空
      { T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
      if(!T)
      exit(OVERFLOW);
      T->data=number; // 将值赋给T所指结点
      CreateBiTree(T->lchild); // 递归构造左子树
      CreateBiTree(T->rchild); // 递归构造右子树
      }
     }

     void DestroyBiTree(BiTree &T)
     { // 初始条件:二叉树T存在。操作结果:销毁二叉树T
      if(T) // 非空树
      { DestroyBiTree(T->lchild); // 递归销毁左子树,如无左子树,则不执行任何操作
      DestroyBiTree(T->rchild); // 递归销毁右子树,如无右子树,则不执行任何操作
      free(T); // 释放根结点
      T=NULL; // 空指针赋0
      }
     }

     void PreOrderTraverse(BiTree T,void(*Visit)(int))
     { // 初始条件:二叉树T存在,Visit是对结点操作的应用函数。修改算法6.1
      // 操作结果:先序递归遍历T,对每个结点调用函数Visit一次且仅一次
      if(T) // T不空
      { Visit(T->data); // 先访问根结点
      PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
      PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
      }
     }

     void InOrderTraverse(BiTree T,void(*Visit)(int))
     { // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
      // 操作结果:中序递归遍历T,对每个结点调用函数Visit一次且仅一次
      if(T)
      { InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
      Visit(T->data); // 再访问根结点
      InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
      }
     }

      void PostOrderTraverse(BiTree T,void(*Visit)(int))
     { // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
      // 操作结果:后序递归遍历T,对每个结点调用函数Visit一次且仅一次
      if(T) // T不空
      { PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
      PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
      Visit(T->data); // 最后访问根结点
      }
     }

     void main()
     {
      BiTree T;
      InitBiTree(T); // 初始化二叉树T
      printf("按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0\n");
      CreateBiTree(T); // 建立二叉树T
      printf("先序递归遍历二叉树:\n");
      PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
      printf("\n中序递归遍历二叉树:\n");
      InOrderTraverse(T,visit); // 中序递归遍历二叉树T
      printf("\n后序递归遍历二叉树:\n");
      PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
     }
    2011年10月18日 14:36

答案

  • ///////////////////////////////////////////////////////////////////////////////
    #include<malloc.h> // malloc()等
    #include<stdio.h> // 标准输入输出头文件,包括EOF(=^Z或F6),NULL等
    #include<stdlib.h> // atoi(),exit()
    #include<math.h> // 数学函数头文件,包括floor(),ceil(),abs()等
    
    
    #define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
    
    typedef struct BiTNode
    {  
    	int data; // 结点的值
    	BiTNode *lchild,*rchild; // 左右孩子指针
    }BiTNode,*BiTree;
    
    int Nil=0; // 设整型以0为空
    
    void visit(int e)
    { printf("%d ",e); // 以整型格式输出
    }
    
    void InitBiTree(BiTree &T)
    { // 操作结果:构造空二叉树T
    	T=NULL;
    // 	T->lchild = NULL;
    // 	T->rchild = NULL;
    }
    
    void CreateBiTree(BiTree &T)
    { 
    	// 算法6.4:按先序次序输入二叉树中结点的值(可为字符型或整型,在主程中定义),
    	// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
    	int number;
    	scanf("%d",&number); // 输入结点的值
    
    	if(number==-1) // 结点的值为空
    	{
    		T = NULL;
    		return;
    	}
    	else // 结点的值不为空
    	{
    		T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
    		if(!T)
    		{
    			printf("loss\n");
    			exit(OVERFLOW);
    		}
    			T->data=number; // 将值赋给T所指结点
    			CreateBiTree(T->lchild); // 递归构造左子树
    			CreateBiTree(T->rchild); // 递归构造右子树
    	}
    }
    
    void DestroyBiTree(BiTree &T)
    { // 初始条件:二叉树T存在。操作结果:销毁二叉树T
    	if(T) // 非空树
    	{ DestroyBiTree(T->lchild); // 递归销毁左子树,如无左子树,则不执行任何操作
    	DestroyBiTree(T->rchild); // 递归销毁右子树,如无右子树,则不执行任何操作
    	free(T); // 释放根结点
    	T=NULL; // 空指针赋0
    	}
    }
    
    void PreOrderTraverse(BiTree T,void(*Visit)(int))
    { // 初始条件:二叉树T存在,Visit是对结点操作的应用函数。修改算法6.1
    	// 操作结果:先序递归遍历T,对每个结点调用函数Visit一次且仅一次
    	if(T) // T不空
    	{
    		if (T->data != 0)
    		{
    		Visit(T->data); // 先访问根结点
    		}
    	PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
    	PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
    	}
    }
    
    void InOrderTraverse(BiTree T,void(*Visit)(int))
    { // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
    	// 操作结果:中序递归遍历T,对每个结点调用函数Visit一次且仅一次
    	if(T)
    	{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
    	if (T->data != 0)
    	{
    	Visit(T->data); // 再访问根结点
    	}
    	InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
    	}
    }
    
    void PostOrderTraverse(BiTree T,void(*Visit)(int))
    { // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
    	// 操作结果:后序递归遍历T,对每个结点调用函数Visit一次且仅一次
    	if(T) // T不空
    	{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
    	PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
    	if (T->data != 0)
    	{
    	Visit(T->data); // 最后访问根结点
    	}
    	}
    }
    
    void main()
    {
    	BiTree T;
    	InitBiTree(T); // 初始化二叉树T
    	printf("按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0\n");
    	CreateBiTree(T); // 建立二叉树T
    	printf("先序递归遍历二叉树:\n");
    	PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
    	printf("\n中序递归遍历二叉树:\n");
    	InOrderTraverse(T,visit); // 中序递归遍历二叉树T
    	printf("\n后序递归遍历二叉树:\n");
    	PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
     }

    if(number==Nil) // 结点的值为空
      T=NULL;

    这句是有问题的,他把等于0的结点的后续全部去掉了,这个代码必须是输入完全二叉树.


    • 已编辑 王译 2011年10月19日 2:22 代码修改
    • 已标记为答案 Helen Zhao 2011年11月2日 3:50
    2011年10月19日 2:14

全部回复

  • ///////////////////////////////////////////////////////////////////////////////
    #include<malloc.h> // malloc()等
    #include<stdio.h> // 标准输入输出头文件,包括EOF(=^Z或F6),NULL等
    #include<stdlib.h> // atoi(),exit()
    #include<math.h> // 数学函数头文件,包括floor(),ceil(),abs()等
    
    
    #define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
    
    typedef struct BiTNode
    {  
    	int data; // 结点的值
    	BiTNode *lchild,*rchild; // 左右孩子指针
    }BiTNode,*BiTree;
    
    int Nil=0; // 设整型以0为空
    
    void visit(int e)
    { printf("%d ",e); // 以整型格式输出
    }
    
    void InitBiTree(BiTree &T)
    { // 操作结果:构造空二叉树T
    	T=NULL;
    // 	T->lchild = NULL;
    // 	T->rchild = NULL;
    }
    
    void CreateBiTree(BiTree &T)
    { 
    	// 算法6.4:按先序次序输入二叉树中结点的值(可为字符型或整型,在主程中定义),
    	// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
    	int number;
    	scanf("%d",&number); // 输入结点的值
    
    	if(number==-1) // 结点的值为空
    	{
    		T = NULL;
    		return;
    	}
    	else // 结点的值不为空
    	{
    		T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
    		if(!T)
    		{
    			printf("loss\n");
    			exit(OVERFLOW);
    		}
    			T->data=number; // 将值赋给T所指结点
    			CreateBiTree(T->lchild); // 递归构造左子树
    			CreateBiTree(T->rchild); // 递归构造右子树
    	}
    }
    
    void DestroyBiTree(BiTree &T)
    { // 初始条件:二叉树T存在。操作结果:销毁二叉树T
    	if(T) // 非空树
    	{ DestroyBiTree(T->lchild); // 递归销毁左子树,如无左子树,则不执行任何操作
    	DestroyBiTree(T->rchild); // 递归销毁右子树,如无右子树,则不执行任何操作
    	free(T); // 释放根结点
    	T=NULL; // 空指针赋0
    	}
    }
    
    void PreOrderTraverse(BiTree T,void(*Visit)(int))
    { // 初始条件:二叉树T存在,Visit是对结点操作的应用函数。修改算法6.1
    	// 操作结果:先序递归遍历T,对每个结点调用函数Visit一次且仅一次
    	if(T) // T不空
    	{
    		if (T->data != 0)
    		{
    		Visit(T->data); // 先访问根结点
    		}
    	PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
    	PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
    	}
    }
    
    void InOrderTraverse(BiTree T,void(*Visit)(int))
    { // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
    	// 操作结果:中序递归遍历T,对每个结点调用函数Visit一次且仅一次
    	if(T)
    	{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
    	if (T->data != 0)
    	{
    	Visit(T->data); // 再访问根结点
    	}
    	InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
    	}
    }
    
    void PostOrderTraverse(BiTree T,void(*Visit)(int))
    { // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
    	// 操作结果:后序递归遍历T,对每个结点调用函数Visit一次且仅一次
    	if(T) // T不空
    	{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
    	PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
    	if (T->data != 0)
    	{
    	Visit(T->data); // 最后访问根结点
    	}
    	}
    }
    
    void main()
    {
    	BiTree T;
    	InitBiTree(T); // 初始化二叉树T
    	printf("按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0\n");
    	CreateBiTree(T); // 建立二叉树T
    	printf("先序递归遍历二叉树:\n");
    	PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
    	printf("\n中序递归遍历二叉树:\n");
    	InOrderTraverse(T,visit); // 中序递归遍历二叉树T
    	printf("\n后序递归遍历二叉树:\n");
    	PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
     }

    if(number==Nil) // 结点的值为空
      T=NULL;

    这句是有问题的,他把等于0的结点的后续全部去掉了,这个代码必须是输入完全二叉树.


    • 已编辑 王译 2011年10月19日 2:22 代码修改
    • 已标记为答案 Helen Zhao 2011年11月2日 3:50
    2011年10月19日 2:14
  • 既然有代码

    单步调试一下

    看看每一步的数据都是否正确

    • 已建议为答案 王译 2011年10月19日 2:22
    2011年10月19日 2:15
  • 既然有代码

    单步调试一下

    看看每一步的数据都是否正确

    是的,我就是单步调出来的.
    2011年10月19日 2:22
  • 那我要怎么改才能不输入完整的二叉树呢??

    2011年10月19日 13:36
  • 不是不可以,但是很麻烦,你要每次输入时同时输入结点的孩子情况,并根据情况创建结点.
    2011年10月20日 0:35
  • 但是我想改出来!
    2011年10月20日 7:06