数据结构(二) 数

五、树

• 树的定义

1. 
   

    
   
   
2. 树的逻辑表示：树形表示法、文氏图表示法、凹入表示法、括号表示法。
   
   

    
   
   

    
   
   

    
   
   

    
3. 结点：表示树中的元素，包括数据项及若干指向其子树的分支。
4. 结点的度：结点拥有的子树树；树的度：一棵树中最大的结点度数
   
   

    
5. 叶子结点：度为0的结点；分支结点：度不为0的结点；孩子：结点子树的根称为该结点的孩子；双亲：孩子结点的上层结点叫该结点的双亲；兄弟：同一双亲的孩子。
6. 深度：树中结点的最大层次数。                                                               
   
   

    
7. 有序树：树中各结点的子树从左至右是有次序的，不能互换。否则称为无序树。

• 树的性质

1. 树中的结点数等于所有结点的度数加1。
   
   

    
2. 度为m的树中第i层上至多有mi-1 个结点（i>=1）。    
3. 
   

    
   
   
4. 
   

    
   
   
5. 
   

    
   
   

• 二叉树的概念

1. 
   

    
   
   
2. 满二叉树：定义——一棵深度为k且具有2k-1个结点的二叉树。特点——每一层上的结点数都是最大结点数。
3. 完全二叉树：定义——深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。

• 二叉树的性质

1. 
   

    
   二叉树的第i层上至多有2i-1(i>=1)个结点。
2. 深度为K的二叉树至多有2k-1个结点。
3. 对任何一棵二叉树T，如果其叶子数为n0，度为2的结点数为n2，则n0=n2+1。
   
   

    
4. 
   

    
   
   
5. 
   

    
   
   
6. 一个有n个结点的完全二叉树，编号最大的分支结点的编号是
   
   

    
7. 一个有n个结点的完全二叉树，n0的个数是不小于n/2的最小整数。

• 二叉树的存储结构

1. 用一组连续的存储单元存储二叉树的数据元素。在存储之前对二叉树的所有结点安排一个适当的序列，使得结点在这个序列中的相互位置能反应出结点之间的逻辑关系。                                                                                                     
   
   

    
2. 特点：结点间关系蕴含在其存储位置中；浪费空间，适于存满二叉树和完全二叉树。

• 二叉树的链式存储结构

1. 用一个链表来存储一棵二叉树，二叉树中每一个结点用链表中的一个链结点来存储。                                                                                                   
   
   

    
2. 
   

    
   
   
3. 
   

    
   
   

• 遍历二叉树

1. 遍历方法：                                                                                                    
   
   

    
2. 
   

    
   
   
3. 利用遍历结果确定二叉树：                                                                         
   
   

    
4. 先序遍历算法：
   1. //先序遍历递归算法
   2. void preorder(Tree t){
   3. if(t==null)
   4. return;
   5. visit(t);
   6. preorder(t.left());
   7. preorder(t.right());
   8. }
   1. //先序遍历非递归算法
   2. void PreOrderUnrec(Bitree t)
   3. {
   4. //创建栈来存放树的结点
   5. SqStack s;
   6. StackInit(s);
   7. p=t;
   9. while (p!=null || !StackEmpty(s))
   10. {
   11. while (p!=null) //遍历左子树
   12. {
   13. visite(p->data);
   14. push(s,p);
   15. p=p->lchild;
   16. }//endwhile
   18. if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历
   19. {
   20. p=pop(s);
   21. p=p->rchild;
   22. }//endif
   24. }//endwhile
   26. }//PreOrderUnrec
5. 中序遍历算法：
   1. //中序遍历递归算法
   2. void inorder(Tree t){
   3. if(t==null)
   4. return;
   5. inorder(t.left());
   6. visit(t);
   7. inorder(t.right());
   8. }
   1. void InOrderUnrec(Bitree t)
   2. {
   3. //创建栈来存放树的结点
   4. SqStack s;
   5. StackInit(s);
   6. p=t;
   8. while (p!=null || !StackEmpty(s))
   9. {
   10. while (p!=null) //遍历左子树
   11. {
   12. push(s,p);
   13. p=p->lchild;
   14. }//endwhile
   16. if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历
   17. {
   18. p=pop(s);
   19. visite(p->data); //访问根节点
   20. p=p->rchild;
   21. }//endif
   23. }//endwhile
   25. }//InOrderUnrec
6. 后序遍历算法：
   1. 后序遍历递归算法
   2. void inorder(Tree t){
   3. if(t==null)
   4. return;
   5. inorder(t.left());
   6. inorder(t.right());
   7. visit(t);
   8. }
   1. //后序遍历非递归算法
   2. 对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。
   3. void postOrder2(BinTree *root) //非递归后序遍历
   4. {
   5. stack<BTNode*> s;
   6. BinTree *p=root;
   7. BTNode *temp;
   8. while(p!=NULL||!s.empty())
   9. {
   10. while(p!=NULL) //沿左子树一直往下搜索，直至出现没有左子树的结点
   11. {
   12. BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
   13. btn->btnode=p;
   14. btn->isFirst=true;
   15. s.push(btn);
   16. p=p->lchild;
   17. }
   18. if(!s.empty())
   19. {
   20. temp=s.top();
   21. s.pop();
   22. if(temp->isFirst==true) //表示是第一次出现在栈顶
   23. {
   24. temp->isFirst=false;
   25. s.push(temp);
   26. p=temp->btnode->rchild;
   27. }
   28. else //第二次出现在栈顶
   29. {
   30. cout<<temp->btnode->data<<" ";
   31. p=NULL;
   32. }
   33. }
   34. }
   35. }

• 线索二叉树

1. 利用二叉链表的空指针域，建立指向该结点的前驱/后继结点的指针，方便二叉树的线性化使用。                                                                                     
   
   

    
2. 对二叉链表以某种次序遍历使其变为线索二叉树的过程叫做线索化。有先序线索二叉树、中序线索二叉树（更实用）和后序线索二叉树三种。
   
   

    
3. 建立中序线索二叉树                                                                                
   
   

    
4. 
   

    
   
   

    
   
   

    
   
   
5. 
   

    
   
   

    
   
   

• 树的存储结构

1. 双亲表示法：用一组连续空间存储树的结点，每个节点包含两个域——数据域用来存放结点本身信息，双亲域用来指示本结点的双亲结点在数组中位置。
   
   

    
2. 孩子表示法：采用孩子链表，每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表。                                                             
   
   

    
                                 带双亲的孩子链表                                                                                             
   
   

    
3. 孩子兄弟表示法：用二叉链表作为树的存储结构。链表中结点的两个链域分为指向该结点的第一个孩子结点和下一个兄弟结点。                                                  
   
   

    

• 森林与二叉树的转换

1. 将树转换为二叉树                                                                                     
   
   

    
   
   

    
2. 将二叉树转换为树：                                                                                 
   
   

    
   
   

    
3. 森林转换成二叉树：                                                                                                 
   
   

    
   
   

    
4. 二叉树转换成森林                                                                                    
   
   

    
   
   

    

• 哈夫曼树

1. 结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根节点到该结点之间的路径长度与该结点的权的乘积。                                                                          
   
   

    
   
   

    
2. 在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称哈夫曼树。