输入第一行包括一个整数n(1<=n<=100)。 接下来的一行包括n个整数。
可能有多组测试数据,对于每组数据,将题目所给数据建立一个二叉排序树,并对二叉排序树进行前序、中序和后序遍历。 每种遍历结果输出一行。每行最后一个数据之后有一个换行。 输入中可能有重复元素,但是输出的二叉树遍历序列中重复元素不用输出。
5 1 6 5 9 8
1 6 5 9 8 1 5 6 8 9 5 8 9 6 1
//have a nice day:D #include<iostream> #include<cstdio> using namespace std; struct TreeNode{ int data; TreeNode* leftChild; TreeNode* rightChild; TreeNode(int x): data(x),leftChild(NULL),rightChild(NULL){} }; void PreOrder(TreeNode* root){ if(root == NULL){ return; } cout<<root->data<<" "; PreOrder(root->leftChild); PreOrder(root->rightChild); return; } void InOrder(TreeNode* root){ if(root == NULL){ return; } InOrder(root->leftChild); cout<<root->data<<" "; InOrder(root->rightChild); return; } void PostOrder(TreeNode* root){ if(root == NULL){ return; } PostOrder(root->leftChild); PostOrder(root->rightChild); cout<<root->data<<" "; return; } TreeNode* Insert(TreeNode* root,int x){ if(root == NULL){ root = new TreeNode(x); } else if(x<root->data){ root->leftChild = Insert(root->leftChild,x); } else if(x>root->data){ root->rightChild = Insert(root->rightChild,x); } return root; } int main(){ int N; int temp; while(cin>>N){ TreeNode* root = NULL; for(int i=0; i<N; i++){ cin>>temp; root = Insert(root,temp); } PreOrder(root); cout<<endl; InOrder(root); cout<<endl; PostOrder(root); cout<<endl; } return 0; }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < arr.length; i ++) { arr[i] = sc.nextInt(); } TreeNode root = new TreeNode(arr[0]); for (int i = 1; i < arr.length; i ++) { createBST(root, arr[i]); } DLR(root); System.out.println(); LDR(root); System.out.println(); LRD(root); System.out.println(); } } public static void createBST(TreeNode root, int value) { if(root.value == value) return; if(value < root.value) { if(root.left == null) root.left = new TreeNode(value); else createBST(root.left, value); } else { if(root.right == null) root.right = new TreeNode(value); else createBST(root.right, value); } } public static void DLR(TreeNode root) { if(root != null) { System.out.print(root.value + " "); DLR(root.left); DLR(root.right); } } public static void LDR(TreeNode root) { if(root != null) { LDR(root.left); System.out.print(root.value + " "); LDR(root.right); } } public static void LRD(TreeNode root) { if(root != null) { LRD(root.left); LRD(root.right); System.out.print(root.value + " "); } } static class TreeNode { private int value; private TreeNode left; private TreeNode right; public TreeNode(int value) { this.value = value; } } }
import java.util.Scanner; class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } public class Main { static void insert(int v, TreeNode root) { if (v != root.val) { if (v < root.val) { // 小于根节点,往左 if (root.left == null) { // 若左节点为空,直接插入 root.left = new TreeNode(v); } else { insert(v, root.left); // 若左节点不为空,把左节点当做根节点递归调用insert } } else { if (root.right == null) { root.right = new TreeNode(v); } else { insert(v, root.right); } } } } // 前序遍历 static void preorderTraversal(TreeNode root) { if (root == null) return; System.out.print(root.val + " "); preorderTraversal(root.left); preorderTraversal(root.right); } // 中序遍历 static void inorderTraversal(TreeNode root) { if (root == null) return; inorderTraversal(root.left); System.out.print(root.val + " "); inorderTraversal(root.right); } // 后序遍历 static void postorderTraversal(TreeNode root) { if (root == null) return; postorderTraversal(root.left); postorderTraversal(root.right); System.out.print(root.val + " "); } public static void main(String[] args) { int n = 0; Scanner in = new Scanner(System.in); while (in.hasNext()) { n = in.nextInt(); int v = in.nextInt(); TreeNode root = new TreeNode(v); n--; while (n > 0) { v = in.nextInt(); insert(v, root); n--; } preorderTraversal(root); System.out.println(); inorderTraversal(root); System.out.println(); postorderTraversal(root); System.out.println(); } } }
/** 参考 CSDN Blog : http://blog.csdn.net/stpeace/article/details/9067029 */ #include<iostream> #include<cstdio> using namespace std; const int maxn = 105; int num[maxn] = {0}; // BST 树的结点 typedef struct node { int key; struct node *lChild; // 指针定义分开 struct node *rChild; }Node, *BST; // BST 树插入节点 bool insertNode(Node* &p, int i) { if(p == NULL) { p = new Node; p->key = i; p->lChild = p->rChild = NULL; return true; } if(i == p->key) return false; if(i < p->key) return insertNode(p->lChild, i); if(i > p->key) return insertNode(p->rChild, i); return false; // 确保一定有返回值 } // 根据已知数组创建 BST void createBST(Node* &T, int a[], int n) { T = NULL; for(int i = 0; i < n; ++i) { insertNode(T, a[i]); } } // 先序遍历 void preOrderTraverse(BST T) { if(T != NULL) { cout << T->key << " "; preOrderTraverse(T->lChild); preOrderTraverse(T->rChild); } } // 中序遍历 void inOrderTraverse(BST T) { if(T != NULL) { inOrderTraverse(T->lChild); cout << T->key << " "; inOrderTraverse(T->rChild); } } // 后续遍历 void lastOrderTraverse(BST T) { if(T != NULL) { lastOrderTraverse(T->lChild); lastOrderTraverse(T->rChild); cout << T->key << " "; } } int main() { int n; BST T; while(cin >> n) { for(int i = 0; i < n; ++i) { cin >> num[i]; } createBST(T, num, n); preOrderTraverse(T); cout << endl; inOrderTraverse(T); cout << endl; lastOrderTraverse(T); cout << endl; } return 0; }
#include<iostream> using namespace std; typedef struct node { int val; node * left,*right; node(int val):val(val),left(NULL),right(NULL){} }BTree; void Insert(BTree * &t,int v) { if(t == NULL) { t = new node(v); return; } if(t->val == v) return; if(v < t->val) Insert(t->left,v); if(v > t->val) Insert(t->right, v); } void preOrder(BTree * t) { if(t == NULL) return; cout << t->val << ' '; preOrder(t->left); preOrder(t->right); } void inOrder(BTree * t) { if(t == NULL) return; inOrder(t->left); cout << t->val << ' '; inOrder(t->right); } void postOrder(BTree * t) { if(t == NULL) return; postOrder(t->left); postOrder(t->right); cout << t->val << ' '; } int main(void) { int n; while(cin >> n) { getchar(); BTree * t = NULL; for(int i = 0;i < n;i++) { int v; cin >> v; Insert(t,v); } preOrder(t); cout << endl; inOrder(t); cout << endl; postOrder(t); cout << endl; } return 0; }
#include<bits/stdc++.h> using namespace std; struct Node { int v; struct Node* lchild,* rchild; }; Node* newNode(int x) { Node* t = new Node; t->v = x; t->lchild = t->rchild = nullptr; return t; } void Insert(Node* &root, int x) { if(root == nullptr) { root = newNode(x); return ; } if(root->v == x) return ; else if(root->v < x) Insert(root->rchild, x); else Insert(root->lchild, x); } Node* Create(int n) { int x; Node* root = nullptr; for(int i = 0;i < n; i++) { cin >> x; Insert(root, x); } return root; } void PreOrder(Node* root) { if(root == nullptr) return ; cout << root->v << ' '; PreOrder(root->lchild); PreOrder(root->rchild); } void MidOrder(Node* root) { if(root == nullptr) return ; MidOrder(root->lchild); cout << root->v << ' '; MidOrder(root->rchild); } void LastOrder(Node* root) { if(root == nullptr) return ; LastOrder(root->lchild); LastOrder(root->rchild); cout << root->v << ' '; } int main() { ios::sync_with_stdio(false); int n; while(cin >> n) { Node* root = Create(n); PreOrder(root); cout << '\n'; MidOrder(root); cout << '\n'; LastOrder(root); cout << '\n'; } return 0; }
#include<iostream> using namespace std; struct TNode { int data; TNode* left, * right; TNode(int x) :data(x), left(nullptr), right(nullptr) {} }; void build(int node, TNode*& tree) { TNode* move = tree, * parent = nullptr; while (move != nullptr) { parent = move; if (node < move->data) move = move->left; else if (node > move->data) move = move->right; else return; } TNode* temp = new TNode(node); if (parent == nullptr) tree = temp; else if (node < parent->data) parent->left = temp; else parent->right = temp; } void preOrder(TNode*& tree) { if (tree != nullptr) { cout << tree->data << " "; preOrder(tree->left); preOrder(tree->right); } } void inOrder(TNode*& tree) { if (tree != nullptr) { inOrder(tree->left); cout << tree->data << " "; inOrder(tree->right); } } void postOrder(TNode*& tree) { if (tree != nullptr) { postOrder(tree->left); postOrder(tree->right); cout << tree->data << " "; } } int main() { int n; while (cin>>n) { int node; TNode* tree = nullptr; for (int i = 0; i < n; i++) { cin >> node; build(node, tree); } preOrder(tree); cout << endl; inOrder(tree); cout << endl; postOrder(tree); cout << endl; } return 0; }
import java.util.Scanner; public class Main { static class Node { int value; Node left; Node right; Node(int value) { this.value = value; } } // creat 写法一 static void creat1(Node root, int value) { if (value < root.value) { if (root.left == null) root.left = new Node(value); else creat1(root.left, value); } else if (value > root.value) { if (root.right == null) root.right = new Node(value); else creat1(root.right, value); } } // creat 写法二 static Node creat2(Node root,int value){ if (root==null) root=new Node(value); else if (value<root.value) root.left=creat2(root.left,value); else if (value>root.value) root.right=creat2(root.right,value); return root; } static void preOrder(Node root) { if (root != null) { System.out.print(root.value + " "); preOrder(root.left); preOrder(root.right); } } static void inOder(Node root) { if (root != null) { inOder(root.left); System.out.print(root.value + " "); inOder(root.right); } } static void postOrder(Node root) { if (root != null) { postOrder(root.left); postOrder(root.right); System.out.print(root.value + " "); } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); Node root = new Node(scanner.nextInt()); for (int i = 1; i < n; i++) creat2(root, scanner.nextInt()); preOrder(root); System.out.println(); inOder(root); System.out.println(); postOrder(root); System.out.println(); } } }
#include <iostream> #include <memory> using namespace std; struct node{ int data; shared_ptr<node> left,right; node():data(0),left(nullptr),right(nullptr){}; node(const int& d):data(d),left(nullptr),right(nullptr){}; }; typedef shared_ptr<node> tree; void build_tree(tree& l,const int& d){ if(l==nullptr){ l = make_shared<node>(d);//待插入节点 return; } if(d<l->data) build_tree(l->left,d); else if(d>l->data) build_tree(l->right,d); return; } void pre_order(tree& l){ if(l==nullptr) return; cout<<l->data<<' '; pre_order(l->left); pre_order(l->right); } void mid_order(tree& l){ if(l==nullptr) return; mid_order(l->left); cout<<l->data<<' '; mid_order(l->right); } void post_order(tree& l){ if(l==nullptr) return; post_order(l->left); post_order(l->right); cout<<l->data<<' '; } int main(){ int n,x; while(cin>>n){ tree my_tree; for(int i(0);i<n;++i){ cin>>x; build_tree(my_tree,x); } pre_order(my_tree); cout<<endl; mid_order(my_tree); cout<<endl; post_order(my_tree); cout<<endl; } return 0; }
#include<iostream> using namespace std; int n; class tree { public: int data; tree *lc; tree *rc; }; void build(tree *node,tree *head) { if (node->data == head->data) return; //去除重复元素 if (node->data < head->data) { if (!head->lc) //左子树若为空则直接插入 { head->lc = node; } else { build(node, head->lc); //从左子树递归查找 } } if (node->data > head->data) { if (!head->rc) { head->rc = node; } else { build(node, head->rc); //右 } } } void pre(tree *head) //前序 { tree *temp = head; if (temp != NULL) { cout << temp->data << " "; pre(temp->lc); pre(temp->rc); } } void mid(tree *head) //中序 { tree *temp = head; if (temp != NULL) { mid(temp->lc); cout << temp->data<<" "; mid(temp->rc); } } void behind(tree *head) //后序 { tree *temp = head; if (temp != NULL) { behind(temp->lc); behind(temp->rc); cout << temp->data << " "; } } int main() { while (cin>>n) { tree *head; tree *node; head = new tree; //建立树根节点 分配空间 head->data = 0; head->lc = head->rc = NULL; cin >> head->data; //输入根节点数据 for (int i = 1; i < n; i++) { node = new tree; //建立新节点 分配空间 node->data = 0; node->lc = NULL; node->rc = NULL; cin >> node->data; build(node, head); //插入新节点 } pre(head); cout << endl; mid(head); cout << endl; behind(head); cout << endl; } }c++版本 用链表实现 简单易懂
#include <iostream> using namespace std; typedef struct node { int data; struct node *lchild, *rchild; }BSTNode, *BSTree; void InsertTree(BSTree &T, int x) { if(T == NULL){ T = new BSTNode; T->data = x; T->rchild = NULL; T->lchild = NULL; } else if(x < T->data) InsertTree(T->lchild, x); else if(x == T->data) return; else InsertTree(T->rchild, x); } void preTraverse(BSTree T) { if(T == NULL) return; cout << T->data << " "; preTraverse(T->lchild); preTraverse(T->rchild); } void inTraverse(BSTree T) { if(T == NULL) return; inTraverse(T->lchild); cout << T->data << " "; inTraverse(T->rchild); } void postTraverse(BSTree T) { if(T == NULL) return; postTraverse(T->lchild); postTraverse(T->rchild); cout << T->data << " "; } int main() { int n; while (cin >> n) { BSTree T = NULL; for (int i = 0; i < n; i++) { int x; cin >> x; InsertTree(T, x); } preTraverse(T); cout << endl; inTraverse(T); cout << endl; postTraverse(T); cout << endl; } }
#include <iostream> #include <vector> #include <queue> #include <climits> #include <cassert> using namespace std; template <typename T> struct BSTNode { using valueType = T; BSTNode* leftChild; BSTNode* rightChild; valueType element; explicit BSTNode(const valueType data = T(), BSTNode* left = nullptr, BSTNode* right = nullptr) : element(data), leftChild(left), rightChild(right) { } }; template <typename T> class BSTree { public: using valueType = T; BSTNode<valueType>* root; explicit BSTree() { root = nullptr; } void insert(const valueType& data); void clear(); bool empty() { return root == nullptr; } }; template <typename valueType> void freeTree(BSTNode<valueType>* &root) { if (root->leftChild) freeTree(root->leftChild); if (root->rightChild) freeTree(root->rightChild); if (root) { delete root; root = nullptr; } return; } template <typename valueType> void BSTree<valueType>::insert(const valueType& data) { BSTNode<valueType>* parent = nullptr, * node = root; while (node) { parent = node; if (node->element > data) node = node->leftChild; else if (node->element < data) node = node->rightChild; else if (node->element == data) return; } if (root == nullptr) root = new BSTNode<valueType>(data); else if (parent->element < data) parent->rightChild = new BSTNode<valueType>(data); else if (parent->element > data) parent->leftChild = new BSTNode<valueType>(data); return; } template <typename valueType> void BSTree<valueType>::clear() { if (root) freeTree(root); return; } void preOrderTraversal(BSTNode<int>* node) { cout << node->element << " "; if (node->leftChild) preOrderTraversal(node->leftChild); if (node->rightChild) preOrderTraversal(node->rightChild); } void inOrderTraversal(BSTNode<int>* node) { if (node->leftChild) inOrderTraversal(node->leftChild); cout << node->element << " "; if (node->rightChild) inOrderTraversal(node->rightChild); } void postOrderTraversal(BSTNode<int>* node) { if (node->leftChild) postOrderTraversal(node->leftChild); if (node->rightChild) postOrderTraversal(node->rightChild); cout << node->element << " "; } int main() { BSTree<int> tree; int n, temp; while (cin >> n) { for (int i = 0; i < n; ++i) { cin >> temp; tree.insert(temp); } preOrderTraversal(tree.root); cout << endl; inOrderTraversal(tree.root); cout << endl; postOrderTraversal(tree.root); cout << endl; tree.clear(); assert(tree.empty()); } return 0; }
#include<stdio.h> #include<string.h> struct node{ node *lchild,*rchild; int c; }tree[110]; int loc; node *create(){ tree[loc].lchild=tree[loc].rchild=NULL; return &tree[loc++]; } void postOrder(node *T){ if(T->lchild!=NULL) postOrder(T->lchild); if(T->rchild!=NULL) postOrder(T->rchild); printf("%d ",T->c); } void inOrder(node *T){ if(T->lchild!=NULL) inOrder(T->lchild); printf("%d ",T->c); if(T->rchild!=NULL) inOrder(T->rchild); } void preOrder(node *T){ printf("%d ",T->c); if(T->lchild!=NULL) preOrder(T->lchild); if(T->rchild!=NULL) preOrder(T->rchild); } node *insert(node *T,int x){ if(T==NULL){ T=create(); T->c=x; return T; }else if(x<T->c) T->lchild=insert(T->lchild,x); else if(x>T->c) T->rchild=insert(T->rchild,x); return T; } int main(){ int n; while(~scanf("%d",&n)){ loc=0; node *T=NULL; for(int i=0;i<n;i++){ int x; scanf("%d",&x); T=insert(T,x); } preOrder(T); printf("\n"); inOrder(T); printf("\n"); postOrder(T); printf("\n"); } return 0; }先把树建立起来,就好说了
#参考SINGLE、DOG的Python版 class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right def insertNode(value, root): #插入节点 if root.data == value: return if root.data < value: if not root.right: root.right = Node(value) else: insertNode(value, root.right) else: if not root.left: root.left = Node(value) else: insertNode(value, root.left) def pre_orderTtaversing(root): #前序遍历 if not root: return print(root.data, end=" ") pre_orderTtaversing(root.left) pre_orderTtaversing(root.right) def mid_orderTtaversing(root): #中序遍历 if not root: return mid_orderTtaversing(root.left) print(root.data, end=" ") mid_orderTtaversing(root.right) def post_orderTtaversing(root): #后序遍历 if not root: return post_orderTtaversing(root.left) post_orderTtaversing(root.right) print(root.data, end=" ") try: while True: num = int(input()) nodeList = list(map(int, input().split())) root = Node(nodeList[0]) for i in range(1, num): insertNode(nodeList[i], root) pre_orderTtaversing(root) print() mid_orderTtaversing(root) print() post_orderTtaversing(root) print() except Exception: pass
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); while(scan.hasNextInt()) { BinarySearchTree searchTree = new BinarySearchTree(); int n = scan.nextInt(); for(int i = 0; i < n; i++) searchTree.insert(scan.nextInt()); BinarySearchTree.preOrder(searchTree.root); System.out.println(); BinarySearchTree.inOrder(searchTree.root); System.out.println(); BinarySearchTree.postOrder(searchTree.root); System.out.println(); } scan.close(); } } class Node { int key; Node leftChild; Node rightChild; public Node(int key) { this.key = key; leftChild = null; rightChild = null; } } class BinarySearchTree { Node root; public boolean insert(int key) { if (root == null) { root = new Node(key); return true; } Node current = root; Node parent = null; boolean belongLeft = false; while (current != null) { parent = current; if (key < current.key) { current = current.leftChild; belongLeft = true; } else if (key > current.key) { current = current.rightChild; belongLeft = false; } else return false; } Node insertion = new Node(key); if (belongLeft) parent.leftChild = insertion; else parent.rightChild = insertion; return true; } /** * 先序遍历 * @param root * 根节点 */ public static void preOrder(Node root) { if (root != null) { System.out.print(root.key + " "); preOrder(root.leftChild); preOrder(root.rightChild); } } /** * 中序遍历 * @param root * 根节点 */ public static void inOrder(Node root) { if (root != null) { inOrder(root.leftChild); System.out.print(root.key + " "); inOrder(root.rightChild); } } /** * 后序遍历 * @param root * 根节点 */ public static void postOrder(Node root) { if (root != null) { postOrder(root.leftChild); postOrder(root.rightChild); System.out.print(root.key + " "); } } }
#include<stdio.h> #include<malloc.h> typedef struct BNode{ int data; struct BNode* lchild; struct BNode* rchild; }Node,*Tree; void Create(Tree &t,int x){ if(!t){ t=(Node*)malloc(sizeof(Node)); t->data=x; t->lchild=t->rchild=NULL; } else if(x<t->data)Create(t->lchild,x); else if(x>t->data)Create(t->rchild,x); } void PreOrder(Tree t){ printf("%d ",t->data); if(t->lchild)PreOrder(t->lchild); if(t->rchild)PreOrder(t->rchild); } void InOrder(Tree t){ if(t->lchild)InOrder(t->lchild); printf("%d ",t->data); if(t->rchild)InOrder(t->rchild); } void PostOrder(Tree t){ if(t->lchild)PostOrder(t->lchild); if(t->rchild)PostOrder(t->rchild); printf("%d ",t->data); } int main(){ int n; int a; while(scanf("%d",&n)!=EOF){ Tree t=NULL; for(int i=0;i<n;i++){ scanf("%d",&a); Create(t,a); } PreOrder(t); printf("\n"); InOrder(t); printf("\n"); PostOrder(t); printf("\n"); free(t); } return 0; }
import java.util.Scanner; class TreeNode{ TreeNode left; TreeNode right; int value; public TreeNode(int value){ this.value = value; } } public class Main{ public static void main(String[] args){ Scanner scan = new Scanner(System.in); while(scan.hasNext()){ int n = scan.nextInt(); TreeNode root = null; for(int i=0;i<n;i++){ root = insert(root, scan.nextInt()); } preOrder(root); System.out.println(); inOrder(root); System.out.println(); backOrder(root); System.out.println(); } } public static void preOrder(TreeNode root){ if(root!=null){ System.out.print(root.value+" "); preOrder(root.left); preOrder(root.right); } } public static void inOrder(TreeNode root){ if(root!=null){ inOrder(root.left); System.out.print(root.value+" "); inOrder(root.right); } } public static void backOrder(TreeNode root){ if(root!=null){ backOrder(root.left); backOrder(root.right); System.out.print(root.value+" "); } } public static TreeNode insert(TreeNode root, int value){ if(root == null) root = new TreeNode(value); if(root.value == value) return root; if(root.value> value){ root.left = insert(root.left, value); }else root.right = insert(root.right, value); return root; } }
我把二叉排序树又抽象了一层
package com.speical.first;
import java.util.Scanner;
/**
* @author Special
* @time 2018/02/05 05:28:59
*/
public class Pro194 {
static class BST{
Node root;
int size;
class Node{
int value;
Node left, right;
public Node(int value) {
this.value = value;
}
}
public void addNode(Node node) {
if(size == 0) {
root = node;
}else {
Node point = root, parent = root;
while(point != null) {
if(node.value == point.value) { return; }
parent = point;
if(node.value < point.value) {
point = point.left;
}else if(node.value > point.value) {
point = point.right;
}
}
if(node.value < parent.value) {
parent.left = node;
}else {
parent.right = node;
}
}
size++;
}
public void preOrder(Node node) {
if(node != null) {
System.out.print(node.value + " ");
preOrder(node.left);
preOrder(node.right);
}
}
public void inOrder(Node node) {
if(node != null) {
inOrder(node.left);
System.out.print(node.value + " ");
inOrder(node.right);
}
}
public void postOrder(Node node) {
if(node != null) {
postOrder(node.left);
postOrder(node.right);
System.out.print(node.value + " ");
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
while(input.hasNext()) {
int n = input.nextInt();
BST bst = new BST();
while(n-- > 0) {
bst.addNode(bst.new Node(input.nextInt()));
}
bst.preOrder(bst.root);
System.out.println();
bst.inOrder(bst.root);
System.out.println();
bst.postOrder(bst.root);
System.out.println();
}
}
}