二叉树的链式存储

若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和右孩子的两个指 针。在这种存储结构中,n个结点的二叉树共有________个指针域,其中有________个指针域是存放了地址,有________________个指针是空指针。

因为有n个节点,每个节点都存了一个lchild,一个rchild,所以共2n个指针域。
因为除了根节点,其他所有的节点都存在自己的父节点,而父节点肯定存在指向其孩子的指针,所以有n-1个存了地址(根节点没有父节点,所以-1),因为总数是2n个所以NULL的就是2n-(n-1)=n+1个

其实就是计算树的边数,每条边是一个指针。

原文地址:https://www.cnblogs.com/fthjane/p/4745603.html