二叉树

二叉树的定义

typedef struct BiTNode{
  ElemType data;                  // 数据域
  struct BiTNode *lchild,*rchild; // 左、右孩子指针
}BiTNode,*BiTree;

二叉树的遍历

先序遍历

• 递归

void preOrder(BiTree T){
  if (T!=NULL)
  {
    visit(T);            // 访问根节点
    preOrder(T->lchild); // 递归遍历左子树
    preOrder(T->rchild); // 递归遍历右子树
  }
}

• 非递归

void PreOrder(BiTree T){
  InitStack(S);
  BiTree p=T;
  while(P||!IsEmpty(S)){
    if(p){
      visit(p);
      Push(S,p);
      p=p->lchild;
    }
    else{
      Pop(S,p);
      p=p->rchild;
    }
  }
}

中序遍历

• 递归

void InOrder(BiTree T){
  if (T!=NULL)
  {
    InOrder(T->lchild); // 递归遍历左子树
    visit(T);            // 访问根节点
    InOrder(T->rchild); // 递归遍历右子树
  }
}

• 非递归

void InOrder(BiTree T){
  InitStack(S);
  BiTree p=T;
  while(P||!IsEmpty(S)){
    if(p){
      Push(S,p);
      p=p->lchild;
    }
    else{
      Pop(S,p);
      visit(p);
      p=p->rchild;
    }
  }
}

后序遍历

• 递归

void PostOrder(BiTree T){
  if (T!=NULL)
  {
    PostOrder(T->lchild); // 递归遍历左子树
    PostOrder(T->rchild); // 递归遍历右子树
    visit(T);             // 访问根节点
  }
}

• 非递归

void PostOrder(BiTree T){
  InitStack(S);
  BiTree p = T;
  BiTree r = NULL;
  while(p||!isEmpty(S)){
    if(p){
      push(S,p);
      p=p->lchild;      // 转向左节点
    }
    else{
      GetTop(S,p);
      if(p->rchild && p->rchild!=r)
        p = p->rchild;  // 若右节点存在，且未访问过，则转向右节点
      else{
        pop(S,p);       // 将结点弹出
        visit(p);       // 访问该结点
        r=p;            // 记录最近访问过的结点，防止重复访问右节点
        p=NULL;         // 结点访问后，重置p指针
      }
    }
  }
}

层序遍历

二叉树的构造

中序+先序

中序+后序

中序+层序

二叉树的其他应用

求结点的双亲

求结点的孩子结点

求二叉树的深度

求二叉树的叶子节点个数

判断两棵二叉树是否相等

判断二叉树是否为完全二叉树

线索二叉树

#