您好,登录后才能下订单哦!
二叉树是一种非常有用的结构,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点;深度为k的二叉树至多有2^k-1个结点;对任何一棵二叉树T,如果其终端结点数为n_0,度为2的结点数为n_2,则n_0=n_2+1。
一棵深度为k,且有2^k-1个节点称之为满二叉树;深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树。详细定义见百度百科
二叉树的结构使其在排序算法中非常有用,最有用的当属平衡二叉树,平衡二叉树将会在本人的博客中讨论。
说起二叉树,就不得不讨论一下二叉树的遍历,一般来说,二叉树的遍历方式有4种:
假设我们的树是这样的:
(一)前序遍历
首先我们得分析先序遍历的顺序:A,B,D,E,C,F,G。
树的遍历利用递归来实现会简单一点,我们将遍历一整棵树分解成遍历左子树和右子树的子问题。
void PrevOrder()//前序遍历 { _PrevOrder(_root); } void _PrevOrder(BinaryTreeNode<T>* root) { if (root == NULL) { return; } cout << root->_data <<" ";//先输出根节点 _PrevOrder(root->_left);//在输出左子树 _PrevOrder(root->_right);//最后右子树 }
(二)中序遍历
遍历的顺序:D,B,E,A,F,C,G
void MidOrder()//中序遍历 { _MidOrder(_root); } void _MidOrder(BinaryTreeNode<T>* root) { if (root == NULL) { return; } _MidOrder(root->_left); cout << root->_data << " "; _MidOrder(root->_right); }
(三)后序遍历
遍历顺序:D,E,B,F,G,C,A
void RearOrder()//后序遍历 { _RearOrder(_root); } void _RearOrder(BinaryTreeNode<T>* root) { if (root == NULL) { return; } _RearOrder(root->_left); _RearOrder(root->_right); cout << root->_data << " "; }
(四)层序遍历
遍历顺序:A,B,C,D,E,F,G
层序遍历的话可以利用队列先进先出的特点,将每一层的节点入队列,只要队列不为空,就出一次队列。
void SequenceOrder()//层序遍历 { queue<BinaryTreeNode<T>*> q; if (_root) q.push(_root); while (!q.empty()) { if (q.front()->_left) { q.push(q.front()->_left); } if (q.front()->_right) { q.push(q.front()->_right); } cout << q.front()->_data<< " "; q.pop(); } }
树的遍历是比较简单的,下面我们看一下有点难度的:
(一)求树的叶子节点的个数:
数的叶子节点总是在最深的一层。,每次当一个子问题的根节点的左右子树都为NULL时,我们就将戒子节点的个数加一,当然,可以把叶子节点定义为一个静态变量,这样,每次加的都是同一个变量上。
也可以不用定义静态的变量,因为静态变量会有线程的安全问题。
size_t LeafCount() { return _LeafCount(_root); } size_t _LeafCount(BinaryTreeNode<T>* root) { if (root == NULL) { return 0; } if (root->_left==NULL && root->_right ==NULL) { return 1; } return (_LeafCount(root->_left)+_LeafCount(root->_right)); }
(二)求树的深度
求树的深度是一个比较有难度的问题,因为我们要比较不同子树的深度的大小,然后取最大的哪一个,但是在一个递归程序中很难保证一个变量不会改变。在这里我们只要比较每个子问题中的左右字数的深度,每次返回使深度最大值加一,最后的值就是树的深度。
size_t Deepth() { return _Deepth(_root); } size_t _Deepth(BinaryTreeNode<T>* root) { if (root == NULL) { return 0; } size_t leftDeep = _Deepth(root->_left)+1; size_t rightDeep = _Deepth(root->_right)+1; return leftDeep > rightDeep ? leftDeep: rightDeep; }
(三)求树的节点的个数
这个问题是比较容易的,我们可以用任意一种遍历方式遍历这棵树,每遍历到一个节点,个数就加以。
size_t Size() { return _Size(_root); } size_t _Size(BinaryTreeNode<T>* root) { if (root == NULL) { return 0; } return _Size(root->_left) + _Size(root->_right) + 1; }
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。