引入
前面,我们说过,二叉树的遍历方法,以及如何使用代码创建二叉树并将三种遍历顺序都输出出来。如果你还对单链表有印象,我们会发现上节我们树的创建过程其实就是根结点指向左右子树,很像单链表指向唯一后继,对不对?还记得为什么我们要使用双向链表嘛?因为双向链表在找寻唯一前驱的时候方便。因此,二叉树也遇到了相同的问题,左右子树不知道自己的双亲是谁,我们该怎么解决呢?
问题
现在的二叉树
- 一个结点下,数据域和指针域
- 数据域,存放数据
- 指针域,指向该结点下的左右子树
问题一
如果我要找这个结点的双亲该怎么办呢?
- 麻烦了!我们要重新遍历这个棵二叉树
- 直到遇到这个结点,然后记录它得双亲