树和二叉树（一）

一、树的概念

• 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.遍历序列构造二叉树

• 先序遍历和中序遍历可以唯一确定一棵二叉树。
  • 先序遍历的第一个节点是根节点，中序遍历中根节点将左右子树分成两部分，第一部分是左子树的中序遍历，第二部分是右子树的中序遍历。根据两部分去先序遍历中找到对应的左右子树的先序遍历，依次循环下去。
• 后序遍历和中序遍历可以唯一确定一棵二叉树。
  • 同先序遍历和中序遍历的原理，后序遍历根节点在尾巴。
• 层次遍历和中序遍历可以确定唯一一棵二叉树。
  • 层次遍历第一个节点是根节点，可以将中序遍历划分成左右子树的中序遍历。第二个节点是左子树的根节点，第三个节点是右子树的根节点，根据上面方法能不断划分，最后确定二叉树。

树和二叉树（一）

原文：https://www.cnblogs.com/k-will/p/12733064.html