1、樹、森林為什么向二叉樹轉(zhuǎn)換？
創(chuàng)新互聯(lián)專注骨干網(wǎng)絡(luò)服務(wù)器租用十年，服務(wù)更有保障！服務(wù)器租用，
成都多線機(jī)房 成都服務(wù)器租用，成都服務(wù)器托管，骨干網(wǎng)絡(luò)帶寬，享受低延遲，高速訪問。靈活、實(shí)現(xiàn)低成本的共享或公網(wǎng)數(shù)據(jù)中心高速帶寬的專屬高性能服務(wù)器。
因?yàn)樵趯?shí)際的處理問題中，大多數(shù)情況都是一對(duì)多，就向樹、森林這樣的數(shù)據(jù)結(jié)構(gòu)！
而對(duì)于二叉樹我們已經(jīng)很熟悉了，所以轉(zhuǎn)向我們所熟悉的結(jié)構(gòu)，好處理。
2、孩子兄弟樹的方法
把握左孩子右兄弟的原則：
(1)、樹與二叉樹的轉(zhuǎn)換：
i>以樹的根結(jié)點(diǎn)為二叉樹的根節(jié)點(diǎn)；
ii>左孩子指針指向該根節(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn)；
iii>右孩子指針指向"兄弟結(jié)點(diǎn)"
(2)、二叉樹表示森林：
i>二叉樹的根結(jié)點(diǎn)是森林中第一棵樹的根結(jié)點(diǎn)
ii>根結(jié)點(diǎn)的右孩子為森林中其它樹的根結(jié)點(diǎn)
3、圖形表示法
4、樹的創(chuàng)建----->化二叉樹
應(yīng)具有的存儲(chǔ)結(jié)構(gòu)：樹結(jié)點(diǎn)和樹
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; //第一個(gè)孩子
TreeNode *nextSibling; //下一個(gè)兄弟
};
template
class Tree{
public:
Tree() : root(NULL){}
Tree(Type ref) : root(NULL), refval(ref){}
~Tree(){}
private:
TreeNode *root;
Type refval; //'#'
};
5、應(yīng)該實(shí)現(xiàn)的方法：
public：
void createTree(const char *str); //創(chuàng)建樹
int size()const; //求樹的結(jié)點(diǎn)個(gè)數(shù)
int height()const; //求樹高
TreeNode* root_1()const; //返回根結(jié)點(diǎn)
bool isEmpty()const; //判樹空
TreeNode *firstChild()const; //返回第一個(gè)孩子結(jié)點(diǎn)
TreeNode *nextSibling()const; //返回第一個(gè)兄弟結(jié)點(diǎn)
TreeNode* find(Type key)const; //查找當(dāng)前結(jié)點(diǎn)
TreeNode* parent(TreeNode *cur)const; //查找當(dāng)前結(jié)點(diǎn)的父
(1)、創(chuàng)建樹(化二叉樹)----->在我們的思想中就是二叉樹的創(chuàng)建。
(2)、求結(jié)點(diǎn)個(gè)數(shù)--->根二叉樹的一樣
(3)、查找當(dāng)前結(jié)點(diǎn)----->跟二叉樹一樣
(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; //先為第一個(gè)孩子
while(p != NULL){
m = height(p); //求高
if(max < m){
max = m; //遍歷所有的分支，每次求最高的
}
p = p->nextSibling; //每次往右分支走,但還是求的左邊樹高;
}
return max+1; //返回時(shí)加上根的高度
}
}
(5)、查找當(dāng)前結(jié)點(diǎn)的父(自己畫圖多多跟蹤)
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); //遞歸查找其父結(jié)點(diǎn)，將找的結(jié)果給了tmp;
if(tmp != NULL){
return tmp;
}
p = p->nextSibling; //在往右找
}
if(p != NULL && p == cur){
return t; //找到了
}else{
return NULL;
}
}
6、全部代碼、測(cè)試代碼，測(cè)試結(jié)果
(1)、因?yàn)樯?，所以都在類?nèi)實(shí)現(xiàn)：
#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)、測(cè)試代碼：
#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)、測(cè)試結(jié)果
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
名稱欄目：樹森林與二叉樹的轉(zhuǎn)換-創(chuàng)新互聯(lián)
標(biāo)題鏈接：http://weahome.cn/article/dpehci.html
重慶分公司
重慶分公司
