c++创建二叉树_从零开始学习数据结构>树、森林与二叉树的转换

1、树、森林为什么向二叉树转换？ 因为在实际的处理问题中，大多数情况都是一对多，就像树、森林这样的数据结构！ 而对于二叉树我们已经很熟悉了，所以就转向我们所熟悉的结构，比较容易处理。 2、孩子兄弟树的方法 把握 左孩子右兄弟 的原则： (1)、树与二叉树的转换 i>以树的根结点为二叉树的根节点； ii>左孩 子指针指向该根节点的第一个子结点； iii>右 孩子指针指向"兄弟结点"。 (2)、二叉树表示森林 i>二叉树的根结点是森林中第一棵树的根结点； ii>根结点的右孩 子为森林中其它树的根结点。 3、图形表示法 4、树的创建----->转化二叉树 应具有的存储结构：树结点和树。

 1template<typename Type> 2class TreeNode{ 3    friend class Tree; 4public: 5    TreeNode() : data(Type()), firstChild(NULL), nextSibling(NULL){} 6    TreeNode(Type d, TreeNode *first = NULL, TreeNode *next = NULL) : 7    data(d), firstChild(first), nextSibling(next){} 8    ~TreeNode(){} 9private:10    Type data;11    TreeNode *firstChild;  //第一个孩子12    TreeNode *nextSibling; //下一个兄弟13};1415template<typename Type>16class Tree{17public:18    Tree() : root(NULL){}19    Tree(Type ref) : root(NULL), refval(ref){}20    ~Tree(){}21private:22    TreeNode *root;23    Type           refval; //'#'24};

5、实现的方法

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

(1)、创建树(化二叉树)----->在我们的思想中就是二叉树的创建； (2)、求结点个数--->根二叉树的一样； (3)、查找当前结点----->跟二叉树一样。 (4)、求树高(森林的也可以求出)

 1    int height(TreeNode *t)const{ 2        TreeNode *p; 3        int m; 4        int max = 0; 5 6        if(t == NULL){ 7            return 0;  //空树，高0 8        }else if(t->firstChild == NULL){ 9            return 1;  //只有根，为110        }else{11            p = t->firstChild; //先为第一个孩子12            while(p != NULL){13                m = height(p); //求高14                if(max 15                    max = m;   //遍历所有的分支，每次求最高的16                }17                p = p->nextSibling;  //每次往右分支走,但还是求的左边树高;18            }19            return max+1;  //返回时加上根的高度20        }21    }

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

 1    TreeNode* parent(TreeNode *t, TreeNode *cur)const{ 2        if(t == NULL || cur == NULL || t == cur){  //父为NULL 3            return NULL; 4        } 5        TreeNode *p = t->firstChild; 6        while(p != NULL && p != cur){ 7            TreeNode *tmp = parent(p, cur); //递归查找其父结点，将找的结果给了tmp; 8            if(tmp != NULL){ 9                return tmp;10            }11            p = p->nextSibling;  //在往右找12        }13        if(p != NULL && p == cur){14            return t;       //找到了15        }else{16            return NULL;17        }18    }

6、全部代码、测试代码，测试结果 (1)、因为方法比较少，所以都在类内实现

  1#ifndef _TREE_H_  2#define _TREE_H_  3  4#include  5using namespace std;  6  7template<typename Type>  8class Tree;  9 10template<typename Type> 11class TreeNode{ 12    friend class Tree; 13public: 14    TreeNode() : data(Type()), firstChild(NULL), nextSibling(NULL){} 15    TreeNode(Type d, TreeNode *first = NULL, TreeNode *next = NULL) : 16    data(d), firstChild(first), nextSibling(next){} 17    ~TreeNode(){} 18private: 19    Type data; 20    TreeNode *firstChild; 21    TreeNode *nextSibling; 22}; 23 24template<typename Type> 25class Tree{ 26public: 27    Tree() : root(NULL){} 28    Tree(Type ref) : root(NULL), refval(ref){} 29    ~Tree(){} 30public: 31    void createTree(const char *str){ 32        createTree(root, str); 33    } 34    int size()const{ 35        return size(root); 36    } 37    int height()const{ 38        return height(root); 39    } 40    TreeNode* root_1()const{ 41        return root; 42    } 43    bool isEmpty()const{ 44        return root == NULL; 45    } 46    TreeNode *firstChild()const{ 47        if(root != NULL){ 48            return root->firstChild; 49        } 50        return NULL; 51    } 52    TreeNode *nextSibling()const{ 53        if(root != NULL){ 54            return root->nextSibling; 55        } 56        return NULL; 57    } 58    TreeNode* find(const Type &key)const{ 59        return find(root, key); 60    }  61    TreeNode* parent(TreeNode *cur)const{ 62        return parent(root, cur); 63    } 64protected: 65    void createTree(TreeNode *&t, const char *&str){ 66        if(*str == refval){ 67            t = NULL; 68        }else{ 69            t = new TreeNode(*str); 70            createTree(t->firstChild, ++str); 71            createTree(t->nextSibling, ++str); 72        } 73    } 74    int size(TreeNode *t)const{ 75        if(t == NULL){ 76            return 0; 77        } 78        return size(t->firstChild) + size(t->nextSibling) + 1; 79    } 80    TreeNode* parent(TreeNode *t, TreeNode *cur)const{ 81        if(t == NULL || cur == NULL || t == cur){ 82            return NULL; 83        } 84        TreeNode *p = t->firstChild; 85        while(p != NULL && p != cur){ 86            TreeNode *tmp = parent(p, cur); 87            if(tmp != NULL){ 88                return tmp; 89            } 90            p = p->nextSibling; 91        } 92        if(p != NULL && p == cur){ 93            return t; 94        }else{ 95            return NULL; 96        } 97    } 98    TreeNode* find(TreeNode *t, const Type &key)const{ 99        if(t == NULL){100            return NULL;101        }102        if(t->data == key){103            return t;104        }105        TreeNode* p  = find(t->firstChild, key);106        if(p != NULL){107            return p;108        }109        return find(t->nextSibling, key);110    }111    int height(TreeNode *t)const{112        TreeNode *p;113        int m;114        int max = 0;115116        if(t == NULL){117            return 0;118        }else if(t->firstChild == NULL){119            return 1;120        }else{121            p = t->firstChild;122            while(p != NULL){123                m = height(p);124                if(max 125                    max = m;126                }127                p = p->nextSibling;128            }129            return max+1;130        }131    }132private:133    TreeNode *root;134    Type           refval;  //'#'135};136137#endif

(2)、测试代码

 1#include"tree.h" 2 3int main(void){ 4    char *str = "RAD#E##B#CFG#H#K#####";  //先根序的二叉树序列; 5    Tree<char> t('#'); 6    t.createTree(str); 7    TreeNode<char> *p = t.find('C'); 8    TreeNode<char> *q = t.parent(p); 9    TreeNode<char> *m = t.find('R');10    printf("%p %p\n", q, m);11    cout<endl;12    cout<endl;1314    return 0;15}

(3)、测试结果        推荐阅读： 从零开始学习数据结构-->入门篇 从零开始学习数据结构-->链表 从零开始学习数据结构-->线性表 从零开始学习数据结构-->栈 从零开始学习数据结构-->队列 从零开始学习数据结构-->矩阵+串 从零开始学习数据结构-->哈希表 从零开始学习数据结构-->散列桶 从零开始学习数据结构-->二叉树

从零开始学习数据结构-->二叉树方法实现

从零开始学习数据结构-->线索二叉树