二叉树用php怎么存储,小蚂蚁学*数据结构(17)??树、二叉树性质、储存方式...

发布于:2021-10-20 17:32:10


是一类非线性数据结构,是以分支关系定义的层次结构。


特点:


至少有一个节点??根,只有根的树成为最小树


树中各子树是互不相交的集合


术语(略)


二叉树


特点:


每个节点最多有二颗子树


子树有左右之分,而且不能任意颠倒


性质:


1,在二叉树的第i层至多有2^(i-1)个节点(i >=1)


2,深度为k的二叉树至多有2^k - 1个节点(k>=1)


3,对任何一颗二叉树T,如果其终端节点数为n0,度为2的节点数为n2,则n0 = n2 + 1(书上有一段神奇的推导过程)


满二叉树:


看着整个轮廓是个完整的三角形的树就是满二叉树。(自己定义的)


完全二叉树:


除了最后一行,上面是个满二叉树,最后一行依次排列。(也是自己定义的)


4,具有n个节点的完全二叉树的深度为 以2为底n的对数 + 1


5,如果对一颗有n个节点的完全二叉树的节点按层序编号,则对任一节点i(1 <= i <= n),有:


1)如果i=1,节点i就是二叉树的根,没有父节点;如果i>1,则其双亲是 i/2,向下取整。


2)如果2i>n,这节点i无左孩子。如果2i<=n,则其左孩子就是2i


3)如果2i+1>n,这节点i无右孩子。如果2i+1<=n,则其右孩子就是2i+1


二叉树的存储结构


顺序存储结构


特点:


节点间关系蕴含在其存储位置中。


浪费空间,适于存储满二叉树和完全二叉树。


很少用这种顺序存储结构,1,浪费空间,2,插入删除很费劲儿,时间复杂度高。


链式存储结构


二叉链表 : 左孩子指针、右孩子指针、数据域


三叉链表 : 比上面多了一个 父节点指针


总结:


在二叉链表中,查找节点都要从根节点开始进行查找,查找的时间复杂度是节点的个数。而在三叉链表中查找节点实现就比较容易些,因为针对每个节点都可以进行上行查找或者下行查找。







相关资源:emoji-aes:using使用AES使用表情符号加密消息-源码

相关推荐

最新更新

猜你喜欢