二叉树小记

树

树的储存结构

树的结点

• 结点

  • 使用树结构存储的每一个数据元素

• 根节点、叶子结点

  • 没有父结点的一个结点为根节点
  • 没有子结点的结点为叶子结点

• 父结点、子结点与兄弟结点

  • 一个含有子结点称为为其子结点的父结点
  • 其上有根节点的结点为子结点
  • 具有相同父结点的结点互称为兄弟结点

注：树的子树是不相交的；除了根节点外，每个结点有且仅有一个父结点。

结点的度与层

• 度

  • 一个结点拥有的子树数称为结点的度
  • 树的度即为根节点的度

• 层

  • 从一棵树的树根开始，树根所在层为第一层，根的子结点所在的层为第二层

有序树与无序树与森林

• 有序树

  • 结点的子树从左到右的位置有规定

• 无序树

  • 结点的子树从左到右的位置无规定

• 森林

  • 互不相交的树组成的集合

二叉树

• 概念

  • 本身是有序树，且各个结点的度不大于2的树

• 性质

  • 第i层最多有2^(i-1)个结点
  • 深度为k的二叉树，最多有2^k - 1个结点
  • 在二叉树中设叶节点数为n0，度为1的节点数为n1,度为2的节点数为n2
    • 则有n0 = n2 + 1

  设总结点数为n n = n0 + n1 + n2
  从分支角度又可以写为 n = n1 + 2 * n2 + 1
  两式做等即可得到
  

• 树与二叉树

  • 树不是特殊的二叉树
  • 树中结点的度数没有限制，而二叉树结点的最大度数为2；
  • 树的结点无左、右之分，而二叉树的结点有左、右之分
  • 二叉树可以为空，树不能为空。

二叉树的分类

• 满二叉树

  • 树中除了叶子结点，每个结点的度都为 2的二叉树

• 完全二叉树

  • 除去最后一层节点外为满二叉树，且最后一层的结点依次从左到右分布的二叉树、
    

二叉树的存储结构与遍历

• 存储结构

  typedef struct BiTNode
  {
      int date; //存储数据
      struct BiTNode *lchild, *rchild; //左右子结点
  }BiTNode, *BiTree;
  

• 先序遍历： 先根 再左 再右

  void PreorderTraversal(BiTree BT )
  {
      if(BT == NULL)return ;
      printf("%c ", BT->date);
      PreorderTraversal(BT->lchild);
      PreorderTraversal(BT->rchild);
  }
  

• 中序遍历： 先左 再根 再右

  //中序遍历
  void InorderTraversal(BiTree BT )
  {
      if(BT == NULL)return ;
      InorderTraversal(BT->lchild);
      printf("%c ", BT->date);
      InorderTraversal(BT->lchild);
  }
  

• 后序遍历： 先左 再右 再根

  //后序遍历
  void PostorderTraversal(BinTree BT)
  {
      if(BT == NULL)return;
      PostorderTraversal(BT->lchild);
      PostorderTraversal(BT->rchild);
      printf("%c ", BT->Data);
  }
  

先序遍历为：A B D E G C F
中序遍历为：D B G E A C F
后序遍历为：D G E B F C A

题一

#include<bits/stdc++.h>
#define len size()

using namespace std;

int n, m, k, t;

string a, b;

void dfs(string mid, string af)
{
    if(!mid.len || !af.len) return;
    char root;
    root = af[af.len - 1];
    cout << root ;
    int k = mid.find(root);
    dfs(mid.substr(0, k), af.substr(0, k));
    dfs(mid.substr(k+1), af.substr(k, mid.len - k - 1));
}

int main()
{
    cin >> a >> b;
    dfs(a, b);
    return 0;
}