树结构汇总1 .树关联1.1树和关联概念1.2树的表示方法1.3树的应用场景2.5.2二叉树2.1二叉树的性质2.2满二叉树2.3完全二叉树2.4堆栈2.5二叉树的基本操作2.5.1遍历2.5.2
1.1树相关1.1树及相关概念
树是由n个节点组成的有限集合，n=0时是空树，每个非空树都有根节点。
每个节点可以有多个子节点，没有子节点的节点称为叶节点。
深度：从根节点到任意一个节点的路径较长，根节点深度为1。
高度：因为从任一节点到叶节点的最长路径很长，所以叶节点的高度为0。
一棵树的高度等于根节点的高度。
1.2树的表示方法普通树：
普通树中的节点可以有多个子节点
树有几种表示方法。
父母表记法
儿童书写法
机智的发卡表示法
树的三种表示
1.3树的应用场景1、创建目录
目录有一个辅助目录，辅助目录有一个三级目录，整个结构类似一个树
2、思维导图
3、霍夫曼编码
4、linux虚拟内存管理
5、b、B-树(索引) ) ) )。
6、C STL的映射、多映射、集、多集
2.1二叉树的2.1二叉树的性质二叉树的节点最多有两个左右子节点(度最大为2 )，如：
属性：
1、二叉树的第I层(i=1)最多有2I1 )2^{I-1}2I1个节点
2、深度为k(k=0)的二叉树最少具有k个节点，最多具有2k1 )2^k-1 )2k1个节点
3、对于任意一棵非空二叉树，其叶节点数为n1，频数2的非叶的节点数为n2，且n1=n2 1
4、具有n个节点的完全二叉树的最小深度为log2(n1 ) log_{2}{(n1 ) }log2 ) n1 )
2.2假设二叉树的高度为k，则只要有2 k 1 2^k-1 2k1个节点，就会填满二叉树。 简单地说，每个非叶节点有两个子节点
2.3完全二叉树的高度为k，则除第k层外，1~k-1层节点均最大，且第k层节点编号均与高度为k的二叉树编号相对应，即为完全二叉树。 例如：
2.4堆积具有一定特性的完全二叉树，一般用数组形式表示
山分为大山和小山：
大山：
除叶之外的所有节点都大于其左右子节点
表达式表示vec[i]=vec[2i 1] vec[i]=vec[2i 2]
一堆小天花板：
除叶之外的所有节点都小于其左右子节点
表达式表示vec[i]=vec[2i 1] vec[i]=vec[2i 2]
可以看到回答者写的堆叠顺序：
各种排序总结
2.5二叉树的基本操作2.5.1实现二叉树的节点结构
templatetypenametclassbinarytreenode { public : tval； 瓶子
aryTreeNode<T>* left = nullptr;BinaryTreeNode<T>* right = nullptr;BinaryTreeNode(T data) :val(data){};//构造函数};二叉树结构
template<typename T>class BinaryTree{public:BinaryTree(){}void Add(T data);void DestoryBinaryTree(BinaryTreeNode<T> * node);BinaryTreeNode<T>* getRoot(){return root;}~BinaryTree(){DestoryBinaryTree(root);}private:BinaryTreeNode<T> * root = nullptr;};增加元素函数
template<typename T>void BinaryTree<T>::Add(T data){BinaryTreeNode<T> * node = new BinaryTreeNode<T>(data);queue<BinaryTreeNode<T>*> que;que.push(root);if (!this->root){root = node;return;}while (!que.empty()){BinaryTreeNode<T> * temp = que.front();que.pop();if (!temp->left){temp->left = node;return;}else{que.push(temp->left);}if (!temp->right){temp->right = node;return;}else{que.push(temp->right);}}}删除元素
template<typename T>void BinaryTree<T>::DestoryBinaryTree(BinaryTreeNode<T> * node){if (node)//如果有节点{if (node->left)//如果存在左孩子{DestoryBinaryTree(node->left);//销毁二叉树的左子树}if (node->right){DestoryBinaryTree(node->right);//销毁二叉树的右子树}}delete node;//销毁节点node = nullptr;} 2.5.2遍历 2.5.2.1层序遍历 void LevelOrder(BinaryTreeNode<T> * node){if (!node){return;}queue<BinaryTreeNode<T> *> que;que.push(node);while (!que.empty()){BinaryTreeNode<T> * temp = que.front();que.pop();cout << temp->val << " ";if (temp->left){que.push(temp->left);}if (temp->right){que.push(temp->right);}}} 2.5.2.2前序遍历递归
void PreOrder(const BinaryTreeNode<T> * node ){if (!node){return;}cout << node->val << " ";PreOrder(node->left);PreOrder(node->right);}非递归
void WPreOrder(BinaryTreeNode<T> * node){if (!node){return;}stack<BinaryTreeNode<T> *> stk;BinaryTreeNode<T> * temp = node;while (!stk.empty() || temp){if (temp){stk.push(temp);cout << temp->val << " ";temp = temp->left;}else{temp = stk.top();stk.pop();temp = temp->right;}}} 2.5.2.3中序遍历递归
void InOrder(const BinaryTreeNode<T> * node){if (!node){return;}InOrder(node->left);cout << node->val << " ";InOrder(node->right);}非递归
void WInOrder(BinaryTreeNode<T> * node){if (!node){return;}stack<BinaryTreeNode<T> *> stk;BinaryTreeNode<T> * temp = node;while (!stk.empty() || temp){if (temp){stk.push(temp);temp = temp->left;}else{temp = stk.top();stk.pop();cout << temp->val << " ";temp = temp->right;}}} 2.5.2.4后序遍历递归
void PostOrder(const BinaryTreeNode<T> * node){if (!node){return;}PostOrder(node->left);PostOrder(node->right);cout << node->val << " ";}非递归`
void WPostOrder(BinaryTreeNode<T> * node){stack<BinaryTreeNode<T>*> stk1;stack<BinaryTreeNode<T>*> stk2;stk1.push(node);BinaryTreeNode<T>* temp;while (!stk1.empty()){temp = stk1.top();stk1.pop();stk2.push(temp);if (temp->left){stk1.push(temp->left);}if (temp->right){stk1.push(temp->right);}}while (!stk2.empty()){temp = stk2.top();stk2.pop();cout << temp->val << " ";}}