各种语言实现二叉树

2017-06-02

过两天考编程范式,复习各个语言的语法,索性整理一篇博客出来,用不同的语言实现二叉树的相关数据结构,以后会不断添加完善。

Scheme

作为一门函数式编程语言,scheme实现二叉树结构极为简单。

1.创建二叉树

;;;create tree
(define (make-tree root left right)
  (list root left right))

2.返回二叉树的根节点,左子树和右子树分别对应的函数

;;;return root
(define (root tree)
  (car tree))
  
;;;return left branch
(define (left tree)
  (cadr tree))
  
;;;return right branch
(define (right tree)
  (caddr tree))

3.判断二叉树是否为空

;;;empty tree?
(define (empty-tree? tree)
  (null? tree))

4.插入元素构造二叉查找树(BST)

二叉查找树可以用一个一个节点插入的方式来构造,递归构造的思想就是:

如果插入的树为空,则该元素作为当前节点
如果插入的节点小于根结点,则插入左子树
如果插入的节点大于等于根结点,则插入右子树

在scheme中有多个条件分支时可用cond关键字来进行条件判断。

;;;insert elements to create a binary search tree
(define (insert element tree)
  (cond ((empty-tree? tree)
         (make-tree element '() '()))
        ((< element (root tree))
         (make-tree (root tree)
                    (insert element (left tree))
                    (right tree)))
        ((>= element (root tree))
         (make-tree (root tree)
                    (left tree)
                    (insert element (right tree))))))

5.从一个列表中构造二叉查找树

此处基本思想:

基线条件:列表为空时返回。
否则,若表中有n个元素,后n-1个元素已经构成一个二叉查找树,把第一个元素插入树中即可。

;;;build a binary search tree from a list
(define (build-tree commonlist)
  (if (null? commonlist)
      '()
      (insert (car commonlist) (build-tree (cdr commonlist)))))

6.平衡二叉树(AVL)

Python

Go