bl双性强迫侵犯h_国产在线观看人成激情视频_蜜芽188_被诱拐的少孩全彩啪啪漫画

樹森林與二叉樹的轉換

1、樹、森林為什么向二叉樹轉換？

創新互聯建站成立于2013年，是專業互聯網技術服務公司，擁有項目成都網站設計、做網站網站策劃，項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元尖扎做網站,已為上家服務,為尖扎各地企業和個人服務,聯系電話:13518219792

  因為在實際的處理問題中，大多數情況都是一對多，就向樹、森林這樣的數據結構！

而對于二叉樹我們已經很熟悉了，所以轉向我們所熟悉的結構，好處理。

2、孩子兄弟樹的方法

  把握左孩子右兄弟的原則：

  (1)、樹與二叉樹的轉換：

  i>以樹的根結點為二叉樹的根節點；

  ii>左孩子指針指向該根節點的第一個子結點；

  iii>右孩子指針指向"兄弟結點"

  (2)、二叉樹表示森林：

  i>二叉樹的根結點是森林中第一棵樹的根結點

  ii>根結點的右孩子為森林中其它樹的根結點

3、圖形表示法

樹 森林與二叉樹的轉換

4、樹的創建----->化二叉樹

  應具有的存儲結構：樹結點和樹

template<typename Type>
class TreeNode{
    friend class Tree<Type>;
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<typename Type>
class Tree{
public:
    Tree() : root(NULL){}
    Tree(Type ref) : root(NULL), refval(ref){}
    ~Tree(){}
private:
    TreeNode<Type> *root;
    Type           refval; //'#'
};

5、應該實現的方法：

public：
    void createTree(const char *str);  //創建樹
    int size()const;     //求樹的結點個數
    int height()const;   //求樹高
    TreeNode<Type>* root_1()const;  //返回根結點
    bool isEmpty()const;  //判樹空
    TreeNode<Type> *firstChild()const;  //返回第一個孩子結點
    TreeNode<Type> *nextSibling()const; //返回第一個兄弟結點
    TreeNode<Type>* find(Type key)const; //查找當前結點
    TreeNode<Type>* parent(TreeNode<Type> *cur)const;  //查找當前結點的父

  (1)、創建樹(化二叉樹)----->在我們的思想中就是二叉樹的創建。

  (2)、求結點個數--->根二叉樹的一樣

  (3)、查找當前結點----->跟二叉樹一樣

  (4)、求樹高(森林的也可以求出)：

    int height(TreeNode<Type> *t)const{
        TreeNode<Type> *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<Type>* parent(TreeNode<Type> *t, TreeNode<Type> *cur)const{
        if(t == NULL || cur == NULL || t == cur){  //父為NULL
            return NULL;
        }
        TreeNode<Type> *p = t->firstChild;
        while(p != NULL && p != cur){
            TreeNode<Type> *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<iostream>
using namespace std;

template<typename Type>
class Tree;

template<typename Type>
class TreeNode{
    friend class Tree<Type>;
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<typename Type>
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<Type>* root_1()const{
        return root;
    }
    bool isEmpty()const{
        return root == NULL;
    }
    TreeNode<Type> *firstChild()const{
        if(root != NULL){
            return root->firstChild;
        }
        return NULL;
    }
    TreeNode<Type> *nextSibling()const{
        if(root != NULL){
            return root->nextSibling;
        }
        return NULL;
    }
    TreeNode<Type>* find(const Type &key)const{
        return find(root, key);
    } 
    TreeNode<Type>* parent(TreeNode<Type> *cur)const{
        return parent(root, cur);
    }
protected:
    void createTree(TreeNode<Type> *&t, const char *&str){
        if(*str == refval){
            t = NULL;
        }else{
            t = new TreeNode<Type>(*str);
            createTree(t->firstChild, ++str);
            createTree(t->nextSibling, ++str);
        }
    }
    int size(TreeNode<Type> *t)const{
        if(t == NULL){
            return 0;
        }
        return size(t->firstChild) + size(t->nextSibling) + 1;
    }
    TreeNode<Type>* parent(TreeNode<Type> *t, TreeNode<Type> *cur)const{
        if(t == NULL || cur == NULL || t == cur){
            return NULL;
        }
        TreeNode<Type> *p = t->firstChild;
        while(p != NULL && p != cur){
            TreeNode<Type> *tmp = parent(p, cur);
            if(tmp != NULL){
                return tmp;
            }
            p = p->nextSibling;
        }
        if(p != NULL && p == cur){
            return t;
        }else{
            return NULL;
        }
    }
    TreeNode<Type>* find(TreeNode<Type> *t, const Type &key)const{
        if(t == NULL){
            return NULL;
        }
        if(t->data == key){
            return t;
        }
        TreeNode<Type>* p  = find(t->firstChild, key);
        if(p != NULL){
            return p;
        }
        return find(t->nextSibling, key);
    }
    int height(TreeNode<Type> *t)const{
        TreeNode<Type> *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<Type> *root;
    Type           refval;  //'#'
};

#endif

  (2)、測試代碼：

樹 森林與二叉樹的轉換

#include"tree.h"

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

  (3)、測試結果

樹 森林與二叉樹的轉換      

  

本文題目：樹森林與二叉樹的轉換
網站鏈接：http://vcdvsql.cn/article38/pdecpp.html

成都網站建設公司_創新互聯，為您提供網站導航、云服務器、營銷型網站建設、企業網站制作、網站收錄、商城網站

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯

搜索引擎優化