响应式网站建设制作需要注意什么,西安专业网站制作,珠海网签查询,如何更新网站缓存一、问题概述 树是n个有限个数据的集合#xff0c;形如#xff1a; 它像不像倒着的树呢#xff1f;我们把它看成是一种数据结构----树。它的第一个节点称作树的根#xff0c;最底下的那些节点称作树的叶子。 我们今天所要研究的是二叉树#xff0c;即父节点最多只有两个孩…一、问题概述 树是n个有限个数据的集合形如 它像不像倒着的树呢我们把它看成是一种数据结构----树。它的第一个节点称作树的根最底下的那些节点称作树的叶子。 我们今天所要研究的是二叉树即父节点最多只有两个孩子左孩子和右孩子。 二叉树还有两种特殊的结构分为完全二叉树和满二叉树。
如 满二叉树高度为N的满二叉树有2^N-1个节点。
完全二叉树高度为N前N-1层为满二叉树第N层为连续的叶子节点。
二叉树有四种遍历方式
前序遍历根左右中序遍历左根右后序遍历左右根层序遍历从上往下从左往右。
那么如何实现一个二叉树的数据结构呢
二、数据结构的设计 在这里我们采取链表的方式即创建节点将节点与节点链接起来的方式实现二叉树。
节点的结构 1将要创建的节点的数据部分存储到数组里然后创建节点。读取数组我们将指针指向空的部分当作是非法字符在这里非法字符是‘#’
2如果不是非法字符则创建节点并链接到二叉树的根上按照先序遍历的方式先创建根再创建根的左最后创建根的右。
3创建完成后对二叉树进行相应的操作。如求叶子节点数第k层节点数四种遍历方式递归和非递归实现等。
三、实现代码
//BinaryTree.h #pragma once
#includeassert.h
#includequeue
#includestack
#includeiostream
using namespace std;templatetypename T
struct BinaryTreeNode //创建节点
{T _data;BinaryTreeNodeT *_left;BinaryTreeNodeT *_right;BinaryTreeNode(const T data):_data(data), _left(NULL), _right(NULL){}
};templatetypename T
class BinaryTree
{typedef BinaryTreeNodeT Node;
public:BinaryTree():_root(NULL){}BinaryTree(T* arr,size_t size,const T invalid T()){assert(arr);size_t index 0;_root CreateTree(arr,size,invalid,index);}BinaryTree(BinaryTreeT t){assert(t._root);_root _Copy(t._root);}//传统写法/*BinaryTreeT operator(BinaryTreeT t){if (this ! t){Node* tmp _Copy(t._root);_root _Destroy(_root);_root tmp;}return *this;}*///现代写法BinaryTreeT operator(BinaryTreeT t){if (this ! t){BinaryTreeT tmp(t);std::swap(tmp._root, _root);}return *this;}~BinaryTree(){if (_root){_root _Destroy(_root);}}
public:size_t Size(){return _Size(_root);}size_t Depth(){return _Depth(_root);}void PreOrder(){_PreOrder(_root);cout endl;}void InOrder(){_InOrder(_root);cout endl;}void PostOrder(){_PostOrder(_root);cout endl;}void LevelOrder(){_LevelOrder(_root);cout endl;}Node* Find(const T x){return _Find(_root,x);}public://创建二叉树Node* CreateTree(T* arr, size_t size, const T invalid,size_t index){Node* root NULL;if (index size){if (arr[index] ! invalid){root new Node(arr[index]);root-_left CreateTree(arr, size, invalid, index);root-_right CreateTree(arr, size, invalid, index);}}return root;}//拷贝二叉树Node* _Copy(Node* root){Node* cur NULL;if (root){cur new Node(root-_data);cur-_left _Copy(root-_left);cur-_right _Copy(root-_right);}return cur;}//释放二叉树节点Node* _Destroy(Node* root){if (root ! NULL){root-_left _Destroy(root-_left);root-_right _Destroy(root-_right);delete root;root NULL;}return root;}//递归求解二叉树节点的个数size_t _Size(Node* root) {if (root NULL)return 0;return _Size(root-_left) _Size(root-_right) 1;}//二叉树的深度求解size_t _Depth(Node* root){size_t maxDepth 1;if (root){size_t depth 1;if (root-_left) //左不为空则遍历左树的深度{depth _Depth(root-_left);}if (depth maxDepth){maxDepth depth;}if (root-_right) //右不为空则在左树的深度基础上1{depth _Depth(root-_right) 1;}if (depth maxDepth){maxDepth depth;}}return maxDepth;}//二叉树前序遍历的递归实现void _PreOrder(Node* root){if (root){cout root-_data ;_PreOrder(root-_left);_PreOrder(root-_right);}}//二叉树中序遍历的递归实现void _InOrder(Node* root){if (root){_InOrder(root-_left);cout root-_data ;_InOrder(root-_right);}}//二叉树后序遍历的递归实现void _PostOrder(Node* root){if (root){_PostOrder(root-_left);_PostOrder(root-_right);cout root-_data ;}}//二叉树层序遍历的实现void _LevelOrder(Node* root){queueNode* q;if (root)q.push(root);while (!q.empty()){Node* front q.front();cout front-_data ;q.pop();if (front-_left){q.push(front-_left);}if (front-_right){q.push(front-_right);}}}//二叉树中查找某个值的节点Node* _Find(Node* root,const T data){Node* cur root;if(root NULL)return NULL;if(root-_data data) //找到则返回节点return root;Node* ret _Find(cur-_left,data);if(ret NULL){ret _Find(cur-_right,data);}return ret;}
public:void PreOrderNonR(){_PreOrderNonR(_root);coutendl;}void InOrderNonR(){_InOrderNonR(_root);coutendl;}void PostOrderNonR(){_PostOrderNonR(_root);coutendl;}
public://二叉树前序遍历的非递归实现void _PreOrderNonR(Node* root){Node* cur root;stackNode* s;while(!s.empty() || cur){while(cur){coutcur-_data ;s.push(cur);cur cur-_left;}Node* top s.top();s.pop();cur top-_right;}}//二叉树中序遍历的非递归实现void _InOrderNonR(Node* root){Node* cur root;stackNode* s;while(!s.empty() || cur){while(cur){s.push(cur);cur cur-_left;}Node* top s.top();couttop-_data ;s.pop();cur top-_right;}}//二叉树后序遍历的非递归实现void _PostOrderNonR(Node* root){Node* cur root;stackNode* s;Node* prev NULL;while(!s.empty() || cur){while(cur){s.push(cur);cur cur-_left;}Node* top s.top();if(top-_right NULL || top-_right prev){couttop-_data ;prev top;s.pop();}else{cur top-_right;}}}
public:size_t GetKLevelSize(size_t k){assert(_root);size_t level 1;size_t count 0;_GetKLevelSize(_root,k,level,count);return count;}//获取第k层节点的个数当k等于层数level时count否则分别遍历左树和右树void _GetKLevelSize(Node* root,size_t k,size_t level,size_t count){if(root NULL)return;if(k level){count;return;}_GetKLevelSize(root-_left,k,level1,count);_GetKLevelSize(root-_right,k,level1,count);}size_t GetLeafSize(){size_t count 0;_GetLeafSize(_root,count);return count;}//获取叶子节点当节点的左树为空且右树为空时即叶子数加1void _GetLeafSize(Node* root,size_t count){if(root NULL)return;if(root-_left NULL root-_right NULL){count;return;}_GetLeafSize(root-_left,count);_GetLeafSize(root-_right,count);}size_t SizePrev(){size_t count 0;_SizePrev(_root,count);return count;}//用引用的方法获取二叉数节点的个数(需要入栈)void _SizePrev(Node* root,size_t count){if(root NULL)return;Node* cur root;stackNode* s;while(!s.empty() || cur){while(cur){s.push(cur);count;cur cur-_left;}Node* top s.top();s.pop();cur top-_right;}}
private:Node* _root;
};void FunTest()
{int arr[] {1,2,3,#,#,4,#,#,5,6};int arr1[] { 1, 2,#, 3, #, #, 4, 5,#,6 ,#, 7,#,#,8};BinaryTreeint b1(arr,sizeof(arr)/sizeof(arr[0]),#);BinaryTreeint b6(arr1, sizeof(arr1) / sizeof(arr1[0]), #);BinaryTreeint b2(b1);BinaryTreeint b3;b3 b2;cout b1.Size() endl;cout b2.Size() endl;cout b3.Size() endl;cout b1.Depth() endl;cout b6.Depth() endl;coutb1递归先序遍历-;b1.PreOrder();coutb1递归中序遍历-;b1.InOrder();coutb1递归后序遍历-;b1.PostOrder();coutb1层序遍历-;b1.LevelOrder();coutb1非递归先序遍历-;b1.PreOrderNonR();coutb1非递归中序遍历-;b1.InOrderNonR();coutb1非递归后序遍历-;b1.PostOrderNonR();coutFind(4)?endl;coutb1.Find(4)-_dataendl;coutGetLeafSize:b1.GetLeafSize()endl;cout_SizePrev:b1.SizePrev()endl;coutb6递归先序遍历-;b6.PreOrder();coutb6递归中序遍历-;b6.InOrder();coutb6递归后序遍历-;b6.PostOrder();coutb6递归层序遍历-;b6.LevelOrder();cout第三层节点数:b6.GetKLevelSize(3)endl;cout第四层节点数:b6.GetKLevelSize(4)endl;cout第五层节点数:b6.GetKLevelSize(5)endl;coutGetLeafSize:b6.GetLeafSize()endl;cout_SizePrev:b6.SizePrev()endl;
}//BinaryTree.cpp#includeiostream
using namespace std;
#includeBinaryTree.h
int main()
{FunTest();return 0;
}四、运行结果前一篇广义表的数据结构和二叉树的数据结构也有一些类似哦。大家可以看看哒^-^
