二叉树也是常用的数据结构,通过使用二叉树可以快速的对数据进行排序或者查找,在常用的堆排序算法中,堆的底层实质就是一个模拟的完全二叉树!等等,什么是完全二叉树?二叉树又是什么?有哪几类?让我们开始今天的算法课堂~
二叉数的概念和分类
二叉树是每个树节点最多有两个子树的一种特殊的树结构,其有一些内在的性质,比如,若二叉树的层次从0开始,则在二叉树的第i层至多有2^i个节点(i>=0),高度为k的二叉树最多有2^(k+1)-1个节点(空树的高度为-1)。其类别为以下几种:
满二叉搜索树
二叉树的遍历
二叉树的遍历有三种方式:先序遍历,中序遍历,后序遍历。思路很简单,这里面说的顺序的序是指每个子树根节点的遍历(打印)顺序。不懂的话可以看上图,红色的点表示该节点打印,下方为遍历得到的打印顺序。
接下来我们以这个图为例进行Coding,用代码来实现这三种遍历方式:
递归版本(先、中、后序)
递归版的遍历算法很简单了,我们只需要改变打印次序就好了,也没有什么可讲的!
// 递归版// 先序遍历void printPreorder1(TreeNode* head){
if (head == nullptr){
return;
}
cout << head->value << " ";
printPreorder1(head->left);
printPreorder1(head->right);}// 中序遍历void printInorder1(TreeNode* head){
if (head == nullptr){
return;
}
printInorder1(head->left);
cout << head->value << " ";
printInorder1(head->right);}// 后序遍历void printPostorder1(TreeNode* head){
if (head == nullptr){
return;
}
printPostorder1(head->left);
printPostorder1(head->right);
cout << head->value << " ";}
非递归版本(先、中、后序)
首先我们要清楚,任何算法的递归版本都可以改成非递归版本,因为函数递归调用其实质就是压栈的过程,那么我们完全可以使用堆栈来模拟这个过程!
先序遍历:
我们将数的每个节点压入栈中,由于是先序遍历,首先压入的是根节点,然后弹出(弹出节点时打印信息,且一个循环弹出一个节点),接着是压入右子树节点,最后压入左子树节点。为什么要这样呢?由于堆栈是“先进后出”结构,我们想要先打印左子树,因此最后压入左子树,循环这个过程,就达到了我们的目的。
// 迭代版
void printPreorder2(TreeNode* head){
cout << "Pre Order:" << endl;
if (head != nullptr){
stack<TreeNode*> *sta = new stack<TreeNode*>;
sta->push(head);
TreeNode* cur = head;
while(!sta->empty()){
cur = sta->top();
sta->pop();
cout << cur->value << " ";
if (cur->right != nullptr){
sta->push(cur->right);
}
if (cur->left != nullptr){
sta->push(cur->left); // 先压右边节点,再压左边节点,这与栈的特性有关
}
}
}
cout << endl;
}
中序遍历:
中序时,我们首先去遍历二叉树的左分支,并将节点压入栈中,只到找到最左边的叶节点,接着弹出(并打印节点),并看其有没右分支,如果没有,栈再弹出一个节点(根节点),看其有没有右分支。每次弹出,都要观察其是否有右分支,也就是说每个节点都遍历了两次!
void printInorder2(TreeNode* head){
cout << "In Order:" << endl;
if(head != nullptr){
stack<TreeNode*>* sta = new stack<TreeNode*>;
TreeNode* cur = head;
while(!sta->empty() || cur != nullptr){
if(cur != nullptr){
sta->push(cur);
cur = cur->left;
}else{
cur = sta->top();
sta->pop();
cout << cur->value << " ";
cur = cur->right;
}
}
}
cout << endl;
}
后序遍历:
后序遍历在意思上和前序遍历相近,而前序遍历的压栈顺序为:根、右、左。那么如果我们使用两个堆栈,第一个压栈顺序为:根、左、右,但是在(先序遍历时)弹出根节点时将根节点压入第二个堆栈,为什么这里压栈顺序要为左右呢?很简单,在第一个堆栈中最后压入右子树,那么右子树会最先压入第二个堆栈,相应的,当第二个堆栈弹出时,右子树会在左子树的后面弹出(先进后出)。注意:根节点是最先被压入第一个栈中的,同时也是最先被压入第二个栈中的!
void printPostorder2(TreeNode* head){
cout << "Post Order:" << endl;
if (head != nullptr){
stack<TreeNode*>* sta1 = new stack<TreeNode*>;
stack<TreeNode*>* sta2 = new stack<TreeNode*>;
TreeNode* cur = head;
sta1->push(cur);
while(!sta1->empty()){
cur = sta1->top();
sta1->pop(); // 弹出的是最晚被压入栈的数据
sta2->push(cur);
if(cur->left != nullptr){
sta1->push(cur->left);
}
if(cur->right != nullptr){
sta1->push(cur->right);
}
}
while(!sta2->empty()){
cur = sta2->top();
sta2->pop();
cout << cur->value << " ";
}
}
cout << endl;
}
疑问:测试文件new出的对象,没有delete.
答:由于只是刷题测试,new出的空间释放过于麻烦,只要这个进程关闭(运行结束),操作系统会自动回收不用的内存,所以不用delete也行。但工程上一定不要忘了,不然一直运行会导致内存充满,程序崩溃!