c/c++语言开发共享横向打印二叉树-计算机技术网

c/c++语言开发共享横向打印二叉树

2021年5月16日上午10:02 • C/C++开发 • 阅读 1

历届试题横向打印二叉树

时间限制：1.0s 内存限制：256.0mb

问题描述

二叉树可以用于排序。其原理很简单：对于一个排序二叉树添加新节点时，先与根节点比较，若小则交给左子树继续处理，否则交给右子树。

当遇到空子树时，则把该节点放入那个位置。

比如，10 8 5 7 12 4 的输入顺序，应该建成二叉树如下图所示，其中.表示空白。

…|-12
10-|
…|-8-|
…….|…|-7
…….|-5-|
………..|-4

本题目要求：根据已知的数字，建立排序二叉树，并在标准输出中横向打印该二叉树。

输入格式

输入数据为一行空格分开的n个整数。 n<100，每个数字不超过10000。

输入数据中没有重复的数字。

输出格式

输出该排序二叉树的横向表示。为了便于评卷程序比对空格的数目，请把空格用句点代替：

样例输入1

10 5 20

样例输出1

…|-20
10-|
…|-5

样例输入2

5 10 20 8 4 7

样例输出2

…….|-20
..|-10-|
..|….|-8-|
..|……..|-7
5-|
..|-4

#include<iostream>  #include<algorithm>  using namespace std;  char ch[200][200];  int getbit(int x)  {      int sum=0;      while(x)      {          sum++;          x/=10;      }      return sum;  }    class tree  {    public:      tree(int x_)      {          val=x_;          bit=getbit(x_);          par=0;          x=100;          y=0;          l_sum=0;          r_sum=0;        }      tree()      {          val=-1;          bit=0;          par=0;           x=100;          y=0;          l_sum=0;          r_sum=0;        }    public:      tree *lchild=null;      tree *rchild=null;      int val;      int bit;      int par;      int x;      int y;      int l_sum;      int r_sum;      };      int print( tree *t)  {        if(t->val!=-1){              int b=t->bit,v=t->val;         for(int i=t->y+b-1;i>=t->y ;i--){            ch[t->x][i]=v%10+'0';            v/=10;         }          if(t->l_sum||t->r_sum){//根节点          ch[t->x][t->y+t->bit]='-';      }      if(t->par)ch[t->x][t->y-1]='-';        if(t->lchild->val!=-1&&t->rchild->val!=-1){              for(int i= t->x-t->lchild->r_sum-1;i<=t->x+t->rchild->l_sum+1;i++){                  ch[i][t->y+t->bit+1]='|';              }              t->lchild->x=t->x-t->lchild->r_sum-1;              t->rchild->x=t->x+t->rchild->l_sum+1;          }      else if(t->lchild->val!=-1){          for(int i= t->x-t->lchild->r_sum-1;i<=t->x;i++){                  ch[i][t->y+t->bit+1]='|';              }              t->lchild->x=t->x-t->lchild->r_sum-1;          }      else if(t->rchild->val!=-1){            for(int i= t->x ;i<=t->x+t->rchild->l_sum+1;i++){                  ch[i][t->y+t->bit+1]='|';              }                t->rchild->x=t->x+t->rchild->l_sum+1;        }      }      if(t->rchild->val!=-1)print(t->rchild);      if(t->lchild->val!=-1)print(t->lchild);          return t->r_sum;        }    void build(tree *t,tree *t)  {        if(t->val==-1)      {            t->val=t->val;          t->bit=t->bit;          t->x=t->x;          t->y=t->y;          t->l_sum=t->l_sum;          t->r_sum=t->r_sum;          t->lchild=new tree();          t->rchild=new tree();          t->lchild->par=1;          t->rchild->par=1;        }      else if(t->val<t->val)      {          t->r_sum++;          t->y+=(3+t->bit);          build(t,t->rchild);          }      else      {          t->l_sum++;          t->y+=(3+t->bit);          build(t,t->lchild);        }          }        int main()  {      int num;        tree *tree = new tree();      tree *t;      int n=0;      int j;      while(cin>>num)      {          t = new tree(num);            build(t,tree);          n++;        }      for(int i=0;i<200;i++){//将数组初始化为.矩阵      for(int j=0;j<200;j++){          ch[i][j]='.';      }  }        int x=  print(tree);          for(int i=100+x;i>=101-(n-x) ;i--){      for(  j=110;j;j--)      {          if(ch[i][j]!='.')break;            }      for(int k=0;k<=j;k++){           cout<<ch[i][k];      }      cout<<endl;      }        return 0;  }

解题思路，先建立排序二叉树，然后从根节点开始遍历，将数打印到一个二维数组中，然后输出二维数组；

本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址：https://www.ctvol.com/c-cdevelopment/608551.html

c/c++语言开发共享横向打印二叉树

精彩推荐