树与二叉树（一）
结构
一、树的概念
N=0的树称为空树。
树的定义是递归的，本身是一种递归的数据结构，作为一种逻辑结构来说，本身也是分层的结构。
-
节点的深度、高度
节点的深度是从树根往下递增的。
节点的高度是从下往上累加的。
树的高度就是深度，是树中节点的最大层次。
路径长度是节点经过边的数量。
森林是m(m>=0)棵不相交的树的集合。
-
树的性质：
- 树的度等于所有节点的度数+1，也就是总分支数+1。
二、二叉树
1.满二叉树
树高为h，总节点数为2^h-1的二叉树称为满二叉树。
满二叉树中，节点i的左孩子为2i，右孩子为2i+1。
2.完全二叉树
- 一棵高为h的二叉树，当且仅当每个节点都与高为h的满二叉树一一对应，称为完全二叉树。
3.二叉排序树（BST/二叉查找树）
- 左子树所有节点都小于根节点，右子树所有节点都大于根节点。
4.平衡二叉树
- 树上任意节点的左右子树高度差不大于1。
5.存储结构
顺序存储，利用数组，自上而下，自左而右的存储树节点。空间利用率较低，一般用链式。
链式存储，二叉链表包含左指针域，右指针域。
三、二叉树的遍历和线索二叉树
1.先序遍历
-
如果根节点为空，退出，否则：
访问根节点
先序遍历左子树
先序遍历右子树
void PreOrder(root){
if(root!=null){
visit(root);
PreOrder(root.left);
PreOrder(root.right);
}
}
2.中序遍历
-
如果根节点为空，退出，否则：
中序遍历左子树
访问根节点
中序遍历右子树
void InOrder(root){
if(root!=null){
InOrder(root.left);
visit(root);
InOrder(root.right);
}
}
3.后序遍历
-
如果根节点为空，退出，否则：
后序遍历左子树
后序遍历右子树
访问根节点
void PostOrder(root){
if(root!=null){
PostOrder(root.left);
PostOrder(root.right);
visit(root);
}
}
以上三种遍历的时间复杂度都是O(n)，因为每个节点都只访问过一次。
4.非递归中序遍历
- 先扫描根节点的所有左节点，找到后一一入栈，然后出栈一个节点（该节点没有左孩子或者左孩子已经访问过），访问该节点，接着扫描该节点的右节点将其进栈。再扫描该右节点的所有左节点依次进栈，直到栈空为止。
void InOrder(root){
TreeNode p=root;//p是遍历指针
while(p||!stack.isEmpty()){//p非空或者栈中还有元素就循环
if(p){
stack.push(p);
p=p.leaf;
}else{
TreeNode q=stack.pop();
visit(q);
p=p.right;
}
}
}
5.层次遍历
- 借助队列，先将根节点入队，然后出队访问该节点，接着将左右节点都入队，然后出队一个节点，访问，继续如上操作。
void LevelOrder(root){
queue.offer(root);
while(!queue.isEmpty()){
TreeNode p=queue.poll();
visit(p);
if(root.left!=null)
queue.offer(root.left);
if(root.right!=null)
queue.offer(root.right);
}
}
6.遍历序列构造二叉树
-
先序遍历和中序遍历可以唯一确定一棵二叉树。
- 先序遍历的第一个节点是根节点，中序遍历中根节点将左右子树分成两部分，第一部分是左子树的中序遍历，第二部分是右子树的中序遍历。根据两部分去先序遍历中找到对应的左右子树的先序遍历，依次循环下去。
-
后序遍历和中序遍历可以唯一确定一棵二叉树。
- 同先序遍历和中序遍历的原理，后序遍历根节点在尾巴。
-
层次遍历和中序遍历可以确定唯一一棵二叉树。
- 层次遍历第一个节点是根节点，可以将中序遍历划分成左右子树的中序遍历。第二个节点是左子树的根节点，第三个节点是右子树的根节点，根据上面方法能不断划分，最后确定二叉树。
