首页 > 代码库 > 二叉树类的实现
二叉树类的实现
二叉树结点的抽象数据类型:
1 template<class T> 2 class BinaryTreeNode 3 { 4 friend class BinaryTree<T>; 5 private: 6 T element; //结点的数据域 7 BinaryTreeNode<T>* LeftChild; //结点的左孩子结点 8 BinaryTreeNode<T>* RightChild; //结点的右孩子结点 9 public: 10 BinaryTreeNode(); 11 BinaryTreeNode(const T& ele); 12 BinaryTreeNode(const T& ele, BinaryTreeNode<T>* l, BinaryTreeNode<T>* r); 13 bool isLeaf() const; //判断该结点是否是叶子结点,若是,则返回true 14 };
二叉树结点函数功能实现:
1 template<class T> 2 BinaryTreeNode<T>::BinaryTreeNode() 3 { 4 LeftChild = RightChild = NULL; 5 } 6 template<class T> 7 BinaryTreeNode<T>::BinaryTreeNode(const T& ele) 8 { 9 element = ele; 10 LeftChild = RightChild = NULL; 11 } 12 template<class T> 13 BinaryTreeNode<T>::BinaryTreeNode(const T& ele, BinaryTreeNode<T>* l, BinaryTreeNode<T>* r) 14 { 15 element = ele; 16 LeftChild = l; 17 RightChild = r; 18 } 19 template<class T> 20 bool BinaryTreeNode<T>::isLeaf() const 21 { 22 if (LeftChild == NULL && RightChild == NULL) 23 return true; 24 else return false; 25 }
二叉树的抽象数据类型:
1 template<class T> 2 class BinaryTree 3 { 4 private: 5 BinaryTreeNode<T>* root; 6 public: 7 BinaryTree(); 8 ~BinaryTree() {} 9 bool IsEmpty() const; //判断二叉树是否为空树 10 BinaryTreeNode<T>* getRoot() const; //返回二叉树的根结点 11 void breadthFirstOrder(BinaryTreeNode<T>* root);//广度优先遍历以root为根结点的子树 12 void preOrder(BinaryTreeNode<T>* root); //先序遍历以root为根结点的子树 13 void inOrder(BinaryTreeNode<T>* root); //中序遍历以root为根结点的子树 14 void postOrder(BinaryTreeNode<T>* root); //后序遍历以root为根结点的子树 15 void deleteBinaryTree(BinaryTreeNode<T>* root); //删除以root为根结点的子树 16 void visit(BinaryTreeNode<T>* pointer); //访问当前结点 17 BinaryTreeNode<T>* build_from_pre_and_in(char* preorder, char* inorder, int n); 18 //根据前序和中序遍历表达式构造二叉树 19 BinaryTreeNode<T>* build_from_post_and_in(char* postorder, char* inorder, int m); 20 //根据后序和中序遍历表达式构造二叉树 21 int getRootId1(char *preorder, char *inorder, int n); //返回根结点在中序遍历表达式中序号 22 int getRootId2(char *postorder, char *inorder, int m); //返回根结点在中序遍历表达式中序号 23 };
二叉树类的实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。