二叉树

二叉树

性质1 在二叉树的第i层至多有\(2^{i-1}\)个结点(i$\geq$1)

性质2 深度为K的二叉树至多有\(2^k-1\)个节点 (k$\geq$1)

二叉树的遍历

前序遍历

中序遍历

后序遍历

线索二叉树

一棵结点数目为n的二叉树,采用二叉链表的形式存储。对于每个结点均有指向左右孩子的两个指针域,而结点为n的二叉树一共有n-1条有效分支路径。那么,则二叉链表中存在2n-(n-1)=n+1个空指针域。那么,这些空指针造成了空间浪费。

二叉树

线索化

若结点的左子树为空,则该结点的左孩子指针指向其前驱结点。

若结点的右子树为空,则该结点的右孩子指针指向其后继结点。

二叉树

​ 线索二叉树

线索化带来新问题

ltag为0时,指向左孩子,为1时指向前驱

rtag为0时,指向右孩子,为1时指向后继

添加ltag和rtag属性后的结点结构如下:

二叉树

​ 添加标志线索二叉树结点

线索二叉树转变二叉树

二叉树

​ 添加标志位的线索二叉树

二叉排序树

构造一个有n个结点的二叉排序树,在最坏的情况下,深度不超过n。

现有序列:61 87 59 47 35 73 51 98 37 93

构造过程如下:
1)索引 i = 0,A[i] = 61,结点61作为根结点,如图2.1:

二叉树

2)索引 i = 1,A[1] = 87, 87 > 61,且结点61右孩子为空,故81为61结点的右孩子,如图2.2:

二叉树

3)索引 i = 2,A[i] = 59,59 <
61,且结点61左孩子为空,故59为61结点的左孩子,如图2.3:

二叉树

4)索引 i = 3,A[3] = 47,47 < 59,且结点59左孩子为空,故47为59结点的左孩子,如图2.4:

二叉树

5)索引 i = 4,A[4] = 35,35 < 47,且结点47左孩子为空,故35为47结点的左孩子,如图2.5:

二叉树

采用同样规则遍历整个数组得到如图2.6所示的一棵排序二叉树。

二叉树

上一篇:Win11系统电脑安装了IE11无法打开无反应怎么办?


下一篇:20191215从九溪到老和山