Question

二叉树_链式存储

Answer 1

二叉链：数据域（data）、左子结点域（lchild）、右子节点域（rchild）
定义：

求指定节点的左子节点地址：

求指定节点的右子节点地址：

二叉树的遍历：
定义： 按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次；
用途： 它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心；

遍历规则：
1、先序遍历(DLR)： 头 -> 左 -> 右
2、中序遍历(LDR)： 左 -> 头 -> 右
3、后序遍历(LRD)： 左 -> 右 -> 头
先中后都是对于根结点而言。

二叉树遍历的递归实现：

访问方法：

先序遍历：

中序遍历：

后序遍历：

插一嘴：递归实现的思路清晰，易于理解，但是执行效率很低。非递归实现效率高些。

二叉树遍历的非递归实现：
先序遍历：

中序遍历：

后序遍历：好难-.-||略

利用“扩展先序遍历序列” 创建二叉树二叉链表：
1、若输入的字符是 '#'，则建立空树；
2、否则建立根结点，接着递归建立左子树，然后递归建立右子树。