首页 > 代码库 > 二叉树的基本功能实现方法(C++)

二叉树的基本功能实现方法(C++)

假设:有一个n个元素的完全二叉树,为了使其成为满二叉树,补全没有孩子的节点是的除了叶节点所有节点都有两个孩子,即最低层皆为-1.

例1:

              1

         2          3  

      4     5     -1    6 

     -1  -1     -1  -1                -1   -1   

 

补全的节点赋值为-1,表示当前无节点,需转向别的子树。

 

step 1:首先,对于一棵二叉树,需定义一个节点的类模板:

包括:节点键值、左子树指针、右子树指针

template <typename T>class binaryTreeNode {public:    T element;    binaryTreeNode<T>* leftChild;    binaryTreeNode<T>* rightChild;        binaryTreeNode(){leftChild = NULL;rightChild = NULL;}};

step 2:如何创建一棵二叉树呢?根据链表的特性,成员变量为:节点指针类型的mRoot根节点。除此之外,还包括常见的成员函数:如 获取树的当前规模、获取树的深度、打印或输出树及销毁二叉树等操作。

技术分享
 1 template <typename T> 2 class binaryTree { 3 private: 4     binaryTreeNode<T>* mRoot;//树根 5      6      7     int getSize(binaryTreeNode<T>*); 8     int getHeight(binaryTreeNode<T>*); 9     10     void preOrder(binaryTreeNode<T>*);11     void inOrder(binaryTreeNode<T>*);12     void postOrder(binaryTreeNode<T>*);13     void distroy(binaryTreeNode<T>*&);14     binaryTreeNode<T>* AddNode(const T& key,int direction,binaryTreeNode<T>*& root);15     16 public:17     binaryTree();18     virtual ~binaryTree();19     binaryTreeNode<T>* Create();//递归的创建二叉树的节点20     void AddNode(const T& key,int direction);21     22     int getSize();//递归得到树的节点数目23     int getHeight();//递归得到树的高度24     25     //递归遍历26     void preOrder();//前序遍历27     void inOrder();//中序遍历28     void postOrder();//后序遍历29     30     //删除二叉树31     void distroy();32     33 };
View Code

 

>>首先,怎么在二叉树中插入节点呢?
可以想到的是,插入新节点的时候需要标明 插得是左孩子还是右孩子which,在哪一个父节点下插入where,及插入的键值是多少what,简单的来说,就是WWW问题

 1 template <typename T> 2 binaryTreeNode<T>* binaryTree<T>::AddNode(const T& key,int direction,binaryTreeNode<T>*& root) 3 { 4     if(direction == 0)//左孩子 5     { 6         if(root->leftChild == NULL){//找到对应的叶节点插入 7             root->leftChild = new binaryTreeNode<T>(key); 8         } 9         else{10             root->leftChild = AddNode(key, direction, root->leftChild);11         }12     }13     14     else//右孩子15     {16         if (root->rightChild == NULL) {//找到相应的叶节点插入17             root->rightChild = new binaryTreeNode<T>(key);18         }19         else{20             root->rightChild = AddNode(key, direction, root->rightChild);21         }22     }23     24     return root;25 }26 27 template <typename T>28 void binaryTree<T>::AddNode(const T& key,int direction)29 {30     AddNode(key, direction, mRoot);31 }

 

了解了这个思路后,可以不用一个个插入节点,用输入流的方式直接创建一棵树,如下程序:

 1 template <typename T> 2 binaryTreeNode<T>* binaryTree<T>::Create(){ 3      4     binaryTreeNode<T>* current = NULL; 5      6     T val; 7      8     cin >> val;//输入键值 9     10     if(val == -1)//标识当前子树为空,转向下一节点11     {12         return NULL;13     }14     15     else{//递归的创建左右子树16         current = new binaryTreeNode<T>;17         current->element = val;18         current->leftChild = Create();19         current->rightChild = Create();20         return current;21     }22 }

可以发现,-1是一个过渡标识,标明当前从递归左子树 转向 递归右子树。而上述创建程序是一个前序遍历,所谓前序遍历是指:

  1.先访问父节点

  2.递归左子树

  3.递归右子树

时间复杂度是O(N),因为遍历了每一个节点。

 

>>创建了二叉树后,怎么销毁?其实只要一一删除每个节点即可,考虑到链表结构,我们不能使用下标去删除节点,只能一个个的访问,而二叉树典型的遍历方法有:前序遍历、中序遍历 及 后序遍历。在这里,我们使用后序遍历进行递归删除, 即自下而上的删除。

 1 /*二叉树的销毁操作:后序遍历删除 2  3 1)不能使用该声明:void distroy(binaryTreeNode<T>* pNode);该声明会创建一个局部的临时对象来保存传递的指针 4 虽然实参指针和局部指针都执行同一块堆空间,delete局部指针也会删除二叉树结构所占用的堆内存 5 但是实参指针将出现无所指的状态,出现不可预料的错误 6 因此传递的是指针的引用,这样才能将实参指针置空。 7  8 2)使用递归方法释放节点 9  10 */11 12 template <typename T>13 void binaryTree<T>::distroy(binaryTreeNode<T>*& pNode)14 {15     if(pNode)16     {17         distroy(pNode->leftChild);18         distroy(pNode->rightChild);19         delete pNode;20         pNode = NULL;21     }22 }23 template <typename T>24 void binaryTree<T>::distroy()25 {26     distroy(mRoot);27 }

如要删除如上例1中的二叉树,删除过程依次为:4 5 2 6 3 1

 

>>对于获取树的深度,有一种方法是,获取左右子树的深度,比较子树深度大小,大的那个增1即为树的深度了。当然,也是递归实现。

 1 template <typename T> 2 int binaryTree<T>::getHeight() 3 { 4     return getHeight(mRoot); 5 } 6 /* 7 获取当前节点的深度 8  递归的方法首先要设置截止条件,在进行递归操作。 9  0.约束条件:节点为空10  1.递归左子树,每次递归加111  2.递归右子树,每次递归加112  3.比较左右子树深度,更深的子树+1即为当前节点深度。13 */14 15 template <typename T>16 int binaryTree<T>::getHeight(binaryTreeNode<T>* node)17 {18     if(node == NULL)19         return 0;20     else{21         int depL = getHeight(node->leftChild);22         int depR = getHeight(node->rightChild);23         return (depL > depR) ? depL+1 : depR+1;24     }25         26 }

 

>>同理,获取树的规模只要遍历整棵树即可,这里用递归实现。这里仅给出前序遍历,后序遍历和中序遍历类似则不再给出。

 1 template <typename T> 2 void binaryTree<T>::preOrder() 3 { 4     cout <<"前序遍历: "; 5     preOrder(mRoot); 6     cout << endl; 7 } 8  9 /*10  前序遍历:11  1.由于是递归实现,所以要设置截止条件:当前节点为空12  2.先访问父节点,再访问左节点,最后访问右孩子13  14  */15 template <typename T>16 void binaryTree<T>::preOrder(binaryTreeNode<T>* node)17 {18     if(node == NULL)19         return;20     else{21         cout << node->element << ;22         preOrder(node->leftChild);23         preOrder(node->rightChild);24     }25 }

 

对于例1的遍历结果,如下:

输入:1 2 4 -1 -1 5 -1 -1 3 -1 6 -1 -1前序遍历: 1 2 4 5 3 6  中序遍历: 4 2 5 1 3 6  后序遍历: 4 5 2 6 3 1 树的高度为: 3树的节点数目: 6

 

>>总之呢,创建二叉树的全过程都用到了递归,那么递归到底是什么呢?

从定义上来讲:递归作为一种算法,是让函数/子程序/过程在程序运行过程中调用自身的方法,能够把一个较为复杂的问题经过层层转换,得到一个与原问题相似但是规模大大减小的问题来求解。递归方法大大减少了代码的复杂度。

实现方法:首先递归必须设置一个终止条件,当满足终止条件时,则递归返回。除此之外,则递归调用自身。

 

二叉树的基本功能实现方法(C++)