资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

树森林与二叉树的转换-创新互联

1、树、森林为什么向二叉树转换?

创新互联专注骨干网络服务器租用十年,服务更有保障!服务器租用,成都多线机房 成都服务器租用,成都服务器托管,骨干网络带宽,享受低延迟,高速访问。灵活、实现低成本的共享或公网数据中心高速带宽的专属高性能服务器。

 因为在实际的处理问题中,大多数情况都是一对多,就向树、森林这样的数据结构!

而对于二叉树我们已经很熟悉了,所以转向我们所熟悉的结构,好处理。

2、孩子兄弟树的方法

 把握左孩子右兄弟的原则:

 (1)、树与二叉树的转换:

 i>以树的根结点为二叉树的根节点;

 ii>左孩子指针指向该根节点的第一个子结点;

 iii>右孩子指针指向"兄弟结点"

 (2)、二叉树表示森林:

 i>二叉树的根结点是森林中第一棵树的根结点

  ii>根结点的右孩子为森林中其它树的根结点

3、图形表示法

树 森林与二叉树的转换

4、树的创建----->化二叉树

 应具有的存储结构:树结点和树

template
class TreeNode{
    friend class Tree;
public:
    TreeNode() : data(Type()), firstChild(NULL), nextSibling(NULL){}
    TreeNode(Type d, TreeNode *first = NULL, TreeNode *next = NULL) :
    data(d), firstChild(first), nextSibling(next){}
    ~TreeNode(){}
private:
    Type data;
    TreeNode *firstChild;  //第一个孩子
    TreeNode *nextSibling; //下一个兄弟
};

template
class Tree{
public:
    Tree() : root(NULL){}
    Tree(Type ref) : root(NULL), refval(ref){}
    ~Tree(){}
private:
    TreeNode *root;
    Type           refval; //'#'
};

5、应该实现的方法:

public:
    void createTree(const char *str);  //创建树
    int size()const;     //求树的结点个数
    int height()const;   //求树高
    TreeNode* root_1()const;  //返回根结点
    bool isEmpty()const;  //判树空
    TreeNode *firstChild()const;  //返回第一个孩子结点
    TreeNode *nextSibling()const; //返回第一个兄弟结点
    TreeNode* find(Type key)const; //查找当前结点
    TreeNode* parent(TreeNode *cur)const;  //查找当前结点的父

 (1)、创建树(化二叉树)----->在我们的思想中就是二叉树的创建。

 (2)、求结点个数--->根二叉树的一样

 (3)、查找当前结点----->跟二叉树一样

 (4)、求树高(森林的也可以求出):

    int height(TreeNode *t)const{
        TreeNode *p;
        int m;
        int max = 0;

        if(t == NULL){
            return 0;  //空树,高0
        }else if(t->firstChild == NULL){
            return 1;  //只有根,为1
        }else{
            p = t->firstChild; //先为第一个孩子
            while(p != NULL){
                m = height(p); //求高
                if(max < m){
                    max = m;   //遍历所有的分支,每次求最高的
                }
                p = p->nextSibling;  //每次往右分支走,但还是求的左边树高;
            }
            return max+1;  //返回时加上根的高度
        }
    }

 (5)、查找当前结点的父(自己画图多多跟踪)

    TreeNode* parent(TreeNode *t, TreeNode *cur)const{
        if(t == NULL || cur == NULL || t == cur){  //父为NULL
            return NULL;
        }
        TreeNode *p = t->firstChild;
        while(p != NULL && p != cur){
            TreeNode *tmp = parent(p, cur); //递归查找其父结点,将找的结果给了tmp;
            if(tmp != NULL){
                return tmp;
            }
            p = p->nextSibling;  //在往右找
        }
        if(p != NULL && p == cur){
            return t;       //找到了
        }else{
            return NULL;
        }
    }

6、全部代码、测试代码,测试结果

 (1)、因为少,所以都在类内实现:

#ifndef _TREE_H_
#define _TREE_H_

#include
using namespace std;

template
class Tree;

template
class TreeNode{
    friend class Tree;
public:
    TreeNode() : data(Type()), firstChild(NULL), nextSibling(NULL){}
    TreeNode(Type d, TreeNode *first = NULL, TreeNode *next = NULL) :
    data(d), firstChild(first), nextSibling(next){}
    ~TreeNode(){}
private:
    Type data;
    TreeNode *firstChild;
    TreeNode *nextSibling;
};

template
class Tree{
public:
    Tree() : root(NULL){}
    Tree(Type ref) : root(NULL), refval(ref){}
    ~Tree(){}
public:
    void createTree(const char *str){
        createTree(root, str);
    }
    int size()const{
        return size(root);
    }
    int height()const{
        return height(root);
    }
    TreeNode* root_1()const{
        return root;
    }
    bool isEmpty()const{
        return root == NULL;
    }
    TreeNode *firstChild()const{
        if(root != NULL){
            return root->firstChild;
        }
        return NULL;
    }
    TreeNode *nextSibling()const{
        if(root != NULL){
            return root->nextSibling;
        }
        return NULL;
    }
    TreeNode* find(const Type &key)const{
        return find(root, key);
    } 
    TreeNode* parent(TreeNode *cur)const{
        return parent(root, cur);
    }
protected:
    void createTree(TreeNode *&t, const char *&str){
        if(*str == refval){
            t = NULL;
        }else{
            t = new TreeNode(*str);
            createTree(t->firstChild, ++str);
            createTree(t->nextSibling, ++str);
        }
    }
    int size(TreeNode *t)const{
        if(t == NULL){
            return 0;
        }
        return size(t->firstChild) + size(t->nextSibling) + 1;
    }
    TreeNode* parent(TreeNode *t, TreeNode *cur)const{
        if(t == NULL || cur == NULL || t == cur){
            return NULL;
        }
        TreeNode *p = t->firstChild;
        while(p != NULL && p != cur){
            TreeNode *tmp = parent(p, cur);
            if(tmp != NULL){
                return tmp;
            }
            p = p->nextSibling;
        }
        if(p != NULL && p == cur){
            return t;
        }else{
            return NULL;
        }
    }
    TreeNode* find(TreeNode *t, const Type &key)const{
        if(t == NULL){
            return NULL;
        }
        if(t->data == key){
            return t;
        }
        TreeNode* p  = find(t->firstChild, key);
        if(p != NULL){
            return p;
        }
        return find(t->nextSibling, key);
    }
    int height(TreeNode *t)const{
        TreeNode *p;
        int m;
        int max = 0;

        if(t == NULL){
            return 0;
        }else if(t->firstChild == NULL){
            return 1;
        }else{
            p = t->firstChild;
            while(p != NULL){
                m = height(p);
                if(max < m){
                    max = m;
                }
                p = p->nextSibling;
            }
            return max+1;
        }
    }
private:
    TreeNode *root;
    Type           refval;  //'#'
};

#endif

 (2)、测试代码:

树 森林与二叉树的转换

#include"tree.h"

int main(void){
    char *str = "RAD#E##B#CFG#H#K#####";  //先根序的二叉树序列;
    Tree t('#');
    t.createTree(str);
    TreeNode *p = t.find('C');
    TreeNode *q = t.parent(p);
    TreeNode *m = t.find('R');
    printf("%p %p\n", q, m);
    cout<

 (3)、测试结果

树 森林与二叉树的转换

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


当前名称:树森林与二叉树的转换-创新互联
网页网址:http://cdkjz.cn/article/dpehci.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220