学习二叉树

树的定义

树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构,以分层的方式 存储数据。树被用来存储具有层级关系的数据,比如文件系统中的文件;树还被用来存储 有序列表。选择树而不是那些基本的数据结构,是因 为在二叉树上进行查找非常快(而在链表上查找则不是这样),为二叉树添加或删除元素 也非常快(而对数组执行添加或删除操作则不是这样)。


树的种类


  • 无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树

  • 有序树:树中任意节点的子节点之间有顺序关系,这种树称为有序树

    • 二叉树:每个节点最多含有两个子树的树称为二叉树;完全二叉树:对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树;满二叉树:所有叶节点都在最底层的完全二叉树;平衡二叉树(AVL树):当且仅当任何节点的两棵子树的高度差不大于1的二叉树;排序二叉树(二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树)

    • 霍夫曼树:带权路径最短的二叉树称为哈夫曼树或最优二叉树

    • B树:一种对读写操作进行优化的自平衡的二叉查找树,能够保持数据有序,拥有多余两个子树



    有关树的术语

    >

    1. 节点的度:一个节点含有的子树的个数称为该节点的度;
    2. 树的度:一棵树中,最大的节点的度称为树的度;
    3. 叶节点或终端节点:度为零的节点;
    4. 非终端节点或分支节点:度不为零的节点;
    5. 父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;
    6. 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
    7. 兄弟节点:具有相同父节点的节点互称为兄弟节点;
    8. 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
    9. 树的高度或深度:树中节点的最大层次;
    10. 堂兄弟节点:父节点在同一层的节点互为堂兄弟;
    11. 节点的祖先:从根到该节点所经分支上的所有节点;
    12. 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
    13. 森林:由m(m>=0)棵互不相交的树的集合称为森林;
      >

    二叉树

    二叉树是一种特殊的树,它的子节点个数不超过两个。每个节点最多有两棵子树,所以二叉树中不存在度大于2的节点。二叉树中每一个节点都是一个对象,每一个数据节点都有三个指针,分别是指向父母、左孩子和右孩子的指针。每一个节点都是通过指针相互连接的。相连指针的关系都是父子关系

    特殊的二叉树


    • 满二叉树: 在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树

    • 完全二叉树: 是指最后一层左边是满的,右边可能满也可能不满,然后其余层都是满的


    用js生成一个二叉树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    function BinaryTree() {
    var _this = this;
    this.root = null;
    var Node = function (key) {
    this.key = key;
    this.left = null;
    this.right = null;
    }
    this.show = function (key) {
    console.log(key)
    }
    var insertNode = function (node, newNode) {
    if (newNode.key < node.key) {
    if (node.left === null) {
    node.left = newNode
    } else {
    insertNode(node.left, newNode)
    }
    } else {
    if (node.right === null) {
    node.right = newNode
    } else {
    insertNode(node.right, newNode)
    }
    }
    }
    this.show = function (key) {
    console.log(key)
    }
    this.insert = function (key) {
    var newnode = new Node(key)
    if (this.root === null) {
    this.root = newnode
    } else {
    insertNode(this.root, newnode)
    }
    }
    }
    var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]
    var binaryTree = new BinaryTree()
    nodes.forEach(function (key) {
    binaryTree.insert(key)
    })
    console.log(binaryTree)

    中序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    //中序遍历可以输出一个有序的结果
    function inOrderTraverse(node){
    if(!(node == null)){
    inOrderTraverse(node.left);//访问左子树
    this.show(node.key);//输出根节点
    inOrderTraverse(node.right);//访问右子树
    }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    function BinaryTree() {
    var _this = this;
    this.root = null;
    var Node = function (key) {
    this.key = key;
    this.left = null;
    this.right = null;
    }
    this.show = function (key) {
    console.log(key)
    }
    var insertNode = function (node, newNode) {
    if (newNode.key < node.key) {
    if (node.left === null) {
    node.left = newNode
    } else {
    insertNode(node.left, newNode)
    }
    } else {
    if (node.right === null) {
    node.right = newNode
    } else {
    insertNode(node.right, newNode)
    }
    }
    }
    this.show = function (key) {
    console.log(key)
    }
    this.insert = function (key) {
    var newnode = new Node(key)
    if (this.root === null) {
    this.root = newnode
    } else {
    insertNode(this.root, newnode)
    }
    }
    var inOrderTraverseNode = function (node) {
    if (node != null) {
    inOrderTraverseNode(node.left)
    _this.show(node.key)
    inOrderTraverseNode(node.right)
    }
    }
    this.inOrderTraverse = function () {
    inOrderTraverseNode(this.root)
    }
    }
    var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]
    var BinaryTree = new BT()
    nodes.forEach(function (key) {
    BinaryTree.insert(key)
    })
    console.log(BinaryTree)
    BinaryTree.inOrderTraverse()//1 3 4 6 7 8 10 13 14

    前序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    //前序遍历适用于需要复制一个二叉树时
    function preOrderTraverse(node){
    if(!(node == null)){
    this.show(node.key);//输出根节点
    preOrderTraverse(node.left);//访问左子树
    preOrderTraverse(node.right);//访问右子树
    }
    }

    后序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    //后序遍历适用于操作系统文件遍历
    function postOrderTraverse(node){
    if(!(node == null)){
    postOrderTraverse(node.left);//访问左子树
    postOrderTraverse(node.right);//访问右子树
    this.show(node.key);//输出根节点
    }
    }

    查找最小值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    var minNode = function (node) {
    if (node) {
    //当节点和节点的左子节点都存在就递归访问左子节点
    while (node && node.left != null) {
    node = node.left
    }
    return node.key
    }
    return null
    }

    查找最大值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    var maxNode = function (node) {
    if (node) {
    //当节点和节点的右子节点都存在就递归访问右子节点
    while (node && node.right != null) {
    node = node.right
    }
    return node.key
    }
    return null
    }

    删除节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    //寻找最小的左子节点并返回
    var findMinNode = function (node) {
    if (node) {
    while (node && node.left != null) {
    node = node.left
    }
    return node
    }
    return null
    }
    var removeNode = function (node, key) {
    if (node === null) {
    return null
    }
    //如果删除的值小于节点就递归左子节点
    if (key < node.key) {
    node.left = removeNode(node.left, key)
    return node
    //如果删除的值大于节点就递归右子节点
    } else if (key > node.key) {
    node.right = removeNode(node.right, key)
    } else {
    //如果节点是叶节点就直接删除节点
    if (node.left === null && node.right === null) {
    node = null
    return node
    }
    //如果节点没有左子节点 节点等于右子节点
    if (node.left === null) {
    node = node.right
    return node
    //如果节点没有右子节点 节点等于左子节点
    } else if (node.right === null) {
    node = node.left
    return node
    }
    //如果节点拥有左右子节点就找节点右子节点的最小值
    var aux = findMinNode(node.right)
    node.key = aux.key
    //删除节点右子节点的最小值 避免重复数据
    node.right = removeNode(node.right, aux.key)
    return node
    }
    }

    功能实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    function BinaryTree() {
    var _this = this;
    this.root = null;
    var Node = function (key) {
    this.key = key;
    this.left = null;
    this.right = null;
    }
    this.show = function (key) {
    console.log(key)
    }
    var insertNode = function (node, newNode) {
    if (newNode.key < node.key) {
    if (node.left === null) {
    node.left = newNode
    } else {
    insertNode(node.left, newNode)
    }
    } else {
    if (node.right === null) {
    node.right = newNode
    } else {
    insertNode(node.right, newNode)
    }
    }
    }
    this.show = function (key) {
    console.log(key)
    }
    this.insert = function (key) {
    var newnode = new Node(key)
    if (this.root === null) {
    this.root = newnode
    } else {
    insertNode(this.root, newnode)
    }
    }
    var inOrderTraverseNode = function (node) {
    if (node != null) {
    inOrderTraverseNode(node.left)
    _this.show(node.key)
    inOrderTraverseNode(node.right)
    }
    }
    var preOrderTraverseNode = function (node) {
    if (node != null) {
    _this.show(node.key)
    preOrderTraverseNode(node.left)
    preOrderTraverseNode(node.right)
    }
    }
    var postOrderTraverseNode = function (node) {
    if (node != null) {
    postOrderTraverseNode(node.left)
    postOrderTraverseNode(node.right)
    _this.show(node.key)
    }
    }
    var minNode = function (node) {
    if (node) {
    while (node && node.left != null) {
    node = node.left
    }
    return node.key
    }
    return null
    }
    var maxNode = function (node) {
    if (node) {
    while (node && node.right != null) {
    node = node.right
    }
    return node.key
    }
    return null
    }
    var searchNode = function (node, key) {
    if (node === null) {
    return false
    }
    if (key < node.key) {
    return searchNode(node.left, key)
    } else if (key > node.key) {
    return searchNode(node.right, key)
    } else {
    return true
    }
    }
    var findMinNode = function (node) {
    if (node) {
    while (node && node.left != null) {
    node = node.left
    }
    return node
    }
    return null
    }
    var removeNode = function (node, key) {
    if (node === null) {
    return null
    }
    if (key < node.key) {
    node.left = removeNode(node.left, key)
    return node
    } else if (key > node.key) {
    node.right = removeNode(node.right, key)
    } else {
    if (node.left === null && node.right === null) {
    node = null
    return node
    }
    if (node.left === null) {
    node = node.right
    return node
    } else if (node.right === null) {
    node = node.left
    return node
    }
    var aux = findMinNode(node.right)
    node.key = aux.key
    node.right = removeNode(node.right, aux.key)
    return node
    }
    }
    this.inOrderTraverse = function () {
    inOrderTraverseNode(this.root)
    }
    this.preOrderTraverse = function () {
    preOrderTraverseNode(this.root)
    }
    this.postOrderTraverse = function () {
    postOrderTraverseNode(this.root)
    }
    this.min = function (key) {
    return minNode(this.root)
    }
    this.max = function (key) {
    return maxNode(this.root)
    }
    this.search = function (key) {
    return searchNode(this.root, key)
    }
    this.remove = function (key) {
    removeNode(this.root, key)
    }
    }
    var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]
    var binaryTree = new BinaryTree()
    nodes.forEach(function (key) {
    binaryTree.insert(key)
    })
    binaryTree.inOrderTraverse()//1 3 4 6 7 8 10 13 14
    binaryTree.preOrderTraverse()//8 3 1 6 4 7 10 14 13
    binaryTree.postOrderTraverse()//1 4 7 6 3 13 14 10 8
    var minNumber = binaryTree.min()
    console.log('最小值是'+minNumber)
    var maxNumber = binaryTree.max()
    console.log('最大值是'+maxNumber)
    var searchNumber
    searchNumber=7
    var result1 = binaryTree.search(searchNumber) ? console.log(searchNumber+'存在') : console.log(searchNumber+'不存在')
    searchNumber=12
    var result2 = binaryTree.search(searchNumber) ? console.log(searchNumber+'存在') : console.log(searchNumber+'不存在')
    binaryTree.remove(3)
    console.log(binaryTree)