第1个回答 2019-12-23
好题，首先根据面向对象思想，应该定义二叉树节点类，然后二叉树类。二叉树节点包含属性有节点值，左指针，右指针。成员函数有获取节点值。设置左孩子，设置右指针，获取左孩子，获取右孩子。二叉树类属性有根结点指针。成员函数有创建二叉树，先序遍历，中序遍历，后序遍历。#include <iostream>#include <queue>#include <limits>using namespace std; int x; // for input data typedef struct node{ int data; node* pLeft; node* pRight; node(int val = 0) : data(val), pLeft(NULL), pRight(NULL){}}TreeNode, *PTree; class BinaryTree{public: explicit BinaryTree(int size = 0); ~BinaryTree(); TreeNode* getHead() const; static void preOrder(TreeNode*); static void inOrder(TreeNode*); static void postOrder(TreeNode*); static void levOrder(TreeNode*); static int getDepth(TreeNode*); int getCount() const; int getLeafCount() const;private: void insertNode(int); PTree treeHead; int count;}; int main(void){ cout << "--------------------BinaryTree--------------------" << endl; // 4 1 7 3 6 8 BinaryTree t1(6); BinaryTree::preOrder(t1.getHead()); cout << endl; BinaryTree::inOrder(t1.getHead()); cout << endl; BinaryTree::postOrder(t1.getHead()); cout << endl; BinaryTree::levOrder(t1.getHead()); cout << endl; cout << "Tree's depth is " << BinaryTree::getDepth(t1.getHead()) << endl; cout << "Tree's count is " << t1.getCount() << endl; cout << "Tree's leafCount is " << t1.getLeafCount() << endl; return 0;} TreeNode* BinaryTree::getHead() const{ return this->treeHead;} void BinaryTree::insertNode(int data){ if( treeHead == NULL ){ treeHead = new TreeNode(data); return; } TreeNode* pre = NULL; TreeNode* cur = treeHead; while( cur != NULL ) { pre = cur; if( data < cur->data ){ cur = cur->pLeft; }else{ cur = cur->pRight; } } // create node in current cur = new TreeNode(data); if( data < pre->data ) pre->pLeft = cur; else pre->pRight = cur;} BinaryTree::BinaryTree(int size) : treeHead(NULL), count(size){ if( size <= 0 ){ cout << "Create a empty tree!" << endl; return; } cout << "Input " << size << " data to create BinaryTree: "; for(int i = 0; i < size; ++i){ cin >> x; this->insertNode(x); } // clear input stream cin.clear(); cin.ignore(numeric_limits<streamsize>::max(), '\n');} BinaryTree::~BinaryTree(){ queue<TreeNode*> que; que.push(treeHead); while( !que.empty() ) { TreeNode* curNode = que.front(); if( curNode != NULL ){ if( curNode->pLeft != NULL ) que.push(curNode->pLeft); if( curNode->pRight != NULL ) que.push(curNode->pRight); delete curNode; } que.pop(); } } void BinaryTree::preOrder(TreeNode* pNode){ if( pNode != NULL ){ cout << pNode->data << " "; BinaryTree::preOrder(pNode->pLeft); BinaryTree::preOrder(pNode->pRight); }} void BinaryTree::inOrder(TreeNode* pNode){ if( pNode != NULL ){ BinaryTree::inOrder(pNode->pLeft); cout << pNode->data << " "; BinaryTree::inOrder(pNode->pRight); }} void BinaryTree::postOrder(TreeNode* pNode){ if( pNode != NULL ){ BinaryTree::postOrder(pNode->pLeft); BinaryTree::postOrder(pNode->pRight); cout << pNode->data << " "; }} void BinaryTree::levOrder(TreeNode* pNode){ queue<TreeNode*> que; que.push(pNode); while( !que.empty() ) { TreeNode* curNode = que.front(); if( curNode != NULL ){ if( curNode->pLeft != NULL ) que.push(curNode->pLeft); if( curNode->pRight != NULL ) que.push(curNode->pRight); cout << curNode->data << " "; } que.pop(); }} int BinaryTree::getDepth(TreeNode* pNode){ if( pNode == NULL ) return -1; int ld = BinaryTree::getDepth(pNode->pLeft); int rd = BinaryTree::getDepth(pNode->pRight); return (ld>rd ? ld:rd) + 1;} int BinaryTree::getCount() const{ return this->count;} int BinaryTree::getLeafCount() const{ int leafCount = 0; queue<TreeNode*> que; que.push(treeHead); while( !que.empty() ) { TreeNode* curNode = que.front(); if( curNode != NULL ){ if( curNode->pLeft != NULL ) que.push(curNode->pLeft); if( curNode->pRight != NULL ) que.push(curNode->pRight); if( curNode->pLeft==NULL && curNode->pRight==NULL ) leafCount++; } que.pop(); } return leafCount; }本回答被网友采纳