您好,登錄后才能下訂單哦!
1、樹、森林為什么向二叉樹轉(zhuǎn)換?
因為在實際的處理問題中,大多數(shù)情況都是一對多,就向樹、森林這樣的數(shù)據(jù)結(jié)構(gòu)!
而對于二叉樹我們已經(jīng)很熟悉了,所以轉(zhuǎn)向我們所熟悉的結(jié)構(gòu),好處理。
2、孩子兄弟樹的方法
把握左孩子右兄弟的原則:
(1)、樹與二叉樹的轉(zhuǎn)換:
i>以樹的根結(jié)點為二叉樹的根節(jié)點;
ii>左孩子指針指向該根節(jié)點的第一個子結(jié)點;
iii>右孩子指針指向"兄弟結(jié)點"
(2)、二叉樹表示森林:
i>二叉樹的根結(jié)點是森林中第一棵樹的根結(jié)點
ii>根結(jié)點的右孩子為森林中其它樹的根結(jié)點
3、圖形表示法
4、樹的創(chuàng)建----->化二叉樹
應具有的存儲結(jié)構(gòu):樹結(jié)點和樹
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、應該實現(xiàn)的方法:
public: void createTree(const char *str); //創(chuàng)建樹 int size()const; //求樹的結(jié)點個數(shù) int height()const; //求樹高 TreeNode<Type>* root_1()const; //返回根結(jié)點 bool isEmpty()const; //判樹空 TreeNode<Type> *firstChild()const; //返回第一個孩子結(jié)點 TreeNode<Type> *nextSibling()const; //返回第一個兄弟結(jié)點 TreeNode<Type>* find(Type key)const; //查找當前結(jié)點 TreeNode<Type>* parent(TreeNode<Type> *cur)const; //查找當前結(jié)點的父
(1)、創(chuàng)建樹(化二叉樹)----->在我們的思想中就是二叉樹的創(chuàng)建。
(2)、求結(jié)點個數(shù)--->根二叉樹的一樣
(3)、查找當前結(jié)點----->跟二叉樹一樣
(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)、查找當前結(jié)點的父(自己畫圖多多跟蹤)
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); //遞歸查找其父結(jié)點,將找的結(jié)果給了tmp; if(tmp != NULL){ return tmp; } p = p->nextSibling; //在往右找 } if(p != NULL && p == cur){ return t; //找到了 }else{ return NULL; } }
6、全部代碼、測試代碼,測試結(jié)果
(1)、因為少,所以都在類內(nèi)實現(xiàn):
#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)、測試結(jié)果
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權內(nèi)容。