二叉排序树

[编程题]二叉排序树

热度指数：44501 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

输入一系列整数，建立二叉排序树，并进行前序，中序，后序遍历。

输入描述:

输入第一行包括一个整数n(1<=n<=100)。
接下来的一行包括n个整数。

输出描述:

可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。
每种遍历结果输出一行。每行最后一个数据之后有一个换行。

输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。

示例1

输入

5
1 6 5 9 8

输出

1 6 5 9 8 
1 5 6 8 9 
5 8 9 6 1

算法知识视频讲解

Python

TimeMac

#参考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

编辑于 2018-09-19 15:34:11 回复(0)

Python

fhqplzj

# encoding=utf-8
import sys


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


def put(root, num):
    if root is None:
        return TreeNode(num)
    elif num == root.val:
        return root
    elif num < root.val:
        root.left = put(root.left, num)
        return root
    else:
        root.right = put(root.right, num)
        return root


def build(nums):
    root = None
    for num in nums:
        root = put(root, num)
    return root


def preorder(root):
    if root is not None:
        sys.stdout.write('%d ' % root.val)
        preorder(root.left)
        preorder(root.right)


def inorder(root):
    if root is not None:
        inorder(root.left)
        sys.stdout.write('%d ' % root.val)
        inorder(root.right)


def postorder(root):
    if root is not None:
        postorder(root.left)
        postorder(root.right)
        sys.stdout.write('%d ' % root.val)


while True:
    try:
        input()
        nums = map(int, raw_input().split())
        tree = build(nums)
        preorder(tree)
        print
        inorder(tree)
        print
        postorder(tree)
        print
    except EOFError:
        break

编辑于 2017-01-06 21:11:10 回复(0)