数据结构复习之二叉树.md

title: 数据结构复习之二叉树

layout: post

date: 2017-03-21 21:48:01

categories: 算法与数据结构

tags: [二叉树]

description: 二叉树是数据结构中很基础也很重要的一种，在今天参加的美团点评的笔试中也遇到了相关的考题。不出意外，在之后的其他测试中也还会有遇到的可能，因此决定重新复习一下，也作为记录

---

几种特别的二叉树

1. 完全二叉树

   只有最下面两层结点可以只拥有一个子结点或没有子结点，且最下面一层结点都集中在该层最左边

2. 满二叉树

   除了叶子结点外每一个结点都有左右子树，且叶结点都处在最底层的二叉树。

3. 真二叉树

   不含一度结点的二叉树

4. huffman 树

   一定是最优编码树之一，一定是真二叉树。常用于压缩算法。

二叉树的遍历

二叉树遍历有几种方式，以上图为例说明

	前序遍历	中序遍历	后序遍历
规则	根节点->左子树->右子树	左子树->根节点->右子树	左子树->右子树->根节点
顺序	A->B->D->E->F->C->G	D->B->E->F->A->C->G	D->F->E->B->G->C->A

除此之外还有层次遍历，即从最高层向下，从左向右遍历，对于上图，顺序为A->B->C->D->E->G->F

遍历解法

递归法

void Traverse(BinNode* x){
  if(x==NULL) return;
  visit(x);				//(1)
  preTraverse(x->lc);	//(2)
  preTraverse(x->rc);	//(3)
}

​ 顺序(1)(2)(3)即为先序遍历，(2)(1)(3)即为中序遍历，(2)(3)(1)即为后序遍历

其他解法

​ 先序遍历可以用栈改为迭代解法，沿左支深入，访问结点时将右孩子暂存入栈中。

void visitAlongLeft(BinNode* x,Stack<BinNode*> &S){
  while(x!=NULL){
    visit(x->data);
    S.push(x->rc);
    x=x->lc;
  }
}
void traverse(BinNode* root){
  Stack<BinNode*> S;
  BinNode* p=root;
  while(true){
    visitAlongLeft(p,S);
    if(S.empty()) break;
    p=S.pop();
  }
}

​ 层次遍历可以用BFS，可以用queue实现。初始化将root放入queue，当queue不为空，则进行以下操作：弹出第一个结点，访问，若左结点不为空，入队，若右结点不为空，入队。

一个关于二叉树的试题

这个题也是今晚笔试遇到的题目::>_<::并没来得及做完，现在在这里写一下。

题目 ：在不使用额外辅助数据结构存储结点情况下求二叉树中两个结点的最低公共祖先。

解题思路1 ：二叉树遍历的题目不是递归就是迭代，迭代解法一般需要用stack或者queue来辅助，本题不允许使用额外数据结构存储子结点，则考虑用递归解法。

代码 ：

bool findNode(BinNode* root,BinNode* node){
  if(root==NULL||node==NULL) return false;
  if(root==node) return true;
  bool found=findNode(root->lc,node);
  if(!found) found=findNode(root->rc,node);
  return found;
}
BinNode* findYoungestCommonAncestor(BinNode* root,BinNode* a,BinNode* b){
  if(findNode(root->lc,a)){
    if(findNode(root->rc,b))
      return root;
    else 
      return findYoungestCommonAncestor(root->lc,a,b);
  }else{
    if(findNode(root->lc,b))
      return root;
    else
      return findYoungestCommonAncestor(root->rc,a,b);
  }
}