二叉树 和 其他树 《数据结构和算法应用》

概述:

平衡树——特点:所有结点左右子树深度差≤1

排序树——特点:所有结点“左小右大
字典树——由字符串构成的二叉排序树
判定树——特点:分支查找树(例如12个球如何只称3次便分出轻重)
带权树——特点:路径带权值(例如长度)

最优树——是带权路径长度最短的树,又称 Huffman树,用途之一是通信中的压缩编码。

1. 二叉排序树(二叉查找树 Binary Search Tree):

class Node:
    def __init__(self,item):
        self.item = item
        self.child1 = None
        self.child2 = None


class Tree:
    def __init__(self):
        self.root = None

    def add(self, item):
        node = Node(item)
        if self.root is None:
            self.root = node
        else:
            q = [self.root]

            while True:
                pop_node = q.pop(0)
                if pop_node.child1 is None:
                    pop_node.child1 = node
                    return
                elif pop_node.child2 is None:
                    pop_node.child2 = node
                    return
                else:
                    q.append(pop_node.child1)
                    q.append(pop_node.child2)

    def traverse(self):  # 层次遍历
        if self.root is None:
            return None
        q = [self.root]
        res = [self.root.item]
        while q != []:
            pop_node = q.pop(0)
            if pop_node.child1 is not None:
                q.append(pop_node.child1)
                res.append(pop_node.child1.item)

            if pop_node.child2 is not None:
                q.append(pop_node.child2)
                res.append(pop_node.child2.item)
        return res

    def preorder(self,root):  # 先序遍历
        if root is None:
            return []
        result = [root.item]
        left_item = self.preorder(root.child1)
        right_item = self.preorder(root.child2)
        return result + left_item + right_item

    def inorder(self,root):  # 中序序遍历
        if root is None:
            return []
        result = [root.item]
        left_item = self.inorder(root.child1)
        right_item = self.inorder(root.child2)
        return left_item + result + right_item

    def postorder(self,root):  # 后序遍历
        if root is None:
            return []
        result = [root.item]
        left_item = self.postorder(root.child1)
        right_item = self.postorder(root.child2)
        return left_item + right_item + result

t = Tree()
for i in range(10):
    t.add(i)
print('层序遍历:',t.traverse())
print('先序遍历:',t.preorder(t.root))
print('中序遍历:',t.inorder(t.root))
print('后序遍历:',t.postorder(t.root))
输出结果:

层次遍历: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
先次遍历: [0, 1, 3, 7, 8, 4, 9, 2, 5, 6]
中次遍历: [7, 3, 8, 1, 9, 4, 0, 5, 2, 6]
后次遍历: [7, 8, 3, 9, 4, 1, 5, 6, 2, 0]

 

1.1 二叉排序树:

或是一棵空树;或者是具有如下性质的非空二叉树

(1)若左子树不为空,左子树的所有结点的值均小于根的值;

(2)若右子树不为空,右子树的所有结点均大于根的值;

(3)它的左右子树也分别为二叉排序树。

例:二叉排序树 如图9.7:

二叉排序树的查找过程和次优二叉树类似,通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列,一个无序序列可以通过构造一棵二叉排序树变成一个有序序列,构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点,在进行插入操作时,不必移动其它结点,只需改动某个结点的指针,由空变为非空即可。搜索,插入,删除的复杂度等于树高,期望O(logn),最坏O(n)(数列有序,树退化成线性表).
虽然二叉排序树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉排序树可以使树高为O(logn),如SBT,AVL,红黑树等.故不失为一种好的动态排序方法.

2.2 二叉排序树b中查找

在二叉排序树b中查找x的过程为:

若b是空树,则搜索失败,否则:
若x等于b的根节点的数据域之值,则查找成功;否则:
若x小于b的根节点的数据域之值,则搜索左子树;否则:
查找右子树。
Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){    
    //在根指针T所指二叉排序樹中递归地查找其关键字等于key的数据元素,若查找成功,    
    //则指针p指向该数据元素节点,并返回TRUE,否则指针P指向查找路径上访问的    
    //最好一个节点并返回FALSE,指针f指向T的双亲,其初始调用值为NULL    
    if(!T){ p=f; return FALSE;} //查找不成功    
    else if EQ(key, T->data.key) {P=T; return TRUE;} //查找成功    
    else if LT(key,T->data.key)     
        return SearchBST(T->lchild, key, T, p); //在左子树继续查找    
    else return SearchBST(T->rchild, key, T, p); //在右子树继续查找    
}

 

2.3 在二叉排序树插入结点的算法

向一个二叉排序树b中插入一个结点s的算法,过程为:

2.4 在二叉排序树删除结点的算法

在二叉排序树删去一个结点,分三种情况讨论:

若*p结点为叶子结点,即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构,则只需修改其双亲结点的指针即可。
若*p结点只有左子树PL或右子树PR,此时只要令PL或PR直接成为其双亲结点*f的左子树即可,作此修改也不破坏二叉排序树的特性。
若*p结点的左子树和右子树均不空。在删去*p之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整,可以有两种做法:其一是令*p的左子树为*f的左子树,*s为*f左子树的最右下的结点,而*p的右子树为*s的右子树;其二是令*p的直接前驱(或直接后继)替代*p,然后再从二叉排序树中删去它的直接前驱(或直接后继)。在二叉排序树上删除一个结点的算法如下:
Status DeleteBST(BiTree &T, KeyType key){
    //若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素,并返回  
    //TRUE;否则返回FALSE   
    if(!T) return FALSE;    //不存在关键字等于key的数据元素  
    else{
        if(EQ(key, T->data.key)) {return Delete(T)};     找到关键字等于key的数据元素
        else if(LT(key, T->data.key))    return DeleteBST(T->lchild, key);
        else return DeleteBST(T->rchild, key);
    }
}
Status Delete(BiTree &p){
    //从二叉排序树中删除结点p,并重接它的左或右子树   
    if(!p->rchild){  //右子树空则只需重接它的左子树  
        q=p; p=p->lchild;    free(q);
    }
    else if(!p->lchild){ //左子树空只需重接它的右子树  
        q=p; p=p->rchild; free(q);
    }
    else{   //左右子树均不空  
        q=p;
        s=p->lchild;
        while(s->rchild){
            q=s;
            s=s->rchild
        }   //转左,然后向右到尽头  
        p->data = s->data;    //s指向被删结点的“前驱”  
        if(q!=p)
            q->rchild = s->lchild; //重接*q的右子树  
        else
            q->lchild = s->lchild;    //重接*q的左子树  
        free(s);
    }
    return TRUE;
}
Status DeleteBST(BiTree &T, KeyType key){
    //若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素,并返回
    //TRUE;否则返回FALSE
    if(!T) return FALSE;    //不存在关键字等于key的数据元素
    else{
        if(EQ(key, T->data.key)) {return Delete(T)};     找到关键字等于key的数据元素
        else if(LT(key, T->data.key))    return DeleteBST(T->lchild, key);
        else return DeleteBST(T->rchild, key);
    }
}
Status Delete(BiTree &p){
    //从二叉排序树中删除结点p,并重接它的左或右子树
    if(!p->rchild){  //右子树空则只需重接它的左子树
        q=p; p=p->lchild;    free(q);
    }
    else if(!p->lchild){ //左子树空只需重接它的右子树
        q=p; p=p->rchild; free(q);
    }
    else{   //左右子树均不空
        q=p;
                s=p->lchild;
        while(s->rchild){
                       q=s;
                       s=s->rchild
                }   //转左,然后向右到尽头
        p->data = s->data;    //s指向被删结点的“前驱”
        if(q!=p)
                       q->rchild = s->lchild; //重接*q的右子树
        else
                        q->lchild = s->lchild;    //重接*q的左子树
        free(s);
    }
    return TRUE;
}

 

2. 5二叉排序树性能分析

每个结点的Ci为该结点的层次数。最坏情况下,当先后插入的关键字有序时,构成的二叉排序树蜕变为单支树,树的深度为n,其平均查找长度为 (和顺序查找相同),最好的情况是二叉排序树的形态和折半查找的判定树相同,其平均查找长度和log2(n)成正比 (O(log2(n)))。

若b是空树,则将s所指结点作为根结点插入,否则:
若s->data等于b的根结点的数据域之值,则返回,否则:
若s->data小于b的根结点的数据域之值,则把s所指结点插入到左子树中,否则:
把s所指结点插入到右子树中。
/*当二叉排序树T中不存在关键字等于e.key的数据元素时,插入e并返回TRUE,否则返回FALSE*/    
Status InsertBST(BiTree &T, ElemType e){    
    if(!SearchBST(T, e.key, NULL,p){    
        s=(BiTree)malloc(sizeof(BiTNode));    
        s->data = e; s->lchild = s->rchild = NULL;    
        if(!p)  T-s;    //被插结点*s为新的根结点    
        else if LT(e.key, p->data.key) p->lchld = s;  //被子插结点*s为左孩子    
        else p->rchild = s;  //被插结点*s为右孩子    
        return TRUE;    
    }    
    else return FALSE;  //树中已有关键字相同的结点,不再插入    
}

 

 
2.6 二叉排序树的优化
Size Balanced Tree(SBT)
AVL树
红黑树
Treap(Tree+Heap)
这些均可以使查找树的高度为O(logn)

2. 平衡树二叉树)(又称AVL 树):

1. 1 平衡二叉树(Balanced Binary Tree)

性质:  左右子树都是平衡二叉树且所有结点左、右子树深度之差的绝对值 ≤ 1。

若定义结点的“平衡因子”  BF(Balance Factor) = 左子树深度 –右子树深度 则:平衡二叉树中所有结点的BF ∈[ -1, 0, 1 ]

例:判断下列二叉树是否AVL树?

常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中,我们可以看到,其高度一般都良好地维持在O(log2n),大大降低了操作的时间复杂度。

平衡二叉树是二叉排序树的另一种形式。

我们希望由任何初始序列构成的二叉排序树都是平衡二叉树。因为平衡二叉树上任何结点的左右子树的深度之差都不超过1,则可以证明它的深度和logN是同数量级的(其中N是结点的个数)。由此,它的平均查找长度也和logN同数量级。

C语言描述:

typedef struct  BSTNode {    
    ElemType    data;    
    int     bf;     //结点的平衡因子    
    struct BSTNode  *lchild, *rchild;       
    //左、右孩子指针    
} BSTNode, * BSTree;    
typedef struct  BSTNode {  
        ElemType    data;  
        int     bf;     //结点的平衡因子  
        struct BSTNode  *lchild, *rchild;     
                        //左、右孩子指针  
    } BSTNode, * BSTree;

 

构造二叉平衡(查找)树的方法是:在插入过程中,采用平衡旋转技术

插入算法 :

算法思想:

在平衡二叉排序树BBST上插入一个新的数据元素e的递归算法可描述如下:

1.若BBST为空树,则插入一个数据元素为e的新结点作为BBST的根结      点,树的深度增1;

2.若e的关键字和BBST的根结点的关键字相等,则不进行插入;

3.若e的关键字小于BBST的根结点的关键字,而且在BBST的左子树中不存在和e有相同关键字的结点,则将e插入在BBST的左子树上,并且当插入之后的左子树深度增加(+1)时,分别就下列不同情况处理之:

i.BBST的根结点的平衡因子为-1(右子树的深度大于左子树的深度):则将根结点的平衡因子更改为0,BBST的深度不变;

ii.BBST的根结点的平衡因子为0(左、右子树的深度相等):则将根结点的平衡因子更改为1,BBST的深度增1;

iii.BBST的根结点的平衡因子为1(左子树的深度大于右子树的深度):

a. 若BBST的左子树根结点的平衡因子为1,则需进行单向右旋平衡处理,并且在右旋处理之后,将根结点和其右子树根结点的平衡因子更改为0,树的深度不变;

b. 若BBST的左子树根结点的平衡因子为-1,则需进行先向左、后向右的双向旋转平衡处理,并且在旋转处理之后,修改根结点和其左、右子树根结点的平衡因子,树的                深度不变。

4.若e的关键字大于BBST的根结点的关键字,而且在BBST的右子树中不存在和e有相同关键字的结点,则将e插入在BBST的右子树上,并且当插入之后的右子树深度增加(+1)时,分别就不同情况处理之。其处理操作和上述3.中描述相对称。

typedef struct  BSTNode {    
    ElemType    data;    
    int     bf;     //结点的平衡因子    
    struct BSTNode  *lchild, *rchild;       
    //左、右孩子指针    
} BSTNode, * BSTree;    
void R_Rotate (BSTree &p) {    
    //对以*p为根的二叉排序树作右旋处理,处理之后p指向新的树根结点,     
    //即旋转处理之前的左子树的根结点     
    lc = p->lchild;          //lc指向的*p的左子树根结点    
    p->lchild = lc->rchild;       //lc的右子树挂接为*p的左子树    
    lc->rchild = p;      
    p = lc;             //p指向新的根结点    
} // R_Rotate     
  
void L_Rotate (BSTree &p) {    
    //对以*p为根的二叉排序树作左旋处理,处理之后p指向新的树根结点,    
    //即旋转处理之前的右子树的根结点     
    rc = p->rchild;          //rc指向的*p的右子树根结点    
    p->rchild = rc->lchild;       //rc的左子树挂接为*p的右子树    
    rc->lchild = p;      
    p = rc;             //p指向新的根结点     
} // L_Rotate     
  
  
  
#define LH  +1      //左高     
#define EH  0       //等高     
#define RH  -1      //右高     
  
  
  
Status InsertAVL (BSTree &T, ElemType e, Boolean &taller) {    
    //若在平衡的二叉排序树T中不存在和e有相同关键字的结点,则插入     
    //一个数据元素为e的新结点,并返回1,否则返回0。若因插入而使二    
    //叉排序树失去平衡,则作平衡旋转处理,布尔变量taller反映T长高    
    //与否。     
    if (!T) {      //插入新结点,树“长高”,置taller为TRUE    
        T = (BSTree) malloc (sizeof (BSTNode));    
        T->data = e;    
        T->lchild = T->rchild = NULL;    
        taller = TRUE;    
    }    
    else {    
        if (EQ(e.key, T->data.key))      //树中已存在和e有相同关键字的    
        {taller = FALSE; return 0;}     //结点则不再插入    
        if (LT(e.key, T->data.key)) {        //应继续在*T的左子树中进行搜索    
            if (!InsertAVL(T->lchild, e, taller))    //未插入    
                return  0;    
            if (taller)         //已插入到*T的左子树中且左子树“长高”    
                switch (T->bf) {     //检查*T的平衡度    
                    case LH:        //原本左子树比右子树高,需要作左平衡处理    
                        LeftBalance (T);    
                        taller = FALSE;    
                        break;    
                    case EH:            //原本左右子树等高,现因左子树增高而使树增高    
                        T->bf = LH;    
                        taller = TRUE;    
                        break;    
  
                    case RH:        //原本右子树比左子树高,现左、右子树等高    
                        T->bf = EH;    
                        taller = FALSE;    
                        break;    
            } // switch (T->bf)    
        } // if     
        else {      //应继续在*T的右子树中进行搜索    
            if (!InsertAVL(T->rchild, e, taller))        //未插入    
                return  0;    
            if (taller)     //已插入到*T的右子树中且右子树“长高”    
                switch (T->bf) { //检查*T的平衡度    
                case LH:        //原本右子树比左子树高,现左、右子树等高    
                    T->bf = EH;    
                    taller = FALSE;    
                    break;    
                case EH:    //原本左右子树等高,现因右子树增高而使树增高    
                    T->bf = RH;    
                    taller = TRUE;    
                    break;    
                case RH:        //原本右子树比左子树高,需要作右平衡处理       
                    RightBalance (T);    
                    taller = FALSE;    
                    break;    
            } // switch (T->bf)     
        } // else     
    } // else     
    return  1;     
} // InsertAVL     
  
  
void LeftBalance (BSTree &T) {    
    //对以指针T所指结点为根的二叉树作左平衡旋转处理,本算法     
    //结束时,指针T指向新的根结点     
    lc = T->lchild;          //lc指向*T的左子树根结点    
    switch (lc->bf) {        //检查*T的左子树的平衡度,并作相应平衡处理    
            case LH:    //新结点插入在*T的左孩子的左子树上,要作单右旋处理    
                T->bf = lc->bf = EH;    
                R_Rotate (T);    
                break;    
            case RH:    //新结点插入在*T的左孩子的右子树上,要作双旋处理    
                rd = lc->rchild;     //rd指向*T的左孩子的右子树根    
                switch (rd->bf) {    //修改*T及其左孩子的平衡因子    
            case LH:    
                T->bf = RH;    
                lc->bf = EH;    
                break;    
            case EH:    
                T->bf = lc->bf = EH;    
                break;    
            case RH:    
                T->bf = EH;    
                lc->bf = LH;    
                break;    
                } // switch (rd->bf)     
                rd->bf = EH;    
                L_Rotate (T->lchild);   //对*T的左子树作左旋平衡处理    
                R_Rotate (T);      //对*T作右旋平衡处理    
    } // switch (lc->bf)     
} // LeftBalance

 

3. 判定树(决策树):

      二分查找过程可用二叉树来描述:把当前查找区间的中间位置上的结点作为根,左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树,称为描述二分查找的判定树(Decision Tree 决策树)或比较树(Comparison Tree)。

注意:
判定树的形态只与表结点个数n相关,而与输入实例中R[1..n].keys的取值无关。
【例】具有11个结点的有序表可用下图所示的判定树来表示。

举例:12个球如何用天平只称3次便分出轻重?

分析:12个球中必有一个非轻即重,即共有24种“次品”的可能性。每次天平称重的结果有3种,连称3次应该得到的结果有33=27种。说明仅用3次就能找出次品的可能性是存在的。

思路:首先,将12个球分三组,每组4个,任意取两组称。会有两种情况:平衡,或不平衡。其次,一定要利用已经称过的那些结论;即充分利用“旧球”的标准性作为参考。

二分查找判定树的查找
二分查找就是将给定值K与二分查找判定树的根结点的关键字进行比较。若相等,成功。否则若小于根结点的关键字,到左子树中查找。若大于根结点的关键字,则到右子树中查找。
【例】对于有11个结点的表,若查找的结点是表中第6个结点,则只需进行一次比较;若查找的结点是表中第3或第9个结点,则需进行二次比较;找第1,4,7,10个结点需要比较三次;找到第2,5,8,11个结点需要比较四次。
由此可见,成功的二分查找过程恰好是走了一条从判定树的根到被查结点的路径,经历比较的关键字次数恰为该结点在树中的层数。若查找失败,则其比较过程是经历了一条从判定树根到某个外部结点的路径,所需的关键字比较次数是该路径上内部结点的总数。
【例】待查表的关键字序列为:(05,13,19,21,37,56,64,75,80,88,92),若要查找K=85的记录,所经过的内部结点为6、9、10,最后到达方形结点”9-10″,其比较次数为3。
实际上方形结点中”i-i+1″的含意为被查找值K是介于R[i].key和R[i+1].key之间的,即R[i].key<K<R[i+1].key。
二分查找的平均查找长度
设内部结点的总数为n=2h-1,则判定树是深度为h=lg(n+1)的满二叉树(深度h不计外部结点)。树中第k层上的结点个数为2k-1,查找它们所需的比较次数是k。因此在等概率假设下,二分查找成功时的平均查找长度为:
ASLbn≈lg(n+1)-1
二分查找在查找失败时所需比较的关键字个数不超过判定树的深度,在最坏情况下查找成功的比较次数也不超过判定树的深度。即为:
 
二分查找的最坏性能和平均性能相当接近。二分查找的优点和缺点
虽然二分查找的效率高,但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间。
二分查找只适用顺序存储结构。为保持表的有序性,在顺序结构里插入和删除都必须移动大量的结点。因此,二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。
对那些查找少而又经常需要改动的线性表,可采用链表作存储结构,进行顺序查找。链表上无法实现二分查找。

5. 带权树:

即路径带有权值。例如:

6. 最优树(赫夫曼树):

赫夫曼树:给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为赫夫曼树(Huffman tree)。即带权路径长度最短的树。

赫夫曼树构造算法:
假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为{ w1、w2、…、wn},则哈夫曼树的构造规则为:  (1) 将{w1、w2、…,wn}看成是有n 棵树的森林(每棵树仅有一个结点);  (2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;  (3)从森林中删除选取的两棵树,并将新树加入森林;  (4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。
赫夫曼编码:是通信中最经典的压缩编码.
其算法:
stdafx.h文件
// stdafx.h : include file for standard system include files,  
// or project specific include files that are used frequently, but  
// are changed infrequently  
//  
  
#pragma once  
  
#include <stdio.h>    
#include "stdlib.h"  
#include <iostream>  
using namespace std;  
  
  
//宏定义      
#define TRUE   1      
#define FALSE   0      
#define OK    1      
#define ERROR   0    
#define INFEASIBLE -1      
#define OVERFLOW -2    
#define STACKEMPTY -3   
#define QUEUEEMPTY  -3      
  
#define MAX 10 // MAXIMUM STACK CONTENT    
#define MAX_QUEUE 10 // MAXIMUM QUEUE CONTENT    
  
typedef int Status;      
typedef int ElemType;    
  
typedef struct{  
    unsigned int weight;  
    unsigned int parent, lchild,rchild;  
}HTNode, *HuffmanTree;  //动态分配数组存储赫夫曼树  
  
typedef char * * HuffmanCode;//动态分配数组存储赫夫曼编码表  
test.cpp文件:
// Test.cpp : Defines the entry point for the console application.    
//    
#include "stdafx.h"    
  
  
  
/************************************************************************/  
/* 算法: 
*/  
/************************************************************************/  
  
void select(HuffmanTree &HT,int n,int &h1,int &h2)  
{  
    int i ,j;  
  
    for(i=1;i<=n;i++)  
        if(!HT[i].parent)  //一旦找到父结点不为0的结点就停止  
        {  
            h1=i;       
            break;  
        }  
        for(j=i+1;j<=n;j++)  
            if(!HT[j].parent)  
            {  
                h2=j;  
                break;  
            }  
            for(i=1;i<=n;i++)  
                if(HT[h1].weight>HT[i].weight&&!HT[i].parent&&(h2!=i))  
                    h1=i;   //进行比较,找权值最小,和h2不同的结点  
            for(j=1;j<=n;j++)  
                if(HT[h2].weight>HT[j].weight&&!HT[j].parent&&(h1!=j))  
                    h2=j;   //进行比较,找权值最小,和h1不同的结点  
            if(h1>h2)  
            {  
                int temp;    //将权值最小的结点赋给h1  
                temp=h1;  
                h1=h2;  
                h2=temp;  
            }  
}  
/************************************************************************/  
/* 
w存放n 个字符的权值(均>0),构造赫夫曼树HT,并求出n 个字符的赫夫曼编码HC。 
*/  
/************************************************************************/  
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w,int n)  
{  
    if(n<=1) return;  
    int m,i;  
    char *cd;  
    int s1, s2;  
    // HuffmanTree p;  
    m = 2*n-1;  
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));  //0号单元未用  
    for (i=1; i<=n; i++) { //初始化,相当: p = HT; p = {*w, 0, 0,0 }, ++p;  
        HT[i].weight=w[i-1];  
        HT[i].parent=0;  
        HT[i].lchild=0;  
        HT[i].rchild=0;  
    }  
    for (i=n+1; i<=m; i++) { //初始化 p = {*w, 0, 0,0 }, ++p;  
        HT[i].weight=0;  
        HT[i].parent=0;  
        HT[i].lchild=0;  
        HT[i].rchild=0;  
    }  
  
    //添加查看便于调试  
    printf("\n-------------------------------------------");  
    printf("\n哈夫曼树的构造过程如下所示:\n");  
    printf("HT初态:\n");  
    printf(" 结点   weight  parent  lchild  rchild");  
    for (i=1; i<=m; i++)  
        printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,HT[i].parent,HT[i].lchild, HT[i].rchild);  
  
    for (i=n+1; i<=m; i++) { // 建哈夫曼树  
        // 在HT[1..i-1]中选择parent为0且weight最小的两个结点,  
        // 其序号分别为s1和s2。  
        select(HT, i-1,s1,s2);  
        HT[s1].parent = i; HT[s2].parent = i;  
        HT[i].lchild = s1; HT[i].rchild = s2;  
        HT[i].weight = HT[s1].weight + HT[s2].weight;  
        //添加查看,便于调试  
        printf("\nselect: s1=%d s2=%d\n", s1, s2);  
        printf(" 结点   weight  parent  lchild  rchild");  
        for (int j=1; j<=i; j++)  
            printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,  
            HT[j].parent,HT[j].lchild, HT[j].rchild);  
  
    }  
  
    //---从叶子到根逆向求每个字符的赫夫曼编码---  
    int start,f;  
    unsigned int c;  
    HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n个字符编码的头指针向量  
    cd=(char *)malloc(n*sizeof(char));     //分配求编码的工作空间  
    cd[n-1]='\0';        //编码结束符  
    for(i=1;i<=n;++i)  
    {  
        //逐个字符求赫夫曼编码  
        start=n-1;  
        for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码  
            if(HT[f].lchild==c)  
                cd[--start]='0';  
            else  
                cd[--start]='1';  
        HC[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间  
        strcpy(HC[i],&cd[start]);  //从cd复制编码到HC  
    }  
    free(cd);  //释放工作区间  
}  
void main()  
{  
    HuffmanTree HT; HuffmanCode HC; int *w,n,i;  
    printf("输入结点数: ");  
    scanf("%d",&n);  
    HC=(HuffmanCode)malloc(n*sizeof(HuffmanCode));  
    w=(int *)malloc(n*sizeof(int));  
    printf("输入%d个结点的权值: ",n);  
    for(i=0;i<n;i++)  
        scanf("%d",&w[i]);  
    HuffmanCoding(HT,HC,w,n);  
    printf("\n-------------------------------------------\n");  
    printf("\n各结点的赫夫曼编码:\n");  
    printf("编号  权值  编码\n");  
    for(i=1;i<=n;i++)  
        printf("%2d,%6d:%6s\n",i,w[i-1],HC[i]);  
  
}

 

关于二叉树


二叉树作为树的一种,是一种重要的数据结构,也是面试官经常考的东西。昨天看了一下关于树中的面试题,发现二叉树中的面试题比较常见的题型大概有下面几个:创建一颗二叉树(先序,中序,后序)、遍历一颗二叉树(先序,中序,后序和层次遍历)、求二叉树中叶子节点的个数、求二叉树的高度、求二叉树中两个节点的最近公共祖先、打印和为某一值的全部路径、求某一节点是否在一个树中等等。

再详细的说这些面试题之前,不妨先看一下几种常见的二叉树:

完全二叉树:若二叉树的高度是h,除第h层之外,其他(1~h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没?实际上,完全二叉树和堆联系比较紧密哈~~~

满二叉树:除最后一层外,每一层上的所有节点都有两个子节点,最后一层都是叶子节点。

哈夫曼树:又称为最有数,这是一种带权路径长度最短的树。哈夫曼编码就是哈夫曼树的应用。

平衡二叉树:所谓平衡二叉树指的是,左右两个子树的高度差的绝对值不超过 1。

红黑树:红黑树是每个节点都带颜色的树,节点颜色或是红色或是黑色,红黑树是一种查找树。红黑树有一个重要的性质,从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树,插入,删除,查找的复杂度都是O(log N)。

 

二叉树中的那些面试题


再具体说二叉树中的那些面试题之前,我们先看一下二叉树中的每个节点是什么样的,以及为了完成这些面试题,二叉树中声明的函数原型是什么样的:

二叉树的节点:BinTreeNode

 1 //二叉树的节点类
 2 class BinTreeNode
 3 {
 4 private:
 5     int data;
 6     BinTreeNode *left,*right;
 7 public:
 8     //利用初始化列表完成data,left,rightn的初始化
 9     BinTreeNode(const int &item,BinTreeNode *lPtr = NULL,BinTreeNode *rPtr = NULL):data(item) ,left(lPtr),right(rPtr){};
10     void set_data(int item)
11     {
12         data = item;
13     }
14     int get_data()const
15     {
16         return data;
17     }
18     void set_left(BinTreeNode *l)
19     {
20         left = l;
21     }
22     BinTreeNode* get_left()const
23     {
24         return left;
25     }
26     void set_right(BinTreeNode *r)
27     {
28         right = r;
29     }
30     BinTreeNode* get_right()const
31     {
32         return right;
33     }
34 };

 

二叉树原型:BinTree,其中包含了这篇文章中要完成的函数原型的完整声明。

复制代码
 1 //二叉树
 2 class BinTree
 3 {
 4 private:
 5     BinTreeNode *root;
 6 public:
 7     BinTree(BinTreeNode *t = NULL):root(t){};
 8     ~BinTree(){delete root;};
 9     void set_root(BinTreeNode *t)
10     {
11         root = t;
12     }
13     BinTreeNode* get_root()const
14     {
15         return root;
16     }
17     //1.创建二叉树
18     BinTreeNode* create_tree();
19     //2.前序遍历
20     void pre_order(BinTreeNode *r)const;
21     //3.中序遍历
22     void in_order(BinTreeNode *r)const;
23     //4.后序遍历
24     void post_order(BinTreeNode *r)const;
25     //5.层次遍历
26     void level_order(BinTreeNode *r)const;
27     //6.获得叶子节点的个数
28     int get_leaf_num(BinTreeNode *r)const;
29     //7.获得二叉树的高度
30     int get_tree_height(BinTreeNode *r)const;
31     //8.交换二叉树的左右儿子
32     void swap_left_right(BinTreeNode *r);
33     //9.求两个节点pNode1和pNode2在以r为树根的树中的最近公共祖先
34     BinTreeNode* get_nearest_common_father(BinTreeNode *r,BinTreeNode *pNode1,BinTreeNode *pNode2)const;
35     //10.打印和为某一值的所有路径
36     void print_rout(BinTreeNode *r,int sum)const;
37     //11.判断一个节点t是否在以r为根的子树中
38     bool is_in_tree(BinTreeNode *r,BinTreeNode *t)const;
39 };

 

复制代码

2.1 创建一颗二叉树

创建一颗二叉树,可以创建先序二叉树,中序二叉树,后序二叉树。我们在创建的时候为了方便,不妨用‘#’表示空节点,这时如果先序序列是:6 4 2 3 # # # # 5 1 # # 7 # #,那么创建的二叉树如下:

下面是创建二叉树的完整代码:穿件一颗二叉树,返回二叉树的根。

复制代码
1 //创建二叉树,这里不妨使用前序创建二叉树,遇到‘#’表示节点为空
 2 BinTreeNode* BinTree::create_tree()
 3 {
 4     char item;
 5     BinTreeNode *t,*t_l,*t_r;
 6     cin>>item;
 7     if(item != '#')
 8     {
 9         BinTreeNode *pTmpNode = new BinTreeNode(item-48);
10         t = pTmpNode;
11         t_l = create_tree();
12         t->set_left(t_l);
13         t_r = create_tree();
14         t->set_right(t_r);
15         return t;
16     }
17     else
18     {
19         t = NULL;
20         return t;
21     }
22 }

 

复制代码

2.2 二叉树的遍历

二叉树的遍历分为:先序遍历,中序遍历和后序遍历,这三种遍历的写法是很相似的,利用递归程序完成也是灰常简单的:

复制代码
1 //前序遍历
 2 void BinTree::pre_order(BinTreeNode *r)const
 3 {
 4     BinTreeNode *pTmpNode = r;
 5     if(pTmpNode != NULL)
 6     {
 7         cout<<pTmpNode->get_data()<<" ";
 8         pre_order(pTmpNode->get_left());
 9         pre_order(pTmpNode->get_right());
10     }
11 }
12 //中序遍历
13 void BinTree::in_order(BinTreeNode *r)const
14 {
15     BinTreeNode *pTmpNode = r;
16     if(pTmpNode != NULL)
17     {
18         in_order(pTmpNode->get_left());
19         cout<<pTmpNode->get_data()<<" ";
20         in_order(pTmpNode->get_right());
21     }
22 }
23 //后序遍历
24 void BinTree::post_order(BinTreeNode *r)const
25 {
26     BinTreeNode *pTmpNode = r;
27     if(pTmpNode != NULL)
28     {
29         post_order(pTmpNode->get_left());
30         post_order(pTmpNode->get_right());
31         cout<<pTmpNode->get_data()<<" ";
32     }
33 }

 

复制代码

2.3 层次遍历

层次遍历也是二叉树遍历的一种方式,二叉树的层次遍历更像是一种广度优先搜索(BFS)。因此二叉树的层次遍历利用队列来完成是最好不过啦,当然不是说利用别的数据结构不能完成。

复制代码
1 //层次遍历
 2 void BinTree::level_order(BinTreeNode *r)const
 3 {
 4     if(r == NULL)
 5         return;
 6     deque<BinTreeNode*> q;
 7     q.push_back(r);
 8     while(!q.empty())
 9     {
10         BinTreeNode *pTmpNode = q.front();
11         cout<<pTmpNode->get_data()<<" ";
12         q.pop_front();
13         if(pTmpNode->get_left() != NULL)
14         {
15             q.push_back(pTmpNode->get_left());
16         }
17         if(pTmpNode->get_right() != NULL)
18         {
19             q.push_back(pTmpNode->get_right());
20         }
21     }
22 }

 

复制代码

2.4 求二叉树中叶子节点的个数

树中的叶子节点的个数 = 左子树中叶子节点的个数 + 右子树中叶子节点的个数。利用递归代码也是相当的简单,易懂。

复制代码
1 //获取叶子节点的个数
 2 int BinTree::get_leaf_num(BinTreeNode *r)const
 3 {
 4     if(r == NULL)//该节点是空节点,比如建树时候用'#'表示
 5     {
 6         return 0;
 7     }
 8     if(r->get_left()==NULL && r->get_right()==NULL)//该节点并不是空的,但是没有孩子节点
 9     {
10         return 1;
11     }
12     //递归整个树的叶子节点个数 = 左子树叶子节点的个数 + 右子树叶子节点的个数
13     return get_leaf_num(r->get_left()) + get_leaf_num(r->get_right());
14 }

 

复制代码

2.5 求二叉树的高度

求二叉树的高度也是非常简单,不用多说:树的高度 = max(左子树的高度,右子树的高度) + 1 。

复制代码
1 //获得二叉树的高度
 2 int BinTree::get_tree_height(BinTreeNode *r)const
 3 {
 4     if(r == NULL)//节点本身为空
 5     {
 6         return 0;
 7     }
 8     if(r->get_left()==NULL && r->get_right()==NULL)//叶子节点
 9     {
10         return 1;
11     }
12     int l_height = get_tree_height(r->get_left());
13     int r_height = get_tree_height(r->get_right());
14     return l_height >= r_height ? l_height + 1 : r_height + 1; 
15 }

 

复制代码

2.6 交换二叉树的左右儿子

交换二叉树的左右儿子,可以先交换根节点的左右儿子节点,然后递归以左右儿子节点为根节点继续进行交换。树中的操作有先天的递归性。。

复制代码
1 //交换二叉树的左右儿子
 2 void BinTree::swap_left_right(BinTreeNode *r)
 3 {
 4     if(r == NULL)
 5     {
 6         return;
 7     }
 8     BinTreeNode *pTmpNode = r->get_left();
 9     r->set_left(r->get_right());
10     r->set_right(pTmpNode);
11     swap_left_right(r->get_left());
12     swap_left_right(r->get_right());
13 }

 

复制代码

2.7 判断一个节点是否在一颗子树中

可以和当前根节点相等,也可以在左子树或者右子树中。

复制代码
1 //判断一个节点t是否在以r为根的子树中
 2 bool BinTree::is_in_tree(BinTreeNode *r,BinTreeNode *t)const
 3 {
 4     if(r == NULL)
 5     {
 6         return false;
 7     }
 8     else if(r == t)
 9     {
10         return true;
11     }
12     else
13     {
14         bool has = false;
15         if(r->get_left() != NULL)
16         {
17             has = is_in_tree(r->get_left(),t);
18         }
19         if(!has && r->get_right()!= NULL)
20         {
21             has = is_in_tree(r->get_right(),t);
22         }
23         return has;
24     }
25 }

 

复制代码

2.8 求两个节点的最近公共祖先

求两个节点的公共祖先可以用到上面的:判断一个节点是否在一颗子树中。(1)如果两个节点同时在根节点的右子树中,则最近公共祖先一定在根节点的右子树中。(2)如果两个节点同时在根节点的左子树中,则最近公共祖先一定在根节点的左子树中。(3)如果两个节点一个在根节点的右子树中,一个在根节点的左子树中,则最近公共祖先一定是根节点。当然,要注意的是:可能一个节点pNode1在以另一个节点pNode2为根的子树中,这时pNode2就是这两个节点的最近公共祖先了。显然这也是一个递归的过程啦:

复制代码
 1 //求两个节点的最近公共祖先
 2 BinTreeNode* BinTree::get_nearest_common_father(BinTreeNode *r,BinTreeNode *pNode1,BinTreeNode *pNode2)const
 3 {
 4     //pNode2在以pNode1为根的子树中(每次递归都要判断,放在这里不是很好。)
 5     if(is_in_tree(pNode1,pNode2))
 6     {
 7         return pNode1;
 8     }
 9     //pNode1在以pNode2为根的子树中
10     if(is_in_tree(pNode2,pNode1))
11     {
12         return pNode2;
13     }
14     bool one_in_left,one_in_right,another_in_left,another_in_right;
15     one_in_left = is_in_tree(r->get_left(),pNode1);
16     another_in_right = is_in_tree(r->get_right(),pNode2);
17     another_in_left = is_in_tree(r->get_left(),pNode2);
18     one_in_right = is_in_tree(r->get_right(),pNode1);
19     if((one_in_left && another_in_right) || (one_in_right && another_in_left))
20     {
21         return r;
22     }
23     else if(one_in_left && another_in_left)
24     {
25         return get_nearest_common_father(r->get_left(),pNode1,pNode2);
26     }
27     else if(one_in_right && another_in_right)
28     {
29         return get_nearest_common_father(r->get_right(),pNode1,pNode2);
30     }
31     else
32     {
33         return NULL;
34     }
35 }

 

复制代码

可以看到这种做法,进行了大量的重复搜素,其实有另外一种做法,那就是存储找到这两个节点的过程中经过的所有节点到两个容器中,然后遍历这两个容器,第一个不同的节点的父节点就是我们要找的节点啦。 实际上这还是采用了空间换时间的方法。

2.9 从根节点开始找到所有路径,使得路径上的节点值和为某一数值(路径不一定以叶子节点结束)

这道题要找到所有的路径,显然是用深度优先搜索(DFS)啦。但是我们发现DFS所用的栈和输出路径所用的栈应该不是一个栈,栈中的数据是相反的。看看代码:注意使用的两个栈。

复制代码
 1 //注意这两个栈的使用
 2 stack<BinTreeNode *>dfs_s;
 3 stack<BinTreeNode *>print_s;
 4 //打印出从r开始的和为sum的所有路径
 5 void BinTree::print_rout(BinTreeNode *r,int sum)const
 6 {
 7     if(r == NULL)
 8     {
 9         return;
10     }
11     //入栈
12     sum -= r->get_data();
13     dfs_s.push(r);
14     if(sum <= 0)
15     {
16         if(sum == 0)
17         {
18             while(!dfs_s.empty())
19             {
20                 print_s.push(dfs_s.top());
21                 dfs_s.pop();
22             }
23             while(!print_s.empty())
24             {
25                 cout<<print_s.top()->get_data()<<" ";
26                 dfs_s.push(print_s.top());
27                 print_s.pop();
28             }
29             cout<<endl;
30         }
31         sum += r->get_data();
32         dfs_s.pop();
33         return;
34     }
35     //递归进入左子树
36     print_rout(r->get_left(),sum);
37     //递归进入右子树
38     print_rout(r->get_right(),sum);
39     //出栈
40     sum += r->get_data();
41     dfs_s.pop();
42 }

 

复制代码

 

最后,给出一点测试代码:

 1 int main()
 2 {
 3     BinTree tree;
 4     /*--------------------------------------------------------------------------*/
 5     cout<<"请输入二叉树前序序列进行建树,'#'代表空节点:"<<endl;
 6     tree.set_root(tree.create_tree());
 7     cout<<endl;
 8     /*--------------------------------------------------------------------------*/
 9     cout<<"前序遍历的结果:";
10     tree.pre_order(tree.get_root());
11     cout<<endl<<endl;
12     /*--------------------------------------------------------------------------*/
13     cout<<"中序遍历的结果:";
14     tree.in_order(tree.get_root());
15     cout<<endl<<endl;
16     /*--------------------------------------------------------------------------*/
17     cout<<"后序遍历的结果:";
18     tree.post_order(tree.get_root());
19     cout<<endl<<endl;
20     /*--------------------------------------------------------------------------*/
21     cout<<"层次遍历的结果:";
22     tree.level_order(tree.get_root());
23     cout<<endl<<endl;
24     /*--------------------------------------------------------------------------*/
25     cout<<"该二叉树叶子节点的个数:";
26     cout<<tree.get_leaf_num(tree.get_root())<<endl<<endl;
27     /*--------------------------------------------------------------------------*/
28     cout<<"该二叉树的高度是:";
29     cout<<tree.get_tree_height(tree.get_root())<<endl<<endl;
30     /*--------------------------------------------------------------------------*/
31     tree.swap_left_right(tree.get_root());
32     cout<<"交换左右子树之后的先序遍历结果为:";
33     tree.pre_order(tree.get_root());
34     cout<<endl<<endl;
35     /*--------------------------------------------------------------------------*/
36     BinTreeNode *p1 = tree.get_root()->get_left()->get_right();
37     BinTreeNode *p2 = tree.get_root()->get_left()->get_left();
38     BinTreeNode *p3 = tree.get_root()->get_right()->get_right()->get_right();
39     cout<<p1->get_data()<<" 和 "<<p2->get_data()<<"的最近公共祖先是:";
40     BinTreeNode *p = tree.get_nearest_common_father(tree.get_root(),p1,p2);
41     cout<<p->get_data()<<endl;
42     cout<<p1->get_data()<<" 和 "<<p3->get_data()<<"的最近公共祖先是:";
43     p = tree.get_nearest_common_father(tree.get_root(),p1,p3);
44     cout<<p->get_data()<<endl<<endl;
45     /*--------------------------------------------------------------------------*/
46     cout<<"路径如下:"<<endl;
47     tree.print_rout(tree.get_root(),12);
48     return 0;
49 }

 

Leave a Reply

Your email address will not be published. Required fields are marked *