概览
- 二叉树的链表和静态链表的定义
- 二叉树的遍历（先序遍历、中序遍历、后序遍历、层次遍历，前三者又分为递归和非递归）
- 重建二叉树
- 二叉排序树（BST）
- 完全二叉树（CBT）
- 平衡二叉树（AVL）
- 红黑树
二叉树结点的定义
struct Node{ int val; Node *lchild,*rchild; Node(int v):val(v),lchild(nullptr),rchild(nullptr){} };
树的内容主要围绕在树的遍历中展开，有先序遍历，中序遍历，后序遍历和层序遍历。其中，前三种遍历又分为递归式写法和非递归式的写法，递归式的写法更简洁，是重点，是DFS的思想；非递归式代码比较繁琐。层序遍历则是BFS的思想，借助队列实现。
1、二叉树的遍历
先序遍历、中序遍历、后序遍历的递归写法以及层次遍历不再讨论。这里主要记录一下后序遍历的非递归写法。非递归写法需要借助栈实现，当访问到结点v时，栈中存放的元素恰为结点v的所有父节点。
//非递归后序遍历 void postOrderTraversal(Node* root) { stack<Node*> st; Node* pNode=root; Node* pLastVisit=nullptr;//标记上一次刚访问过的结点 while(pNode || !st.empty()){ if(pNode!=nullptr){ st.push(pNode); pNode=pNode->lchild; }else{ pNode=st.top(); //如果栈顶元素有右孩子且右孩子尚未被访问 if(pNode->rchild!=nullptr && pNode->rchild!=pLastVisit){ pNode=pNode->rchild; st.push(pNode); pNode=pNode->lchild; }else{ printf("%d ",pNode->val); st.pop(); pLastVisit=pNode; pNode=nullptr;//访问过的结点置空，防止其再次入栈 } } } }
2、重建二叉树
常考的点有利用二叉树的前序序列+中序序列，或后序序列+中序序列，或层序序列+中序序列构建二叉树（构建的树唯一）；还有前序序列+后序序列构建二叉树（构建的树可能不唯一）。
(1)、前序序列+中序序列：
Node* buildBiTree(vector<int> pre,int preL,int preR,vector<int> in,int inL,int inR) { if(preL>preR || inL>inR) return nullptr; int rootVal=pre[preL]; Node* root=new Node(rootVal); int pos=inL;//记录根结点在中序序列中出现的位置 while(in[pos]!=rootVal) pos++; int leftCnt=pos-inL;//左子树的结点个数 root->lchild=buildBiTree(pre,preL+1,preL+leftCnt,in,inL,pos-1); root->rchild=buildBiTree(pre,preL+leftCnt+1,preR,in,pos+1,inR); return root; }
(2)、后序序列+中序序列：（这个与"前序+中序"思路一样）
Node* buildBiTree(vector<int> post,int postL,int postR,vector<int> in,int inL,int inR) { if(postL>postR || inL>inR) return nullptr; int rootVal=post[postR]; Node* root=new Node(rootVal); int pos=inL;//记录根结点在中序序列中出现的位置 while(in[pos]!=rootVal) pos++; int leftCnt=pos-inL;//左子树的结点个数 root->lchild=buildBiTree(post,postL,postL+leftCnt-1,in,inL,pos-1); root->rchild=buildBiTree(post,postL+leftCnt,postR-1,in,pos+1,inR); return root; }
(3)、层序序列+中序序列：（这个PAT还没有考过）
Node* buildBiTree(vector<int> layer,vector<int> in,int inL,int inR) { if(layer.size()==0 || inL>inR) return nullptr; int rootVal=layer[0]; Node* root=new Node(rootVal); int pos=inL; while(in[pos]!=rootVal) pos++; vector<int> layerLeft,layerRight;//存放左、右子树的层序序列 for(int i=1;i<layer.size();i++){ int j; for(j=inL;j<pos;j++){ if(layer[i]==in[j]){ layerLeft.push_back(layer[i]); break; } } if(j==pos) layerRight.push_back(layer[i]); } root->lchild=buildBiTree(layerLeft,in,inL,pos-1); root->rchild=buildBiTree(layerRight,in,pos+1,inR); return root; }
(4)、前序序列+后序序列：构建的二叉树可能不唯一，当无法确定某个节点是左孩子还是右孩子的时候，统一视为左孩子。详见1119 Pre- and Post-order Traversals
Node* buildBiTree(vector<int> pre,int preL,int preR,vector<int> post,int postL,int postR) { //注意边界 if(preL>preR || postL>postR) return nullptr; if(preL==preR) return new Node(pre[preL]); int rootVal=pre[preL];//前序序列的首个元素即根结点 Node* root=new Node(rootVal); int temp=pre[preL+1];//根结点后面的一个元素，即根结点的孩子 int pos=postL;//记录元素temp在后序序列的位置 while(post[pos]!=temp) pos++; int leftCnt=pos-postL+1;//以temp为根结点的子树的结点个数 if(leftCnt==preR-preL){//说明结点temp是根结点rootVal唯一的一个孩子，但不确定是左还是右 root->lchild=buildBiTree(pre,preL+1,preL+leftCnt,post,postL,pos); root->rchild=nullptr; }else{ root->lchild=buildBiTree(pre,preL+1,preL+leftCnt,post,postL,pos); root->rchild=buildBiTree(pre,preL+leftCnt+1,preR,post,pos+1,postR-1); } return root; }
3、二叉搜索树（BST）
二叉搜索树的数据域满足：左子树<根结点<右子树，利用这个特点，对二叉搜索树进行中序遍历，得到的结果序列是有序的。这是个很有用的性质，但是需要注意的是，在以往的刷题过程中，当遇到二叉搜索树的题目时（一般会给出前序序列），还是用前面那种【前序+中序】的方式构建二叉搜索树，这样做费时费力。因为，对于二叉搜索树，利用前序序列作为结点的插入顺序，可直接构建二叉树。这里需要明确的关系是：二叉搜索树的树形结构是由插入序列决定的，同样一组数，若插入的顺序不同，则得到的BST也不同。特别地，若以该二叉树的前序序列作为插入序列，则得到的二叉树的前序序列就是原插入序列。有点绕...，如插入顺序是 5,3,7,4,2,8,6 ，则得到的BST为
但是，以 5,3,2,4,7,6,8 的顺序插入得到的结果是相同的，而{5,3,2,4,7,6,8}恰为这棵树的前序序列。因此，我想借此说明的就是——若要判定某个序列是否为BST的前序序列，可以将其作为插入序列快速构建好BST，然后再遍历得到该BST的前序序列，将该序列与原序列比较即可。
插入操作：
void insert(Node* &root,int key) { if(root==nullptr){ root=new Node(key); return; } if(key<root->val) insert(root->lchild,key); else insert(root->rchild,key); }
删除操作：暂时不写
4、完全二叉树（CBT）
对于完全二叉树而言，除了可以用常见的链式存储外，更方便的是用数组存储（下标从1开始），一般涉及完全二叉树的题目时，应首先想到这个方法。用数组存储，有如下的性质：（假设共有n个结点）
(1)、某结点下标为i，其左孩子结点为2*i，右孩子结点为2*i+1（如果有孩子的话）
(2)、最后一个非叶结点为在n/2处
(3)、判断结点是否为空时，检查该结点的下标idx是否大于n
(4)、顺序遍历数组1~n的结果恰是该完全二叉树的层序遍历序列
熟悉这些性质，当涉及CBT的题目时，就不应该傻不拉几的按照一般的做法去思考了。利用好性质，代码量可以大幅度减少，节约时间。（教训较大的两道题，1064 Complete Binary Search Tree，1147 Heaps）
比如，遍历一棵完全二叉树，要先用常规方法那样建树，然后遍历吗？没必要啊！以中序遍历CBT为例，如下：
int CBT[N];//从下标为1处开始存放 void inOrderTraversal(int root) { if(root>n) return; inOrderTraversal(root*2);//遍历左子树 //do something here inOrderTraversal(root*2+1); }
5、平衡二叉树（AVL）
具体的讲解《算法笔记》里已经讲的很清楚了，没什么好说的。模板，记住。例题：1066 Root of AVL Tree；1123 Is It a Complete AVL Tree
6、红黑树（具体的实现待考完再补充）例题：1135 Is It A Red-Black Tree
- 还没有人评论，欢迎说说您的想法！
客服
