Please enable JavaScript.
Coggle requires JavaScript to display documents.
树与二叉树 - Coggle Diagram
树与二叉树
树、森林
树的要点:结点可分为m个互不相交的有限集;
树是一种递归的数据结构;
具有n个结点的m叉树的最小高度为logm(n(m-1)+1)向上取整;
高度为h的m叉树至多有(m的h次方-1)/(m-1);
树的存储结构
双亲表示法:其中根节点的伪指针域为-1,这种结构可以很快的找到每个节点的双亲,但求孩子结点必须遍历整个结构
孩子表示法:寻找双亲需要遍历整个结构
孩子兄弟表示法:又称二叉树表示法,
优点:方便实现树转化二叉树的操作,找结点的孩子
缺点:当前结点查找双亲结点比较麻烦,若为每个节点增设一个parent域指向其父结点,则查找父亲的结点也方便。
给定一棵树,可以找到唯一的一棵二叉树与之对应。物理结构来看它们的二叉链表是相同的;
对应的二叉树,没有右孩子
遍历对应关系:
树、森林、二叉树
先根、先序、线序
后根、中序、中序
二叉树
哈夫曼树
带权路径最小的二叉树称为哈夫曼树也称最优二叉树;
若没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码
左右孩子是任意的,所以构造出的哈夫曼树并不唯一,但哈夫曼树的带权路径长度WPL相同且最优
完全二叉树的高度:h=log2n向下取整+1
含有n个结点的二叉链表中,含有n+1个空链域
线索二叉树是为了
加快查找结点前驱和后继
无左子树,令lchild指向其前驱节点
无右子树,令rchild指向其后继结点
这种节点构成的二叉链表作为二叉树的存储结构,成为线索链表,其中指向结点前驱和后继的指针成为线索,加上线索的二叉树称为线索二叉树。
在后继线索二叉树中找结点的后继较为复杂,需要知道结点的双亲,即采用代标志的三叉链表作为存储结构。