自定义类_BinaryTree

最新推荐文章于 2023-01-26 11:46:57 发布
最新推荐文章于 2023-01-26 11:46:57 发布
阅读量1.7k 收藏
点赞数
分类专栏： VC++自定义类 _原创 文章标签： null struct constructor delete class
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/zeroDspace/article/details/528354
版权


// 功能: 二叉树的实现
// 时间: 2005-11-12
//
// BUG:
// 以多文件方式引用会引起错误
// 原因为:
// 在 BinaryTree类 的声明中
// 定义 struct tagBinaryTreeNode
// BinaryTree为模版类,template<class Type>
// 在 struct tagBinaryTreeNode 中有元素类型为Type
// Type value;
// 如果放在 BinaryTree外，
// 怎么使 tagBinaryTreeNode.value 的类型与 Type 匹配



// BinaryTree类的声明部分
//
#define BTREE_ERROR 0
#define BTREE_LEFT 1
#define BTREE_RIGHT 2
#define NULL 0

template<class Type>
class BinaryTree
{
 public:
  typedef struct tagBinaryTreeNode
  {
   Type value;
   struct tagBinaryTreeNode *left;
   struct tagBinaryTreeNode *right;
   struct tagBinaryTreeNode *parent;
  } BNODE , *BLIST , *BPOINT;

 public:
  BinaryTree();
  ~BinaryTree();

  //清空二叉树
  void Clear();
  //将结点e赋值为value
  void Assign( Type value , BPOINT e = NULL );
  //插入结点
  void InsertChild( BPOINT e , Type value , int LRFlag = BTREE_LEFT );
  //删除子树
  void DeleteChildren( BPOINT e , int LRFlag );
  void DeleteChildren( BPOINT e );
  //父结点指针
  BPOINT Parent( BPOINT e );
  //子结点指针
  BPOINT Child( BPOINT e , int LRFlag = BTREE_LEFT );
  //兄弟结点指针
  BPOINT Sibling( BPOINT e );
  //判断结点e是父结点的 左孩子 or 右孩子
  int GetLRFlag( BPOINT e );
  //根结点指针
  BPOINT Root();
  //得到指定结点的值
  Type GetValue( BPOINT e );
  //前序遍历二叉树
  BPOINT PreOrderTraverseFirst();
  BPOINT PreOrderTraverseNext( BPOINT e );
  //中序遍历二叉树
  BPOINT InOrderTraverseFirst();
  BPOINT InOrderTraverseNext( BPOINT e );
  //后序遍历二叉树
  BPOINT PostOrderTraverseFirst();
  BPOINT PostOrderTraverseNext( BPOINT e );
 private:
  //中序遍历
  void InOrderTraverse( BPOINT e );

 private:
  BLIST root;
};


// BinaryTree类的实现部分
//
template<class Type>
BinaryTree<Type>::BinaryTree()
{
 //cout<<"hi, i am in constructor of BinaryTree"<<endl;
 root = NULL;
}

template<class Type>
BinaryTree<Type>::~BinaryTree()
{
 //cout<<"hi, i am in deconstructor of BinaryTree"<<endl;
 DeleteChildren( root );
}

//
//清空二叉树
template<class Type>
void BinaryTree<Type>::Clear()
{
 DeleteChildren( root );
 root = NULL; 
}
//
//如果指定e，则将结点e赋值为value
//如果没有指定e，则默认结点为root
//如果是空树，即root==NULL，则建立root结点
template<class Type>
void BinaryTree<Type>::Assign( Type value , BPOINT e )
{
 if( e == NULL )
 {
  if( root == NULL )
  {
   root = new BNODE;
   root->value = value;
   root->left = NULL;
   root->right = NULL;
   root->parent = NULL;
  }
  else
  {
   root->value = value;
  }
 }
 else
 {
  e->value = value;
 }
}
//
//插入结点
template<class Type>
void BinaryTree<Type>::InsertChild( BPOINT e , Type value , int LRFlag )
{
 if( e == NULL )
  return;
 BPOINT child = new BNODE;
 child->value = value;
 child->left = NULL;
 child->right = NULL;
 child->parent = e;
 //判断要插入的位置，即左右边
 if( LRFlag == BTREE_LEFT )
 {
  if( e->left != NULL )
  {
   //如果e的左子树不空，
   //则将其作为child结点的左子树
   child->left = e->left;
   e->left->parent = child;
   e->left = child;
  }
  else
  {
   e->left = child;
  }
 }
 else
 {
  if( e->right != NULL )
  {
   //如果e的右子树不空，
   //则将其作为child结点的右子树
   child->right = e->right;
   e->right->parent = child;
   e->right = child;
  }
  else
  {
   e->right = child;
  }
 }
}
//
//删除子树
template<class Type>
void BinaryTree<Type>::DeleteChildren( BPOINT e , int LRFlag )
{
 if( LRFlag & BTREE_LEFT )
 {
  DeleteChildren( e->left );
  e->left = NULL;
 }
 if( LRFlag & BTREE_RIGHT )
 {
  DeleteChildren( e->right );
  e->right = NULL;
 }
}
template<class Type>
void BinaryTree<Type>::DeleteChildren( BPOINT e )
{
 if( e != NULL )
 {
  DeleteChildren( e->left );
  DeleteChildren( e->right );
  if( e != root )
  {
   if( e->parent->left == e )
    e->parent->left = NULL;
   if( e->parent->right == e )
    e->parent->right = NULL;
  }
  else
  {
   root = NULL;
  }
  delete e;
 }
}
//
//得到父结点的指针
template<class Type>
BinaryTree<Type>::BPOINT BinaryTree<Type>::Parent( BPOINT e )
{
 if( e == NULL )
  return NULL;
 return e->parent;
}
//
//得到子结点的指针
template<class Type>
BinaryTree<Type>::BPOINT BinaryTree<Type>::Child( BPOINT e , int LRFlag )
{
 if( e == NULL )
  return NULL;
 if( LRFlag == BTREE_LEFT )
 {
  return e->left;
 }
 else
 {
  return e->right;
 }
}
//
//得到根结点的指针
template<class Type>
BinaryTree<Type>::BPOINT BinaryTree<Type>::Root()
{
 return root;
}
//
//得到兄弟结点的指针
template<class Type>
BinaryTree<Type>::BPOINT BinaryTree<Type>::Sibling( BPOINT e )
{
 if( e == root || e == NULL )
  return NULL;
 if( e->parent->left == e )
  return e->parent->right;
 else
  return e->parent->left;
}
//
//判断结点e是父结点的 左孩子 or 右孩子
template<class Type>
int BinaryTree<Type>::GetLRFlag( BPOINT e )
{
 if( e == NULL || e == root )
  return BTREE_ERROR;
 if( e->parent->left == e )
  return BTREE_LEFT;
 else
  return BTREE_RIGHT;
}
//
//得到指定结点的值
template<class Type>
Type BinaryTree<Type>::GetValue( BPOINT e )
{
 if( e == NULL )
  return 0;
 return e->value;
}
//
//前序遍历二叉树
template<class Type>
BinaryTree<Type>::BPOINT BinaryTree<Type>::PreOrderTraverseFirst()
{
 return root;
}
template<class Type>
BinaryTree<Type>::BPOINT BinaryTree<Type>::PreOrderTraverseNext( BPOINT e )
{
 if( e->left != NULL )
 {
  return e->left;
 }
 else if( e->right != NULL )
 {
  return e->right;
 }
 else
 {
  while( e != NULL && e != root && ( GetLRFlag( e ) == BTREE_RIGHT || e->parent->right == NULL ) )
  {
   e = e->parent;
  }
  if( e == NULL || e == root )
   return NULL;
  else
   return e->parent->right;
 }
}
//
//中序遍历二叉树
template<class Type>
BinaryTree<Type>::BPOINT BinaryTree<Type>::InOrderTraverseFirst()
{
 if( root == NULL )
  return NULL;
 BPOINT e = root;
 while( e->left != NULL )
  e = e->left;
 return e;
}
template<class Type>
BinaryTree<Type>::BPOINT BinaryTree<Type>::InOrderTraverseNext( BPOINT e )
{
 if( e == NULL )
  return NULL;
 BPOINT p;
 if( e->right != NULL )
 {
  p = e->right;
  while( p->left != NULL )
   p = p->left;
  return p;
 }
 else
 {
  p = e;
  while( GetLRFlag( p ) == BTREE_RIGHT && p != NULL && p != root )
   p = p->parent;
  return p->parent;
 }
}
//
//后序遍历二叉树
template<class Type>
BinaryTree<Type>::BPOINT BinaryTree<Type>::PostOrderTraverseFirst()
{
 if( root == NULL )
  return NULL;
 BPOINT e = root;
 while( e->left != NULL )
  e = e->left;
 return e;
}
template<class Type>
BinaryTree<Type>::BPOINT BinaryTree<Type>::PostOrderTraverseNext( BPOINT e )
{
 if( e == NULL || e == root )
  return NULL;

 BPOINT p = Sibling( e );
 if( GetLRFlag(e) == BTREE_LEFT && p != NULL )
 {
  while( p->left != NULL )
   p = p->left;
  return p;
 }
 else
 {
  return e->parent;
 }
}
//
//


#include "iostream.h"

void main()
{
 int flag;

 BinaryTree<int> btree;
 BinaryTree<int>::BPOINT p;

btree.Clear();
 btree.Assign( 17 );
 btree.InsertChild( btree.Root() , 16 , BTREE_LEFT );
 btree.InsertChild( btree.Root() , 18 , BTREE_RIGHT );
 btree.InsertChild( btree.Child( btree.Root() , BTREE_RIGHT ) , 19 , BTREE_LEFT );
//btree.DeleteChildren( btree.Root()->left->parent->right );

 cout<<"value of root is ";
 cout<<btree.GetValue( btree.Root() )<<endl;


 cout<<"根结点的 左孩子 是 根结点的 ";
 flag = btree.GetLRFlag( btree.Child( btree.Root() , BTREE_LEFT ) );
 if( flag == BTREE_LEFT )
  cout<<"左孩子"<<endl;
 else if( flag == BTREE_RIGHT )
  cout<<"右孩子"<<endl;
 else
  cout<<"!!!出错!!!"<<endl;


 cout<<"根结点的 左孩子 ";
 flag = btree.GetLRFlag( btree.Sibling( btree.Child( btree.Root() , BTREE_LEFT ) ) );
 if( flag & BTREE_LEFT )
  cout<<"的 兄弟是 根结点的 左孩子"<<endl;
 else if( flag & BTREE_RIGHT )
  cout<<"的 兄弟是 根结点的 右孩子"<<endl;
 else
  cout<<"没有兄弟"<<endl;

 cout<<btree.Root()<<"/t"<<btree.GetValue( btree.Root() )<<endl;
 cout<<btree.Child( btree.Root() , BTREE_LEFT )<<"/t"<<btree.GetValue(btree.Child( btree.Root() , BTREE_LEFT ))<<endl;
 cout<<btree.Sibling( btree.Child( btree.Root() , BTREE_LEFT ) )<<"/t"<<btree.GetValue(btree.Sibling( btree.Child( btree.Root() , BTREE_LEFT ) ))<<endl;

 cout<<"前序:"<<endl;
 p = btree.PreOrderTraverseFirst();
 while( p )
 {
  cout<<btree.GetValue(p)<<endl;
  p = btree.PreOrderTraverseNext(p);
 }


 cout<<"中序:"<<endl;
 p = btree.InOrderTraverseFirst();
 while( p )
 {
  cout<<btree.GetValue(p)<<endl;
  p = btree.InOrderTraverseNext(p);
 }

 cout<<"后序:"<<endl;
 p = btree.PostOrderTraverseFirst();
 while( p )
 {
  cout<<btree.GetValue(p)<<endl;
  p = btree.PostOrderTraverseNext(p);
 }
}

Binary Tree二叉树用class实现
u010146618的博客
10-13 412
python class 创建二叉树
数据结构-二叉树(binaryTree)-C语言实现
NICE__FUTURE的博客
08-22 1257
用C语言实现二叉树基本功能 接口部分 “binaryTree.h” /*二叉树接口*/ #ifndef _BINARY_TREE_H_ #define _BINARY_TREE_H_ #include &amp;lt;stdbool.h&amp;gt; #define NAME_LENGTH 20 #define MAX_TRNODES 15 //测试用定义的最大节点数量，根据情况设定 /*实体定义*...
编程练习——二叉树（BinaryTree）
帐前卒 专栏
08-19 2146
先写一个树节点类。使用Temple也可以，不使用的话，使用特定类型，用法比较局限。不过本着“今天尽量不要做出今天不必要的决定”极限编程法制。做一个特殊类型的BinaryTree，也未尝不可。这里的TreeNode只有数据域。 templateclass T>class TreeNode{private: T data; TreeNode * left; 
二叉树的创建，前序，中序，后序，层序遍历
魏尔肖的博客
04-27 1732
二叉树（binary tree）是另一种树形结构，它的特点是每个节点至多有两颗子树，并且其子树有左右之分，并且顺序不能颠倒。 主要用递归的思想完成创建，遍历等操作。 #include <iostream> using namespace std; #include <string> #include <queue>template <typename T> struct TreeNode{
binaryTree遍历
大学之道
06-11 361
前序遍历的输出结果：ABDECF 中序遍历的输出结果：DBEAFC 后序遍历的输出顺序：DEBFCA https://www.cnblogs.com/turnips/p/5096578.html 前序遍历的规则： （1）访问根节点 （2）前序遍历左...
BinaryTree
分享技术，享受生活
07-10 754
class BinaryTree { // 定义二叉树的操作类 class Node {  @SuppressWarnings("unchecked")  private Comparable data; // 保存操作的数据内容  private Node left; // 左
binarytree.rar
04-02
二叉树是一种在计算机科学中广泛使用的数据结构，它的每个节点最多有两个子节点，通常称为左子节点和右...解压“binarytree.rar”，查看其中的文件，理解数据结构，并根据给定的描述编写代码，以实现二叉树的前序遍历。
BinaryTree-源码.rar
10-10
【标题】：“BinaryTree-源码.rar”是一个与二叉树相关的源代码压缩包，它可能包含各种二叉树数据结构的实现，如二叉搜索树、平衡二叉树（AVL树或红黑树）或者自定义的二叉树结构。这个压缩包可能为学习数据结构与...
binaryTree_二叉树mfc_policeman4uu_mfc实现二叉树_
09-30
为了实现这些功能，你需要在MFC工程中创建一个自定义的二叉树节点类，包含数据字段、指针以及遍历相关的方法。接着，构建二叉树结构，可以通过动态内存分配创建节点，并根据需求连接它们。在遍历过程中，你可以使用...
Python-BinaryTree用于学习二叉树的Python库
08-12
"Python-BinaryTree"是一个专门用于学习和操作二叉树的Python库，它提供了方便的API来创建、遍历和操作二叉树。 1. **二叉树的概念与类型** - 二叉树的基本概念：二叉树的每个节点包含一个值、一个指向左子树的...
二叉树（Binary_tree）C++ 模板
Aiden的博客
06-03 687
二叉树节点 Binary_node.h template<typename Entry> struct Binary_node { public: Binary_node(); Binary_node(const Entry &x); public: Entry data; Binary_node<Entry> *left; Binary_node<Entry> *right; }; template<typename Entry> Bin
C++ class实现二叉树(完整代码，附非递归遍历)
m0_51955470的博客
05-03 610
代码如下: #include <iostream> #include <stack> using namespace std; typedef char ElemType; int InOrder_count = 0; class BinTreeNode { friend class BinaryTree; public: BinTreeNode(): lchild(NULL), rchild(NULL) { }; private: ElemType data
数据结构--二叉树 Binary Tree
Michael是个半路程序员
05-10 1292
文章目录1.概念2.存储方式2.1 链式存储（二叉树代码大部分是链式实现的）2.2 顺序存储（基于数组）3.二叉树的遍历 1.概念 二叉树，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点 满二又树，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点。 完全二叉树，叶子节点都在最底下两层，最后一层的叶子节点都靠左排...
【数据结构】树结构-二叉树(BinaryTree)的建立、前中后序遍历、查找节点和删除节点
weixin_37838913的博客
04-06 281
树结构分析树树的常用术语遍历二叉树根据节点查找二叉树删除节点 分析树 前戏: {7,3,10,1,5,9,12} 数组: 增加慢:index本来有值,要指定插入时,后面的值都要后移 查询快:直接根据index找 链表 增加快:每插入一个数只要把节点的next指给要插入值的引用,把插入值的next指向原来的值引用 查询慢:但是要查询时,比如要查询12,就要查7次 二叉树: 分析如果以二叉排序树来存储...
数据结构笔记 —— 二叉树（前序、中序、后序遍历和查找）
一纸春秋的博客
12-19 772
前序遍历，中序遍历，后序遍历 首先定义节点类，这里依旧是在拿梁山好汉作为节点里面的信息 //先创建HeroNode节点 class HeroNode { private int no; private String name; private HeroNode left; //默认为null private HeroNode right; //默认为null public HeroNode(int no,String name){ this.no =
java：手写二叉树BinaryTree添加和查询方法
qiaolevip的专栏
05-17 792
package arrays.myArray;public class BinaryTree { private Node root; // 添加数据 public void add(int data) {  // 递归调用  if (null == root)   root = new Node(data, null, null);  else   addTree(root, data)
蓝桥杯常用树模板（C/C++）
m0_71934846的博客
01-26 2423
蓝桥杯常用树模板（C/C++）
Python 初识二叉树，新手也秒懂！（续：实战binarytree）
汉阳Hann's Home
07-25 2399
Python 初识二叉树，新手也秒懂！续集之——初步探索二叉树的第三方库 binarytree 其使用环境、安装方法及二叉树的相关知识，请见：《Python 初识二叉树，新手也秒懂！》 不能导入的请安装：pip install binarytree 安装好了就导入库：import binarytree ...
[BinaryTree] 二叉树类的实现
weixin_30439031的博客
01-30 394
二叉树结点的抽象数据类型： 1 template<class T> 2 class BinaryTreeNode 3 { 4 friend class BinaryTree<T>; 5 private: 6 T element; //结点的数据域 7 BinaryTr...
Java中的二叉树实现：TreeNode和BinaryTree类
在Java编程语言中，二叉树的实现通常需要自定义TreeNode和BinaryTree类，因为Java标准库中并不直接包含这些类的实现。本文将详细介绍二叉树在Java中的实现原理，以及TreeNode和BinaryTree类的设计和应用。 首先，...
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值