c++简单实现二叉树

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

专业术语：

节点父节点根节点子孙堂兄弟

深度：

从根节点到最底层节点的层数称为深度

叶子节点：

没有子节点的节点称为叶子节点

非终端节点：

实际就是非叶子节点

度：

子节点的个数称为度

树的分类：

一般树

任意一个节点的子节点个数都不受限制

二叉树

任意一个节点的子节点的个数最多是两个且子节点的位置不可更改

分类：

一般二叉树

满二叉树

在不添加树的层数的情况下每个子节点都满了不能再多一个节点

完全二叉树

如果只删除了满二叉树最底层最右边的连续若干个节点这样形成的二叉树就是完全二叉树

满二叉树是完全二叉树的一个特例完全二叉树包含满二叉树

森林

N个互不相交的树的集合

树的存储：

二叉树的存储

连续存储[完全二叉树] 数组存储方式

优点查找某个父节点和子节点（包括判断有无子节点）速度很快

缺点很耗费内存空间

链式存储[链表存储]

一般树的存储

双亲表示法

求父节点方便

孩子表示法

求子节点方便

双亲孩子表示法

求父节点子节点都方便

二叉树表示法

一般树转二叉树来存储具体转换方法：

设法保证任意一个节点左指针域指向它的第一个孩子节点

右指针域指向它的下一个兄弟节点

只要满足此条件就能把普通树转换成二叉树

一个普通的树转换成二叉树一定没有右子树

森林的存储

和一般树转换二叉树一样

树的操作：

二叉树每个子节点可以没有子节点如果有最多是2个

二叉树遍历分为三种

中序遍历

左根右-----（先遍历左子树-然后是根节点-再然后遍历右子树）

前序遍历

根左右-----（先遍历跟节点-然后是左子树-再然后遍历右子树）

后序遍历

左右根-----（先遍历左子树-然后是右子树-再然后遍历根节点）

已知两种遍历求原始二叉树

通过先中后中两种遍历可以推算二叉树的原始二叉树

通过先后遍历无法还原原始二叉树

  1 #ifndef __MYBTREE_H__
  2 #define __MYBTREE_H__
  3 #include <Windows.h>
  4 class Monster                                    
  5     {                                    
  6     public:                                    
  7         int ID;                                
  8         int Level;                                
  9         char Name[20];                                
 10     public:                                    
 11         Monster(){}                                
 12         Monster(int ID,int Level,char* Name)                                
 13         {                                
 14             this->ID = ID;                            
 15             this->Level = Level;                            
 16             memcpy(&this->Name,Name,strlen(Name)+1);                            
 17         }                                
 18     };                                    
 19                                         
 20     template<class T>                                    
 21     class TreeNode{                                    
 22     public:                                    
 23         T element;                    //当前节点存储的数据            
 24         TreeNode<T>* pLeft;                    //指向左子节点的指针            
 25         TreeNode<T>* pRight;                    //指向右子节点的指针            
 26                                         
 27         TreeNode(T& ele){                                
 28             //初始化Node节点                            
 29             memset(&element,0,sizeof(TreeNode));                            
 30             //为元素赋值                            
 31             memcpy(&element,&ele,sizeof(T));                            
 32             pLeft = pRight = NULL;                            
 33         }                                
 34     };                                    
 35                                         
 36     template<class T>                                    
 37     class BSortTree{                                    
 38     public:                                    
 39         BSortTree();                    //构造函数            
 40         ~BSortTree();                    //析构函数            
 41     public:                                    
 42         void InOrderTraverse(TreeNode<T>* pNode);                    //中序遍历            
 43         void PreOrderTraverse(TreeNode<T>* pNode);                    //前序遍历            
 44         void PostOrderTraverse(TreeNode<T>* pNode);                    //后序遍历            
 45         TreeNode<T>* GetRoot();                    //返回根节点            
 46         int GetDepth(TreeNode<T>* pNode);                    //返回某个节点的高度/深度    
 47         void clear(TreeNode<T>* pNode);        //清空所有节点
 48     private:                                    
 49         void Init();                                
 50     private:                                    
 51         TreeNode<T>* m_pRoot;                    //根结点指针            
 52         int size;                    //树中元素总个数            
 53     };                                    
 54                                         
 55     template<class T>                                     
 56     BSortTree<T>::BSortTree()                                    
 57     {                                    
 58         Init();                                
 59     }                                    
 60     template<class T>                                     
 61     BSortTree<T>::~BSortTree(){                                    
 62                                         
 63         //释放所以节点空间        
 64         if (NULL != m_pRoot)
 65         {
 66             clear(m_pRoot);
 67         }
 68                                     
 69     }                                    
 70     template<class T>
 71     void BSortTree<T>::clear(TreeNode<T>* pNode)        //清空所有节点
 72     {
 73         if (NULL != pNode)
 74         {
 75             clear(pNode->pLeft);
 76             clear(pNode->pRight);
 77             delete pNode;
 78             pNode = NULL;
 79         }
 80     }
 81     template<class T>                                     
 82     void BSortTree<T>::Init()                                    
 83     {                                    
 84                                         
 85         Monster m1(1,1,"刺猬");                                
 86         Monster m2(2,2,"野狼");                                
 87         Monster m3(3,3,"野猪");                                
 88         Monster m4(4,4,"士兵");                                
 89         Monster m5(5,5,"火龙");                                
 90         Monster m6(6,6,"独角兽");                                
 91         Monster m7(7,7,"江湖大盗");                                
 92                                         
 93                                         
 94         TreeNode<Monster>* n1 = new TreeNode<Monster>(m1);                                
 95         TreeNode<Monster>* n2 = new TreeNode<Monster>(m2);                                
 96         TreeNode<Monster>* n3 = new TreeNode<Monster>(m3);                                
 97         TreeNode<Monster>* n4 = new TreeNode<Monster>(m4);                                
 98         TreeNode<Monster>* n5 = new TreeNode<Monster>(m5);                                
 99         TreeNode<Monster>* n6 = new TreeNode<Monster>(m6);                                
100         TreeNode<Monster>* n7 = new TreeNode<Monster>(m7);                                
101                                         
102         m_pRoot = n5;                                
103         n5->pLeft = n4;                                
104         n5->pRight = n6;                                
105         n4->pLeft = n1;                                
106         n1->pRight = n2;                                
107         n6->pLeft = n3;                                
108         n3->pRight = n7;                                
109         size = 7;                                
110         /*                                
111                         5                
112                                         
113                     4        6            
114                                         
115                 1            3                
116                                         
117                      2                7                
118                                         
119         */                                
120     }                                    
121     template<class T>                                     
122     TreeNode<T>* BSortTree<T>::GetRoot()                                    
123     {                                    
124         return m_pRoot;                                
125     }                                    
126     template<class T>                                    
127     int BSortTree<T>::GetDepth(TreeNode<T>* pNode)                                    
128     {                                    
129          if(pNode==NULL)                                     
130         {                                    
131         return 0;                                  
132         }                                    
133         else                                      
134         {                                      
135             int m = GetDepth(pNode->pLeft);                                      
136             int n = GetDepth(pNode->pRight);                                      
137             return (m > n) ? (m+1) : (n+1);                                       
138         }                                      
139     }                                    
140     template<class T>                                     
141     void BSortTree<T>::InOrderTraverse(TreeNode<T>* pNode)                                    
142     {
143         //中序遍历所有怪物,列出怪的名字                                
144         if (NULL != pNode)
145         {
146             InOrderTraverse(pNode->pLeft);
147             printf("%s--%d\r\n",((Monster)pNode->element).Name,((Monster)pNode->element).ID);
148             InOrderTraverse(pNode->pRight);
149         }
150                                         
151                                         
152     }                                    
153                                         
154     template<class T>                                     
155     void BSortTree<T>::PreOrderTraverse(TreeNode<T>* pNode)                                    
156     {                                    
157                                         
158         //前序遍历所有怪物,列出怪的名字    
159         if (NULL != pNode)
160         {
161             printf("%s--%d\r\n",((Monster)pNode->element).Name,((Monster)pNode->element).ID);
162             PreOrderTraverse(pNode->pLeft);
163             PreOrderTraverse(pNode->pRight);
164 
165         }
166                                         
167     }                                    
168                                         
169     template<class T>                                     
170     void BSortTree<T>::PostOrderTraverse(TreeNode<T>* pNode)                                    
171     {                                    
172                                         
173         //后序遍历所有怪物,列出怪的名字        
174         if (NULL != pNode)
175         {
176             PostOrderTraverse(pNode->pLeft);
177             PostOrderTraverse(pNode->pRight);
178             printf("%s--%d\r\n",((Monster)pNode->element).Name,((Monster)pNode->element).ID);
179 
180         }
181                                         
182     }                                    
183 #endif    //__MYBTREE_H__

调用的例子

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include "MyBTree.h"
 4 #include <stack>
 5 int main(void)
 6 {
 7     Stack<BSortTree> 
 8     
 9     BSortTree<Monster>* P =new BSortTree<Monster>();
10     P->InOrderTraverse(P->GetRoot());
11     printf("-----------------------\r\n");
12     P->PreOrderTraverse(P->GetRoot());
13     printf("-----------------------\r\n");
14     P->PostOrderTraverse(P->GetRoot());
15     delete P;
16     system("pause");
17     return 0;
18 }