普通二叉树C++实现

Myth丶恋晨 2022-08-18 02:03 133阅读 0赞

数据结构作业- -没啥好说的

\-BinaryTree.h

#ifndef __BIANRY_TREE_H__
    #define __BINARY_TREE_H__
    
    #include <iostream>
    #include <queue>
    
    template <class T>
    struct BinTreeNode {
    	T data;
    	BinTreeNode* left;
    	BinTreeNode* right;
    
    	BinTreeNode(T value = 0, BinTreeNode* lt = NULL, BinTreeNode* rt = NULL)
    		:data(value), left(lt), right(rt) {}
    };
    
    template <class T>
    class BinaryTree {
    public:
    	BinaryTree() :root(NULL) {}
    	BinaryTree(T value) :refValue(value), root(NULL) {}
    	~BinaryTree() { destroy(); }
    
    	bool isEmpty()const { return NULL == root; }
    	int height()const { return height(root); }
    	int size()const { return size(root); }
    
    	BinTreeNode<T>* getParent(BinTreeNode<T>* node)const { return getParent(root, node); }
    	BinTreeNode<T>* getLeftChild(BinTreeNode<T>* node)const { return node->left; }
    	BinTreeNode<T>* getRightChild(BinTreeNode<T>* node)const { return node->right; }
    	BinTreeNode<T>* getRoot()const { return root; }
    
    	BinTreeNode<T>* find(const T& x)const { return find(root, x); }
    	void preOrder(void(*visit)(BinTreeNode<T>* node))const { preOrder(root, visit); }
    	void inOrder(void(*visit)(BinTreeNode<T>* node))const { inOrder(root, visit); }
    	void postOrder(void(*visit)(BinTreeNode<T>* node))const { postOrder(root, visit); }
    	void levelOrder(void(*visit)(BinTreeNode<T>* node))const;
    
    	void createBinTree(std::istream& in) { destroy(); createBinTree(in, root); }
    	void destroy() { destroy(root); }
    
    private:
    	BinTreeNode<T>* root;
    	T refValue;
    
    	int height(BinTreeNode<T>* node)const;
    	int size(BinTreeNode<T>* node)const;
    
    	BinTreeNode<T>* createBinTree(std::istream& in, BinTreeNode<T>*& node);
    	BinTreeNode<T>* getParent(BinTreeNode<T>* subTree, BinTreeNode<T>* node)const;
    	BinTreeNode<T>* find(BinTreeNode<T>* node, const T& x)const;
    
    	void preOrder(BinTreeNode<T>* subTree, void(*visit)(BinTreeNode<T>* node))const;
    	void inOrder(BinTreeNode<T>* subTree, void(*visit)(BinTreeNode<T>* node))const;
    	void postOrder(BinTreeNode<T>* subTree, void(*visit)(BinTreeNode<T>* node))const;
    
    	void destroy(BinTreeNode<T>*& node);
    
    };
    
    // Internal method: height
    template <class T>
    int BinaryTree<T>::height(BinTreeNode<T>* node)const {
    	if (NULL == node) return 0;
    	int h1 = height(node->left);
    	int h2 = height(node->right);
    	return h1 > h2 ? h1 + 1 : h2 + 1;
    }
    
    // Internal method: size
    template <class T>
    int BinaryTree<T>::size(BinTreeNode<T>* node)const {
    	if (NULL == node) return 0;
    	return size(node->left) + size(node->right) + 1;
    }
    
    // Internal method: getParent
    template <class T>
    BinTreeNode<T>* BinaryTree<T>::getParent(BinTreeNode<T>* subTree, BinTreeNode<T>* node)const {
    	if (NULL == subTree) return NULL;
    	if (subTree->left == node || subTree->right == node) return subTree;
    	BinTreeNode<T>* p;
    	if (NULL != (p = getParent(subTree->left, node))) 
    		return p;
    	else 
    		return getParent(subTree->right, node);
    }
    
    // Internal method: preOrder(DLR)
    template <class T>
    void BinaryTree<T>::preOrder(BinTreeNode<T>* subTree, void(*visit)(BinTreeNode<T>* node))const {
    	if (NULL == subTree) return;
    	visit(subTree);
    	preOrder(subTree->left, visit);
    	preOrder(subTree->right, visit);
    }
    
    // Internal method: inOrder(LDR)
    template <class T>
    void BinaryTree<T>::inOrder(BinTreeNode<T>* subTree, void(*visit)(BinTreeNode<T>* node))const {
    	if (NULL == subTree) return;
    	inOrder(subTree->left, visit);
    	visit(subTree);
    	inOrder(subTree->right, visit);
    }
    
    // Internal method: preOrder(LRD)
    template <class T>
    void BinaryTree<T>::postOrder(BinTreeNode<T>* subTree, void(*visit)(BinTreeNode<T>* node))const {
    	if (NULL == subTree) return;
    	postOrder(subTree->left, visit);
    	postOrder(subTree->right, visit);
    	visit(subTree);
    }
    
    // Internal method: createBinTree
    template <class T>
    BinTreeNode<T>* BinaryTree<T>::createBinTree(std::istream& in, BinTreeNode<T>*& node) {
    	T val;
    	in >> val;
    	if (val == refValue) return NULL;
    	//node = new BinTreeNode<T>(val, createBinTree(in, node->left), createBinTree(in, node->right));
    	node = new BinTreeNode<T>(val);
    	node->left = createBinTree(in, node->left);
    	node->right = createBinTree(in, node->right);
    	return node;
    }
    
    // Internal method: destroy
    template <class T>
    void BinaryTree<T>::destroy(BinTreeNode<T>*& node) {
    	if (NULL == node) return;
    	destroy(node->left);
    	destroy(node->right);
    	delete node;
    }
    
    // Internal method: find
    template <class T>
    BinTreeNode<T>* BinaryTree<T>::find(BinTreeNode<T>* node, const T& x)const {
    	if (node == NULL) return NULL;
    	if (node->data == x) return node;
    	BinTreeNode<T>* t;
    	if (NULL != (t = find(node->left, x))) return t;
    	else return find(node->right, x);
    }
    
    // levelOrder
    template <class T>
    void BinaryTree<T>::levelOrder(void(*visit)(BinTreeNode<T>* node))const {
    	std::queue<BinTreeNode<T>*> Queue;
    	if (NULL == root) return;
    	BinTreeNode<T>* t = root;
    	Queue.push(t);
    	while (!Queue.empty()) {
    		t = Queue.front();
    		visit(t);
    		Queue.pop();
    		if (NULL != t->left) Queue.push(t->left);
    		if (NULL != t->right) Queue.push(t->right);
    	}
    }
    
    
    #endif

测试用例-main.cpp

#include "BinaryTree.h"
    using namespace std;
    
    template <class T>
    void vs(BinTreeNode<T>* node) {
    	cout << node->data << " ";
    }
    
    template <class T>
    void order(const BinaryTree<T>& bt) {
    	cout << "前序输出：";
    	bt.preOrder(&vs);
    	cout << endl;
    	cout << "中序输出：";
    	bt.inOrder(&vs);
    	cout << endl;
    	cout << "后序输出：";
    	bt.postOrder(&vs);
    	cout << endl;
    	cout << "层序输出：";
    	bt.levelOrder(&vs);
    	cout << endl;
    }
    
    int main()
    {
    	BinaryTree<char> bt('#');
    	// 构造二叉树
    	bt.createBinTree(cin);
    	
    	if (bt.isEmpty()) cout << "该树为空" << endl;
    	else cout << "该树不为空" << endl;
    
    	BinTreeNode<char>* root = bt.getRoot();
    	cout << "根节点为：" << root->data << endl;
    	// left child
    	if (NULL == bt.getLeftChild(root))
    		cout << "左儿子为空" << endl;
    	else
    		cout << "左儿子为" << bt.getLeftChild(root)->data << endl;
    	// right child
    	if (NULL == bt.getRightChild(root))
    		cout << "右儿子为空" << endl;
    	else
    		cout << "右儿子为" << bt.getRightChild(root)->data << endl;
    	// parent
    	if (NULL == bt.getParent(root))
    		cout << "父节点为空" << endl;
    	else
    		cout << "父节点为" << bt.getParent(root)->data << endl;
    
    	cout << (NULL != bt.find('A') ? "A为二叉树里面的节点" : "A不是二叉树里面的节点") << endl;
    	cout << (NULL != bt.find('T') ? "T为二叉树里面的节点" : "T不是二叉树里面的节点") << endl;
    
    	cout << "高度为：" << bt.height() << endl;
    	cout << "节点数为：" << bt.size() << endl;
    
    	order(bt);
    
    	return 0;
    }

![SouthEast][]

[SouthEast]: /images/20220731/b33eefb37a994da3a8b20b454b144d12.png