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

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

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

2、孩子兄弟树的方法

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

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

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

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

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

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

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

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

3、图形表示法

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

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

template<typenameType>classTreeNode{friendclassTree<Type>;public:TreeNode():data(Type()),firstChild(NULL),nextSibling(NULL){}TreeNode(Typed,TreeNode*first=NULL,TreeNode*next=NULL):data(d),firstChild(first),nextSibling(next){}~TreeNode(){}private:Typedata;TreeNode*firstChild;//第一个孩子TreeNode*nextSibling;//下一个兄弟};template<typenameType>classTree{public:Tree():root(NULL){}Tree(Typeref):root(NULL),refval(ref){}~Tree(){}private:TreeNode<Type>*root;Typerefval;//'#'};

5、应该实现的方法：

public：voidcreateTree(constchar*str);//创建树intsize()const;//求树的结点个数intheight()const;//求树高TreeNode<Type>*root_1()const;//返回根结点boolisEmpty()const;//判树空TreeNode<Type>*firstChild()const;//返回第一个孩子结点TreeNode<Type>*nextSibling()const;//返回第一个兄弟结点TreeNode<Type>*find(Typekey)const;//查找当前结点TreeNode<Type>*parent(TreeNode<Type>*cur)const;//查找当前结点的父

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

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

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

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

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

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

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

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

(1)、因为少，所以都在类内实现：

#ifndef_TREE_H_#define_TREE_H_#include<iostream>usingnamespacestd;template<typenameType>classTree;template<typenameType>classTreeNode{friendclassTree<Type>;public:TreeNode():data(Type()),firstChild(NULL),nextSibling(NULL){}TreeNode(Typed,TreeNode*first=NULL,TreeNode*next=NULL):data(d),firstChild(first),nextSibling(next){}~TreeNode(){}private:Typedata;TreeNode*firstChild;TreeNode*nextSibling;};template<typenameType>classTree{public:Tree():root(NULL){}Tree(Typeref):root(NULL),refval(ref){}~Tree(){}public:voidcreateTree(constchar*str){createTree(root,str);}intsize()const{returnsize(root);}intheight()const{returnheight(root);}TreeNode<Type>*root_1()const{returnroot;}boolisEmpty()const{returnroot==NULL;}TreeNode<Type>*firstChild()const{if(root!=NULL){returnroot->firstChild;}returnNULL;}TreeNode<Type>*nextSibling()const{if(root!=NULL){returnroot->nextSibling;}returnNULL;}TreeNode<Type>*find(constType&key)const{returnfind(root,key);}TreeNode<Type>*parent(TreeNode<Type>*cur)const{returnparent(root,cur);}protected:voidcreateTree(TreeNode<Type>*&t,constchar*&str){if(*str==refval){t=NULL;}else{t=newTreeNode<Type>(*str);createTree(t->firstChild,++str);createTree(t->nextSibling,++str);}}intsize(TreeNode<Type>*t)const{if(t==NULL){return0;}returnsize(t->firstChild)+size(t->nextSibling)+1;}TreeNode<Type>*parent(TreeNode<Type>*t,TreeNode<Type>*cur)const{if(t==NULL||cur==NULL||t==cur){returnNULL;}TreeNode<Type>*p=t->firstChild;while(p!=NULL&&p!=cur){TreeNode<Type>*tmp=parent(p,cur);if(tmp!=NULL){returntmp;}p=p->nextSibling;}if(p!=NULL&&p==cur){returnt;}else{returnNULL;}}TreeNode<Type>*find(TreeNode<Type>*t,constType&key)const{if(t==NULL){returnNULL;}if(t->data==key){returnt;}TreeNode<Type>*p=find(t->firstChild,key);if(p!=NULL){returnp;}returnfind(t->nextSibling,key);}intheight(TreeNode<Type>*t)const{TreeNode<Type>*p;intm;intmax=0;if(t==NULL){return0;}elseif(t->firstChild==NULL){return1;}else{p=t->firstChild;while(p!=NULL){m=height(p);if(max<m){max=m;}p=p->nextSibling;}returnmax+1;}}private:TreeNode<Type>*root;Typerefval;//'#'};#endif

(2)、测试代码：

#include"tree.h"intmain(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;return0;}

(3)、测试结果