Ayas_Lan's Blog
Go back

树，二叉树和森林

Edit page

与树有关的概念

树的存储结构：

子女链表表示法：
一个结点用两个部分表示，数据部分存放结点的数据，指针部分存放指向子节点的指针
双亲表示法(顺序存储):
每个结点有两部分，其中parent域存放其双亲结点位置的指针。

树的线性表示：

树的层数表示：

按前序写出树中的全部结点，并在结点前带上结点的层号。利用()组合起来。
即可表示成：
(0, k0), (1, k1), (2, k2), (2, k3), (1, k4), (1, k5), (2, k6), (3, k7)

广义表表示法：

将根节点表示为广义表的表头。
就可以表示为：
k0(k1(k2, k3), k4, k5(k6(k7)))

树的遍历：

定义：按一定顺序访问树中的每一个结点，同时每个结点只能被访问一次。
主要包括：前序遍历，后序遍历，层次遍历。

具体实现：

m次树前序遍历的递归实现：

void preorder(node<type> *t){
  int m = MAXN;
  if(t != null){
     cout << t->data <<endl;
     for(int i = 0; i < m; ++i) preorder(t->child[i]);
  }
}

m次树前序遍历的非递归实现：

void s_preorder(node<type> *t, int m){
  stack <node<type>*>s(100);
  if(t == null) return;
  s.push(t);
  while(!s.isEmpty()){
     s.pop(&t);
     cout << t->data << endl;
     //核心时逆序入栈，保证出栈顺序为前向遍历
     for(int i = m - 1; i >= 0; --i){
        if(t->child[i] != null) s.push(t->child[i]);
     }
  }
}

树的层次遍历实现：

void levorder(node<type> *t, int m){
  node <type>*p;
  queue<node <type>*> q;
  q.enqueue<t>;
  while(!q.isEmpty()){
    q.dequeue(&p);
    cout <<p->data<<endl;
    for(int i = 0; i < m; ++i){
      if(p->child[i] != null) q.enqueue(p->child[i]);
    }
  }
}

二叉树：

二叉树的性质：

特殊类型：

满二叉树：

即每一层的结点都达到了最大个数。

完全二叉树：

除最后一层外，每一层结点都达到了最大个数。最后一层结点均靠左。

将任意次树转化为二叉树：

将具有m个子节点的结点k转换为以作为结点k的左子节点，且作为的右子节点。
(左孩子，右兄弟法)
树的前序遍历与对应二叉树的前序遍历结果相同；
树的后序遍历与对应二叉树的中序遍历的结果相同。

二叉树转化为森林：

需要先遵从“左孩子右兄弟”将普通树转化为二叉树，再将根连接在一起。

森林转化为二叉树：

设T = ()是由m棵树构成的森林，设对应的二叉树为.
则有：
的根节点即是的根节点。的左子树是的根节点的子树，的右子树是.
[注意前提是先将树转化为对应的二叉树]

struct TreeNode{
  int data;
  vector<TreeNode*> children;
};

struct BinaryNode{
   int data;
   BinaryNode* left;
   BinaryNode* right;
};

vector<TreeNode*> bstToForest(BinaryNode* root){
  vector<TreeNode*> forest;
  if(root == nullptr) return forest;
  //创建当前子树根节点
  TreeNode* curroot = new TreeNode();
  curroot->data = root->data;
  //处理子树：
  vector<TreeNode*> childforest = bstToForest(root->left);
  curroot->children = childforest;
  vector<TreeNode*> siblingForest = bstToForest(root->right);
  //加入森林
  forest.push_back(root);
  for(TreeNode* siblingTree : siblingForest){
      forest.push_back(siblingTree);
  }
  return forest;
}

二叉树的遍历方式：

中序遍历：

前序遍历：

后序遍历：

二叉树遍历的应用：

1，利用后序遍历计算树中结点个数：
二叉树结点个数 = 左子树数 + 右子树数 + 1；

2，利用后序遍历计算树的高度：
二叉树的高度 = max(左子树高度， 右子树高度) + 1.

3，利用前序遍历建树：

4，利用前序遍历输出二叉树：
例如将二叉树以广义表的形式打印出来。

void PrintTree(TreeNode<type> *BT){
   cout<<BT->data;
   if(BT->leftson != null || BT->rightson != null){
      cout<<"(";
      PrintTree(BT->leftson);
      cout<<",";
      if(BT->rightson != null)
           PrintTree(BT->rightson);
      cout<<")";
   }
}

5，利用栈的前序遍历非递归算法：

void PreOrder(TreeNode<type> *p){
  stack <TreeNode<type> *> s;
  while(p != null){
    visit(p);
    if(p->rightson != null) s.push(p->rightson);
    if(p->leftson != null) p = p->leftson;
    else{
       p = s.gettop();
       s.pop();
    }
  }
}

6，利用栈的中序遍历非递归算法：

void InOrder(TreeNode<type> *p){
  stack<TreeNode<type> *> s;
  do{
    while(p != null){
      s.push(p); p = p->leftson;
    }
    if(!s.IsEmpty()){
      p = s.top(); s.pop();
      visit(p);
      p = p->rightson;
    }
  }while(p != null || !s.IsEmpty());
}

7，利用队列实现层次遍历：

void levOrder(TreeNode<type> *p){
  queue <TreeNode<type> *> q;
  q.enqueue(p);
  while(!q.isEmpty()){
    q.dequeue(p);
    visit(p);
    if(p->leftson != null) q.enqueue(p->leftson);
    if(p->rightson != null) q.enqueue(p->rightson);
  }
}

8,利用栈实现后序遍历的非递归算法：
理解为一种变种的先序遍历——

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<int> postorder(TreeNode* root){
  vector<int> res;
  if(root == nullptr) return res;
  
  stack<TreeNode*> stk;
  stack<int> outstk;
  stk.push(root);
  while(!stk.empty()){
    TreeNode* temp = stk.top();
    stk.pop();
    outstk.push(temp->val);
    //主栈中先左后右，保证在辅助栈中先右后左。
    if(temp->left) stk.push(temp->left);
    if(temp->right) stk.push(temp->right);
  }
  
  while(!outstk.empty()){
     res.push_back(outstk.top());
     outputstk.pop();
  }
}

线索化二叉树：

用处：

霍夫曼树与霍夫曼编码：

路径长度：

两个结点之间的路径长度：PL是连接两结点的路径上的分支数。
树的路径长度：各结点到根节点的路径长度之和。
树的外部路径长度：各叶节点到根节点的路径长度之和EPL
树的内部路径长度：各非叶节点到根节点的路径长度之和IPL

故有：树的路径长度PL = EPL + IPL

带权路径长度：

设二叉树T的n个叶节点分别具有权值，则称T为该权值集合的扩充二叉树。
带有权值的叶节点称为外结点；不带权值的分支节点称为内节点。
具有n个外结点的扩充二叉树的带权路径长度为树的各外结点所带权值与该节点到根的路径长度的乘积的和，即：

其中WPL最小的扩充二叉树称为最优二叉树。

Huffman树：

构造Huffman树的Huffman算法：

已知F为有n棵扩充二叉树的集合。
1，在F中选取两个根节点权值最小的扩充二叉树，作为左右子树构造新二叉树。置新二叉树根节点的权值为两者权值之和。
2，在F中删去这两个二叉树
3，向F中加入新二叉树。

算法实现：

Node* create_huffman_tree(char a[], int w[], int n){
  Node* addr[2*MAXN-1];
  int n1, n2;  //记录最小和次小的索引
  int u, v;    //u : 实际权值； v：数组中存储的权值
  int min1, min2;  //记录最小和次小权值。
  int i, j;
  //初始化叶节点
  for(i = 0; i < n; ++i){
    addr[i] = new Node();
    addr[i]->data = a[i];
    addr[i]->leftson = null;
    addr[i]->rightson = null;
    w[i] = -w[i];   //权值取反，标记为未合并状态。
  }
  //构建非叶节点：
  for(i = n; i < 2*n-1; ++i){
    n1 = -1; n2 = -1;
    min1 = 9999; min2 = 9999;
    
    for(j = 0; j < i; ++j){
       v = w[j];
       u = -v;  //还原权值
       if(u > 0){
         if(u < min1){
            min2 = min1;
            n2 = n1;
            min1 = u;
            n1 = j;
         }
         else if (u < min2){
           min2 = u;
           n2 = j;
         }
       }
    }
    //合并创建新节点
    addr[i] = new Node();
    addr[i]->data = '*';   //非叶节点的特殊标记
    addr[i]->leftson = addr[n1];
    addr[i]->rightson = addr[n2];
    
    //更新权值组合：
    w[i] = w[n1] + w[n2];
    w[n1] = -w[n1];
    w[n2] = -w[n2];
  }
  //处理根节点权值：
  w[2*n-2] = -w[2*n-2];
  
  return addr[2*n-2];
}

注意：
在构造Huffman树时，新合并的结点不能从底层开始——与要合并的在同一层。

Huffman算法应用——Huffman编码：

编码即是对于每一个字符使用一个单独的代码表示。
当每一个字符的使用频率大致相等时，将每一个代码都设置为等长，效率最高。这种即称作等长编码。
但如果字符出现的频率分布不相等，则可以让频率高的字符采用尽可能短的编码，让频率低的字符采用尽可能长的编码，来构造不等长编码。
霍夫曼树用来构造最短的，即是霍夫曼编码，构造方式如下：

Edit page
Share this post on:
Share this post via WhatsApp Share this post on Facebook Share this post on X Share this post via Telegram Share this post on Pinterest Share this post via email
Previous Post
排序算法
Next Post
图