Реализуйте
бинарное дерево поиска для целых чисел. Программа получает на вход
последовательность целых чисел и строит из них дерево. Элементы в деревья
добавляются в соответствии с результатом поиска их места. Если элемент уже
существует в дереве, добавлять его не надо. Балансировка дерева не
производится.
Выведите для
полученного дерева список всех листьев (вершин, не имеющих потомков) в порядке
возрастания.
Вход. На вход программа получает
последовательность целых чисел. Последовательность завершается числом 0,
которое означает конец ввода, и добавлять его в дерево не надо. Гарантируется,
что входная последовательность содержит не более 105 элементов,
каждый из которых не превышает по модулю 2·109.
Выход. Выведите для полученного дерева список всех листьев в
порядке возрастания.
|
Пример входа |
Пример выхода |
|
7 3 2 1 9 5 4 6 8 0 |
1 4 6 8 |
структуры данных – дерево
Создадим
бинарное дерево из имеющися чисел. Дерево содержит только уникальные вершины.
Далее совершим обход дерева слева направо и выведем те вершины, у которых нет
сыновей.
Объявим
структуру вершины дерева.
struct TreeNode
{
int data;
TreeNode *left,
*right;
TreeNode(int x) : data(x), left(NULL), right(NULL) {}
};
Объявим
указатель tree на дерево.
TreeNode *tree;
Вставка числа n
в дерево tree. Если число n в дереве уже существует, то ничего не
добавляем.
void insert(TreeNode
*&tree, int n)
{
if (!tree)
{
tree = new TreeNode(n);
return;
}
if (tree->data == n) return;
if (n < tree->data) insert(tree->left,n);
else
insert(tree->right,n);
}
Совершим рекурсивный обход дерева слева направо. Выводим
все листы в порядке обхода.
void
InOrder(TreeNode *tree)
{
if (!tree) return;
InOrder(tree->left);
if((tree->left == NULL) && (tree->right
== NULL))
printf("%d ",tree->data);
InOrder(tree->right);
}
Основная часть программы. Читаем входные данные, строим
дерево.
while(scanf("%d",&n), n)
insert(tree,n);
Обходим дерево, выводим листы.
InOrder(tree);
printf("\n");
Реализация через классы
#include <stdio.h>
int
i, n;
class
Node
{
public:
int data;
Node *left, *right;
Node(int x)
{
data = x;
left = right = NULL;
}
};
class
Tree
{
public:
Node *root;
Tree()
{
root = NULL;
}
void insert(int n)
{
insert(root,n);
}
void
insert(Node *&tree, int n)
{
if (tree ==
NULL)
{
tree = new
Node(n);
return;
}
if
(tree->data == n) return;
if (n <
tree->data)
insert(tree->left,n);
else
insert(tree->right,n);
}
void InOrder(void)
{
InOrder(root);
}
void
InOrder(Node *tree)
{
if (tree ==
NULL) return;
InOrder(tree->left);
if((tree->left
== NULL) && (tree->right == NULL))
printf("%d
",tree->data);
InOrder(tree->right);
}
};
Tree
t;
int
main(void)
{
while(scanf("%d",&n), n)
t.insert(n);
t.InOrder();
printf("\n");
return 0;
}
#include <cstdio>
#include <stack>
using namespace
std;
struct TreeNode
{
int data;
TreeNode *left,
*right;
TreeNode(int x) : data(x), left(NULL), right(NULL) {}
};
TreeNode *tree;
int i, n, flag = 0;
void insert(TreeNode *&tree, int n)
{
if (!tree)
{
tree = new TreeNode(n);
return;
}
if (tree->data == n) return;
if (n < tree->data) insert(tree->left,n);
else
insert(tree->right,n);
}
void InOrderNR(TreeNode *tree)
{
if (tree == NULL) return;
stack<TreeNode
*> s;
TreeNode *current =
tree;
while(!s.empty() || current)
{
if (current)
{
s.push(current);
current =
current->left;
} else
{
current =
s.top();
s.pop();
if((current->left == NULL) &&
(current->right == NULL))
{
if (flag) printf("
");
printf("%d",current->data);
flag = 1;
}
current =
current->right;
}
}
}
int main(void)
{
while(scanf("%d",&n),
n)
insert(tree,n);
InOrderNR(tree);
printf("\n");
return 0;
}
import
java.util.*;
class
TreeNode
{
int val;
TreeNode left;
TreeNode right;
public
TreeNode(int val)
{
this.val =
val;
left = right = null;
}
}
class
Tree
{
TreeNode root = null;
public void insert(int n)
{
root = insert(root,n);
}
// objects are
passed by copy
TreeNode insert(TreeNode tree, int n)
{
if (tree ==
null)
return new TreeNode(n);
if
(tree.val == n) return tree;
if (n <
tree.val)
tree.left = insert(tree.left,n);
else
tree.right = insert(tree.right,n);
return
tree;
}
public void InOrder()
{
InOrder(root);
}
void
InOrder(TreeNode tree)
{
if (tree ==
null) return;
InOrder(tree.left);
if((tree.left
== null) && (tree.right == null))
System.out.print(tree.val + " ");
InOrder(tree.right);
}
};
public class Main
{
public static void
main(String[] args)
{
Tree a = new
Tree();
Scanner con = new
Scanner(System.in);
int n;
while((n =
con.nextInt()) != 0)
a.insert(n);
a.InOrder();
}
}
import
java.util.*;
import
java.io.*;
class
FastScanner
{
private
BufferedReader br;
private
StringTokenizer st;
public
FastScanner(InputStreamReader reader)
{
br = new
BufferedReader(reader);
}
public String
next()
{
while (st
== null || !st.hasMoreTokens())
{
try
{
st = new
StringTokenizer(br.readLine());
} catch
(Exception e)
{
e.printStackTrace();
}
}
return
st.nextToken();
}
public int nextInt()
{
return
Integer.parseInt(next());
}
public double nextDouble()
{
return
Double.parseDouble(next());
}
public void close() throws Exception
{
br.close();
}
}
class
TreeNode
{
int val;
TreeNode left;
TreeNode right;
public
TreeNode(int val)
{
this.val =
val;
left = right = null;
}
}
class
Tree
{
TreeNode root = null;
public void insert(int n)
{
root = insert(root,n);
}
// objects are
passed by copy
TreeNode insert(TreeNode tree, int n)
{
if (tree ==
null)
return new TreeNode(n);
if
(tree.val == n) return tree;
if (n <
tree.val)
tree.left = insert(tree.left,n);
else
tree.right = insert(tree.right,n);
return
tree;
}
public void InOrder()
{
InOrder(root);
}
void
InOrder(TreeNode tree)
{
if (tree ==
null) return;
InOrder(tree.left);
if((tree.left
== null) && (tree.right == null))
System.out.print(tree.val + " ");
InOrder(tree.right);
}
}
public class Main
{
public static void
main(String[] args)
{
Tree a = new
Tree();
FastScanner con =
new FastScanner(new InputStreamReader(System.in));
int n;
while((n =
con.nextInt()) != 0)
a.insert(n);
a.InOrder();
}
}