蓝桥杯2013年第四届真题-横向打印二叉树-题解（C++代码）

解题思路:

注意事项:

参考代码:

#include <bits/stdc++.h>

using namespace std;

struct node{

int num;

node *lchild;

node *rchild;

};

node *T = NULL;

void addnum(int num)

{

node *temp = NULL,*now = NULL;

if(T == NULL)

{

temp = (node *)malloc(sizeof(node));

temp->num = num;

temp->lchild = NULL;

temp->rchild = NULL;

T = temp;

}

else

{

temp = (node *)malloc(sizeof(node));

temp->num = num;

temp->lchild = NULL;

temp->rchild = NULL;

now = T;

while(1)

{

if(num > now->num && now->rchild !=NULL)

now = now->rchild;

else if(num < now->num && now->lchild !=NULL)

now = now->lchild;

else if(num > now->num && now->rchild ==NULL)

{

now->rchild = temp;

break;

}

else

{

now->lchild = temp;

break;

}

}

}

}

int length(int num,string &temp)

{

char c[10];

int length = 0;

while(num!=0)

{

c[length++] = num % 10 + '0';

num = num / 10;

}

for(int i = length-1;i>=0;i--)

{

temp = temp + c[i];

}

return length;

}

void print()

{

string c[101];

int num[10000] = {0};

int count = 1;

stack<node*> s;

node *now = NULL,*pre = NULL;

now = T;

s.push(T);

while(!s.empty())

{

now = s.top();

if(now->rchild != NULL && num[now->rchild->num] == 0)

{

now = now->rchild;

s.push(now);

}

else

{

num[now->num] = count++;

s.pop();

if(now->lchild != NULL)

{

now = now->lchild;

s.push(now);

}

}

}

queue<node*> q;

queue<int> add;

int need[101] ={0};

q.push(T);

int line;

int le = 0;

int left,right;

string temp = "";

int flag = 0;

while(!q.empty())

{

temp.clear();

now = q.front();

q.pop();

line = num[now->num];

if(now->lchild!= NULL)

{

left = num[now->lchild->num];

q.push(now->lchild);

}

else

left = line;

if(now->rchild != NULL)

{

right = num[now->rchild->num];

q.push(now->rchild);

}

else

right = line;

le = length(now->num,temp);

int i;

if(flag == 1)

c[line] = c[line]+"-"+temp;

else

{

c[line] = temp;

flag = 1;

}

need[line] = 1;

if(right != left)

c[line] = c[line] + "-|";

for(int i = 1;i<count;i++)

{

if(need[i] == 0)

{

if(i>=right && i<=left && i != line)

{

for(int j = c[i].length();j<c[line].length()-1;j++)

{

c[i] = c[i] + ".";

}

c[i] = c[i] + "|"; 

}

}

}

}

for(int i = 1;i<count;i++)

{

cout<<c[i]<<endl;

}

}

int main()

{

int num;

while(scanf("%d",&num)!=EOF)

{

addnum(num);

}

if(T !=NULL)

print();

return 0;

}