二叉树顺序存储结构
- 二叉树的顺序结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点直接的逻辑关系
二叉树链式存储结构
二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域
|
1 2 3 4 5 |
typedef struct BiTNode { ElemType data; struct BiTNode * lchild,* rchild; }BiTNode,* BiTree; |
二叉树的创建
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
//按前序输入二叉树中结点的值，#表示空树 void CreateBiTree(BiTree * T) { ElemType ch; scanf("%c",&ch); if(ch == '#') *T = NULL; else { *T = (BiTree)malloc(sizeof(BiTNode)); if(!*T) exit(OVERFLOW); (*T)->data = ch;//生成根结点 CreateBiTree(&(*T)->lchild);//构造左子树 CreateBiTree(&(*T)->rchild);//构造右子树 } } |
二叉树的遍历
二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的结点，使得每个结点被访问一次且仅被访问一次
前序遍历
根左右
|
1 2 3 4 5 6 7 8 |
void PreOrderTraverse(BiTree T) { if(T == NULL) return; printf("%c",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } |
中序遍历
左根右
|
1 2 3 4 5 6 7 8 |
void InOrderTraverse(BiTree T) { if(T == NULL) return; InOrderTraverse(T->lchild); printf("%c",T->data); InOrderTraverse(T->rchild); } |
后序遍历
左右根
|
1 2 3 4 5 6 7 8 |
void PostOrderTraverse(BiTree T) { if(T == NULL) return; PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%c",T->data); } |
层序遍历
从根结点开始，从上往下逐层遍历，对于每一层，按从左到右的顺序对结点逐个访问
推导遍历结果
示例一
已知一棵二叉树的前序遍历结果是ABCDEF，中序遍历结果是CBAEDF，问后序遍历结果是啥
分析如下：
- 根据前序遍历的特点，可得出，A为根结点
- 已知A为根结点的情况，结合中序遍历的特点，可知，CB为该二叉树的左子树，EDF为该二叉树的右子树
- 左子树CB，结合该二叉树的前序遍历顺序为ABC，可推断，B为左子树的根，C为B的左孩子，B没有右孩子
- 右子树EDF，结合该二叉树的前序遍历顺序为CBADEF，则右子树EDF的根为D，E为D的左孩子，F为D的右孩子
根据上述推导，可得出该二叉树为：
然后根据二叉树得后序遍历特点，可得出后序遍历结果为：CBEFDA
示例二
已知一棵二叉树的中序遍历结果是ABCDEFG，后序遍历结果是BDCAFGE，问前序遍历结果是啥
分析如下：
- 根据后序遍历的特点，可得出，E为根结点
- 已知E为根结点的情况，结合中序遍历的特点，可知，ABCD为该二叉树的左子树，FG为该二叉树的右子树
- 左子树ABCD，结合该二叉树的后序遍历顺序为BDCA，可推断，A为左子树的根，再结合中序遍历得顺序为ABCD，那么BCD就是A的右孩子，A没有左孩子，BCD作为右孩子，结合中序遍历得情况，可知，C为根，B为C的左孩子，D为C的右孩子
- 右子树FG，结合该二叉树的后序遍历顺序为BDCAFGE，其中，右子树FG的根为G，再结合它们的中序遍历情况，可得知，F为G的左孩子，F没有右孩子
根据上述推导，可得出该二叉树为：
然后根据二叉树得前序遍历特点，可得出后序遍历结果为：EACBDGF
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ 栈队列相关09/18
- ♥ 大话数据结构_线索二叉树11/04
- ♥ 大话数据结构_栈11/01
- ♥ 大话数据结构_算法相关&&AVL&&B树相关02/20
- ♥ Dump分析：空指针访问二，重复释放堆内存二03/30
- ♥ 大话数据结构_基础概念11/01
热评文章
- 大话数据结构_树森林二叉树转换与遍历 0
- 红黑树 0
- 大话数据结构_赫夫曼树与应用 0
- 大话数据结构_线索二叉树 0
- 大话数据结构_图 0
- 大话数据结构_二叉树 0