首页 > 其他 > 详细

第五十三课 树中节点的查找操作

时间:2018-09-22 20:55:23      阅读:263      评论:0      收藏:0      [点我收藏+]

技术分享图片

 

 

第一种查找方式中,如果保存这个值的节点确实保存在树中,那么就将这个节点的指针返回,否则返回空。

第二种查找方式中,按节点查找,如果找到就返回这个节点的地址,没有找到就返回空。

技术分享图片

 

具体的查找方式不能像链表那样,因为树是非线性结构。

树是递归定义的,与树相关的算法也是递归的。

例如:我们查找H,先查找根节点,和根节点比较,如果相等就将根节点返回。如果不相等,就去子树中去查找。

 

技术分享图片

 

 

技术分享图片

 

 GTree.h中完成查找函数内容:

  1 #ifndef GTREE_H
  2 #define GTREE_H
  3 
  4 #include "Tree.h"
  5 #include "GTreeNode.h"
  6 
  7 namespace DTLib
  8 {
  9 
 10 template < typename T >
 11 class GTree : public Tree<T>
 12 {
 13 protected:
 14     GTreeNode<T>* find(GTreeNode<T>* node, const T& value) const
 15     {
 16         GTreeNode<T>* ret = NULL;
 17 
 18         if( node != NULL )
 19         {
 20             if( node->value == value )
 21             {
 22                 return node;
 23             }
 24             else
 25             {
 26                 for(node->child.move(0); !node->child.end() && (ret == NULL); node->child.next())
 27                 {
 28                     ret = find(node->child.current(), value);
 29                 }
 30             }
 31         }
 32 
 33         return ret;
 34     }
 35 
 36     GTreeNode<T>* find(GTreeNode<T>* node,  GTreeNode<T>* obj) const
 37     {
 38         GTreeNode<T>* ret = NULL;
 39 
 40         if( node == obj )
 41         {
 42             return node;
 43         }
 44         else
 45         {
 46             if( node != NULL )
 47             {
 48                 for( node->child.move(0); !node->child.end() && (ret == NULL); node->child.next())
 49                 {
 50                     ret = find(node->child.current(), obj);
 51                 }
 52             }
 53         }
 54 
 55         return ret;
 56     }
 57 public:
 58     bool insert(TreeNode<T>* node)
 59     {
 60         bool ret = true;
 61 
 62         return ret;
 63     }
 64 
 65     bool insert(const T& value, TreeNode<T>* parent)
 66     {
 67         bool ret = true;
 68 
 69         return ret;
 70     }
 71 
 72     //删除的节点的子节点我们还需要处理,因此要返回删除节点的指针,这样有机会对里面的元素做进一步操作
 73     SharedPointer< Tree<T> > remove(const T& value)
 74     {
 75         return NULL;
 76     }
 77 
 78     SharedPointer< Tree<T> > remove(TreeNode<T>* node)
 79     {
 80         return NULL;
 81     }
 82 
 83     GTreeNode<T>* find(const T& value) const  // 返回GTreeNode,赋值兼容性
 84     {
 85         return find(root(), value);
 86     }
 87 
 88     GTreeNode<T>* find(TreeNode<T>* node) const
 89     {
 90         return find(root(), dynamic_cast<GTreeNode<T>*>(node));
 91     }
 92 
 93     GTreeNode<T>* root() const
 94     {
 95         return dynamic_cast<GTreeNode<T>*>(this->m_root);
 96     }
 97 
 98     int degree() const
 99     {
100         return 0;
101     }
102     int count() const
103     {
104         return 0;
105     }
106 
107     int height() const
108     {
109         return 0;
110     }
111 
112     void clear()
113     {
114         this->m_root = NULL;
115     }
116 
117     ~GTree()
118     {
119         clear();
120     }
121 };
122 
123 }
124 
125 #endif // GTREE_H

 

小结:

技术分享图片

 

技术分享图片

 

第五十三课 树中节点的查找操作

原文:https://www.cnblogs.com/wanmeishenghuo/p/9690838.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!