树的概念

数据结构与算法 · 2023-02-18

树有节点,父子关系,叶,根,深度,高度,度

         1
        / \
      2     3
     /  \    \
    4     5   6

上述实例中:
1 是根, 高度为2,深度为0 ,度为2
2,3 是节点,高度为1,深度为1 ,度分别为2,1
4,5,6 是叶, 高度为0,深度为2

1是2,3的父节点
同理2,3是1的子节点

深度有两种含义,上面的是定义1,按照层数划分
定义2,按照根节点到该点的最短路径的节点数为深度,如根节点深度为1.

{dotted startColor="#ff6c6c" endColor="#1989fa"/}

二叉树

分为:以下三种
1.空二叉树,2.左二叉树,3.右二叉树,4.完全二叉树

    1.      0

------------


    2.      0
           /
          1
 

------------

         
    3.      0
              \
                1

------------


    4.       0
            / \
          1     2
                

完全二叉树可以用一个数组表述
由于完全二叉树,从上到下,从左到右增大/减小的性质
可以利用数组作为存储树的容器
其中每一个节点的父节点是 i/2 向下取整(i 是节点的总个数)

            1
          /    \
        2        3
      /   \     /  \
    4      5   6    7

二叉树有最大二叉树,最小二叉树(主要根据根树的具体数据的排列来定义)
二叉树对于,增,删,改,查比较友好,尤其是查,每次只需查找一半,极大的提高了查询速度

  1. admin (作者)  2023-02-18

    {!{data:image/webp;base64,UklGRpAJAABXRUJQVlA4WAoAAAAwAAAAxAMAKwEASUNDUMgBAAAAAAHIAAAAAAQwAABtbnRyUkdCIFhZWiAAAAAAAAAAAAAAAABhY3NwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAQAA9tYAAQAAAADTLQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAlkZXNjAAAA8AAAACRyWFlaAAABFAAAABRnWFlaAAABKAAAABRiWFlaAAABPAAAABR3dHB0AAABUAAAABRyVFJDAAABZAAAAChnVFJDAAABZAAAAChiVFJDAAABZAAAAChjcHJ0AAABjAAAADxtbHVjAAAAAAAAAAEAAAAMZW5VUwAAAAgAAAAcAHMAUgBHAEJYWVogAAAAAAAAb6IAADj1AAADkFhZWiAAAAAAAABimQAAt4UAABjaWFlaIAAAAAAAACSgAAAPhAAAts9YWVogAAAAAAAA9tYAAQAAAADTLXBhcmEAAAAAAAQAAAACZmYAAPKnAAANWQAAE9AAAApbAAAAAAAAAABtbHVjAAAAAAAAAAEAAAAMZW5VUwAAACAAAAAcAEcAbwBvAGcAbABlACAASQBuAGMALgAgADIAMAAxADZBTFBIYgUAAAGgRdu2KUk6bdu2bXdHthGj+5Vt27Zt23Z12U5bhShH2UZif5wbkZEv2rvHuBExAWL9b/1v/W/9b/1v/W/9b/1v/f+P5d0l3iYwTwYwjL6+2A8g6wHmeqHosiQYC3DW/RF1R205gyAj2OrBT0qvXZOBvCYJUT88ctaWIwjl1XHC0jcNmepDiI/9/oiwdO0LCOnF5PVzPxOWfmziCuTdv7hLqXduFqJuchXB71q9bMa3Dwlbl0fgSwkrnTduF8Z+LBIBt35+k7B2k6sI6BPeLg+zf1EZ4e2GCPi88PZN6xAwRXi7SDaM+xZVFt6uDrNfmLs3zFEvENfd42C82kyI+8ujMKa/LcRdJgvG7cLcj52HcZFQ92zoKzWEuttDH/tAqLs89KmXhbt3GEoLdxeCHiXkvVqdEvL2Qldlr2gVJ+RdHroqe2WqbULejaFbktcvWerCTeSVBl1FuLsz9ALh7hLQ5x7grl9grCvcvduwQ7i7IHSGkPcWdVLIuyF0VfJ684xKEu5+4wz0UPLaC2MEdzkwJgl3R6vscULep9UgIe/WAJBzPXk9dkZNF/KeDV2RvNpD7xbuLg995mXy8hlKC3cXhB4l5B2rTgl5e6Grsle0Shb2Pqu6sdevAJBzPXtFq6nC3mdVG/aqDAA517NXhloi5P0qdEf26mW4g738aqyQ92/QHvZaq+KEvXeqgex102V1D3t9AwBRwt6bVW/6Oqjasde90A+w12fqoLB3JbWCvgaq/vS1WzWnr5OqDnt5ASD3WvYarSYJex9WBdirAQCcuS1A4fhdG4oyVoyaLuYJ0D7C2q06Gd6KhnnruMrXklWq8qjeCDq32a1UFRng7nHI65km94k8tnp3RlWGOqFajl1wFCE8vWZFLgBk8lM56CsIfKFyk6xAQb5MTztVDgLuLyMij0+bG5eXcuxUDkFfrSGB3xsRnJeddgV14AMJ+r3ZwfjJqQmCbSJ5/nbCqp6LUhQac1OMOrtbpUiIHQPepKbdqvcDTVduqCwh7204Rk3JyiP5PEmhHTP5lZNfckXhM2LyKW++1TUceYSXYpUn36Sjwj5eSnSJLFKoR0t+5bjgyVMKb7KST3ldIK0Nh1kpVnncIOMVFpPSWvfIFYWZ7FXUgBWUlOgiKWLA+aKE5FeOS6SIAThfjI58yusWKWIC0tkoVnlcI3EB8DIZJbqs2NUADhn5leMeeXneXsMxMvIpr4tEZL1CIhdtVR53OQaUpiK/ctwlrQ05g5jIp7wukyEKSCWiWOVxmxww4HseSgyPYlmGwjzkV47rpNAF5eEhn/K6T/xqNw/FKk8YLFeoRkOJ4eIYFtCQXzlhIN1Uzg0s5FPecJAzAPADC8UqT1gcVYVZKDF8DiiHhfwqNny8LLRcISMcjiiHhQoY8HwY+JSXhaSSweu+D88pDw1JpvK47ucL0A4P7VZdXBcDYwQPLVdZt7lttyFJeLilQi237VJLhYmz1Ui3nVQOFV1QuQPd1RC6FBUdV8AOFz29DsbHqWidCQcr3+iS2jD7hIqLXTEBOTsiIzctqHxjPvWD+ZiQ8ctLdpsCZk/NjyeXwBz1AhuJSLPggK2h+8kPY1YzoeQmWcGhV6gaZcOY+pOQ8hOL9wSF8Ssj03bGTqt8fVCvLIB5mDDztzN2REbG7TEEztkyu32vxcN6Lhq/OAUBGwhD/x5cKE//Ihx9OX+m3SEkXSY/5n8mPP3A/LkjVkRu3Z++/XIeTlUUzr616sxp7XstHtZr8fjlmxvcL9b/1v/W/9b/1v/W/9b/1v/W/9b/1v/W/9b/1v/W/9b/1v/W/9b/1v/W/9b/1v/W/9b/1v//ZwpWUDggOAIAAJBBAJ0BKsUDLAE/cbjZZbSvK6cgCAKQLglpbuF3YRtACewD32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ99snIe+2TkPfbJyHvtk5D32ych77ZOQ9YAAP7/rR4AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA=}!}

Theme Jasmine by Kent Liao