首页 > 代码库 > 碎碎念--数据结构

碎碎念--数据结构

1.

图的广度优先搜索实现借助于队列结构;

图的深度优先搜索除了递归方式外,还可借助堆栈、迭代方式实现。


2.

线性表的链式存储结构所需的存储空间一般要多于顺序存储结构。因为顺序存储结构只要存元素的内容,链式存储还需要多一块区域来存储相邻节点的地址。


3.

根结点的层数为0,根的孩子层数为1

树的深度:结点层数最大值。

树的高度:最大层数+1


4.树转换为二叉树:

          加边--删边--调整






5.森林转换为二叉树

(1)将森林中的每棵树转换成相应的二叉树。

(2)第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子,当所有二叉树连在一起后,所得到的二叉树就是由森林转换得到的二叉树。

 


6.二叉树还原为树或森林

(1)若某结点是其双亲的左孩子,则把该结点的右孩子、 右孩子的右孩子……都与该结点的双亲结点用线连起来。

(2)删掉原二叉树中所有双亲结点与右孩子结点的连线。

(3) 整理由(1)、(2)两步所得到的树或森林,使之结构层次分明。 










碎碎念--数据结构