Ширина первого обхода с переполнением стека бинарного дерева поиска
Может быть, быстрый / простой вопрос. У меня уже реализовано двоичное дерево, затем я надеялся преобразовать двоичное дерево поиска в массив или, по крайней мере, распечатать его, как будто в массиве. У меня проблемы с тем, как получить NULL / флаги там ‘\ 0’.
например, допустим, у меня есть дерево вроде:
10
/ \
6 12
/ \ \
1 8 15
\
4
И я хочу, чтобы это напечатало, как это должно напечатать. Подобно:
[10,6,12,1,8,\0,15,\0,4,\0,\0,\0,\0,\0,\0]
^Something Like this^ I don't know if I counted the NULL correctly.
Или другой вариант того, как я хочу показать визуально, что мое дерево — это как правильно отобразить интервал, например, с помощью «/» и «\», указывающих на ключи от родителей:
10
/ \
6 12
/ \ \
1 8 15
\
4
Вот кое-что, что я попытался развить в коде, но я застрял:
void BreadthFirstTravseral(struct node* root)
{
queue<node*> q;
if (!root) {
return;
}
for (q.push(root); !q.empty(); q.pop()) {
const node * const temp_node = q.front();
cout<<temp_node->data << " ";
if (temp_node->left) {
q.push(temp_node->left);
}
if (temp_node->right) {
q.push(temp_node->right);
}
}
}
Любая помощь или ссылка и / или совет и / или пример кода будет очень цениться.
Решение
Будет очень трудно правильно определить интервал, так как ключ может иметь несколько цифр, и это должно повлиять на интервал для всех уровней выше данного узла.
Что касается того, как добавить NULL — просто добавьте условия else для ваших if, где вы печатаете NULL:
if (root) {
q.push(root);
cout << root->data << " ";
} else {
cout << "NULL ";
}
while (!q.empty()) {
const node * const temp_node = q.front();
q.pop();
if (temp_node->left) {
q.push(temp_node->left);
cout << temp_node->left->data << " ";
} else {
cout << "NULL ";
}if (temp_node->right) {
q.push(temp_node->right);
cout << temp_node->right->data << " ";
} else {
cout << "NULL ";
}
}
Другие решения
void BreadthFirstTravseral(struct node* root)
{
queue<node*> q;
if (!root) {
return;
}
for (q.push(root); !q.empty(); q.pop()) {
const node * const temp_node = q.front();
if( temp_node->special_blank ){
cout << "\\0 " ;
continue;//don't keep pushing blanks
}else{
cout<<temp_node->data << " ";
}
if (temp_node->left) {
q.push(temp_node->left);
}else{
//push special node blank
}
if (temp_node->right) {
q.push(temp_node->right);
}else{
//push special node blank
}
}
}
Как насчет этого:
std::vector<node*> list;
list.push_back(root);
int i = 0;
while (i != list.size()) {
if (list[i] != null) {
node* n = list[i];
list.push_back(n->left);
list.push_back(n->right);
}
i++;
}
Не проверено, но я думаю, что это должно работать.
void TreeBreadthFirst(Node* treeRoot)
{
Queue *queue = new Queue();
if (treeRoot == NULL) return;
queue->insert(treeRoot);
while (!queue->IsEmpty())
{
Node * traverse = queue->dequeue();
cout<< traverse->data << “ “ ;
if (traverse->left != NULL)
queue->insert( traverse->left);
if (traverse->right != NULL)
queue->insert(traverse->right);
}
delete queue;
}
Я сделал программу на с. Этот код будет отображаться как дерево.
struct node{
int val;
struct node *l,*r;
};
typedef struct node node;int findDepth(node *t){
if(!t) return 0;
int l,r;
l=findDepth(t->l);
r=findDepth(t->r);
return l>r?l+1:r+1;
}
void disp(node *t){
if(!t)
return;
int l,r,i=0;
node *a[100],*p;
int front=0,rear=-1,d[100],dep,cur,h;
a[++rear]=t;
d[rear]=0;
cur=-1;
h=findDepth(t);
printf("\nDepth : %d \n",h-1);
while(rear>=front){
dep = d[front];
p=a[front++];
if(dep>cur){
cur=dep;
printf("\n");
for(i=0;i<h-cur;i++) printf("\t");
}
if(p){
printf("%d\t\t",p->val);
a[++rear]=p->l;
d[rear]=dep+1;
a[++rear]=p->r;
d[rear]=dep+1;
}
else printf ("-\t\t");
}
}