二叉树的创建及遍历

十一，代码实现

#pragma once #include #include #include using namespace std; template struct BinaryTreeNode { BinaryTreeNode* _left; BinaryTreeNode* _right; T _data; BinaryTreeNode(const T& x) : _data(x)                     //数 , _left(NULL)                  //左孩子 , _right(NULL)                 //右孩子 {} }; template class BinaryTree { typedef BinaryTreeNode Node; public: BinaryTree()   // 默认构造函数 :_root(NULL) {} BinaryTree(const T* a, size_t size,const T& invalid)// invalid 是为空 :_root(NULL) { size_t index = 0; _root = _CreatTree(a, size, index, invalid); } BinaryTree(const BinaryTree& t) :_root(NULL) { _root = _CopyTree(t._root); } BinaryTree& operator=(const BinaryTree& t) { if (this != &t)// 判断自赋值 { Node*root = _CopyTree(t._root); Clear(_root); _root = root; } return *this; } ~BinaryTree() { Clear(_root); } public: Node*_CopyTree(Node* root) { Node* head = NULL; if (root) { head = new Node(root->_data); head->_left = _CopTree(root->_left); head->_right = _CopTree(root->_right); } return head; } void PrevOrder() { _PrevOrder(_root); cout _PostOrder(_root); cout queue q; if (_root) { q.push(_root); } while (q.size()) { BinaryTreeNode* front = q.front(); cout _data _left) { q.push(front->_left); } if (front->_right) { q.push(front->_right); } q.pop(); } cout return _Depth(_root); } protected: BinaryTreeNode * _CreatTree(const T* a, size_t size, size_t &index, const T& invalid) { assert(a); Node* root = NULL; if (index < size && a[index] != invalid) { root = new Node(a[index]); root->_left = _CreatTree(a, size, ++index, invalid); root->_right = _CreatTree(a, size, ++index, invalid); } return root; } void Clear(Node* root) { Node* del; Node* cur = root; if (cur) { del = cur; Clear(cur->_left); Clear(cur->_right); } } void _PrevOrder(Node* root) { if (root == NULL) { return; } cout _data _left); _PrevOrder(root->_right); } void _InOrder(Node* root) { if (root == NULL) { return; } else {         _InOrder(root->_left); cout _data _right); } } void _PostOrder(Node* root) { if (root == NULL) { return; } else { _PostOrder(root->_left); _PostOrder(root->_right); cout _data return 0; } return _size(root->_left) + _size(root->_right) + 1; } size_t _Depth(Node* root) { if (root == NULL) { return 0; } int leftDepth = _Depth(root->_left) + 1; int righrDepth = _Depth(root->_right) + 1; return leftDepth > righrDepth ? leftDepth : righrDepth; } size_t _LeafSize(Node* root)//叶子结点个数 { if (root == NULL) { return 0; } if ((root->_left == NULL) && (root->_right == NULL)) { return 1; } return _LeafSize(root->_left) + _LeafSize(root->_right); } protected: BinaryTreeNode * _root; };  void Test1()  { int array1[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }; //int array2[15] = { 1, 2, '#', 3, '#', '#', 4, 5, '#', 6, '#', 7, '#', '#', 8 }; BinaryTree t1(array1, 10 ,'#');      //BinaryTree t2(array2, 15, '#'); t1.PrevOrder();//先根遍历 t1.InOrder();//中序遍历 t1.PostOrder();//后根遍历 t1.LevelOrder();//层序遍历 cout Node*cur = _root; stack S; while (cur || S.size()) { while (cur) { S.push(cur); cur = cur->_left; } Node* top = S.top(); cout _data _right; } cout Node* top = S.top(); S.pop(); cout _data _right) { S.push(top->_right); } if (top->_left) { S.push(top->_left); } } cout while (cur) { S.push(cur); cur = cur->_left; } Node* top = S.top(); if((top->_right == NULL||top->_right ==prev)) { cout _data if (root == NULL) { return NULL; } if (root->_data == x) { return root; } Node* ret = _Find(x, root->_left); if (ret) { return ret; } return _Find(x, root->_right); }

public：

bool Find(const T& x) { if (_Find(x, _root)) { return true; } return false;   }

十五，第k层有多少结点

protected：

rsize_t _Getlevel(Node * root, int k) { if (root == NULL) { return 0; } if (k == 1) { return 1; } return _Getlevel(root->_left, k - 1) + _Getlevel(root->_right, k - 1); }

public：

size_t Getlevel(int k) { return _Getlevel(_root, k); }