文章来源https://segmentfault.com/a/1190000000740261
基本性质
- 每个节点有三个指针，分别指向父母、左孩子、右孩子、
- 第i层至多有2i-1个结点
- 深度为k的二叉树最多有2i-1个结点
顺序/链式
顺序存储，是用一维数组存储二叉树中的各个结点，而且结点的存储位置能体现结点之间的逻辑关系。
国际标准都使用链式结构
二叉树的遍历
- 前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。、
- 中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。
- 后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。
1/3 前序遍历
遍历的顺序为：A B D H I E J C F K G
//先序遍历 function preOrder(node){ if(!node == null){ putstr(node.show()+ " "); preOrder(node.left); preOrder(node.right); } }
2/3 中序遍历
遍历的顺序为：H D I B E J A F K C G
//使用递归方式实现中序遍历 function inOrder(node){ if(!(node == null)){ inOrder(node.left);//先访问左子树 putstr(node.show()+ " ");//再访问根节点 inOrder(node.right);//最后访问右子树 } }
3/3 后序遍历
遍历的顺序为：H I D J E B K F G C A
//后序遍历 function postOrder(node){ if(!node == null){ postOrder(node.left); postOrder(node.right); putStr(node.show()+ " "); } }
