数据结构期末复习(四)
树的相关概念
节点的度：一个节点的子树数目成为节点的度。也就是一个节点连着几个子节点的意思。
叶子节点：没有子节点的节点。
树的度：Max{所有节点的度}。
深度：就是树的高度，很好理解不解释。
二叉树的相关概念
- 有n个节点的二叉树的分支数为n-1
- 若二叉树高为h，则该二叉树最少有h个节点，最多有2^h-1个节点
- 若高度为h的二叉树具有最大数目的节点，则称其为满二叉树
- 若高度为h的二叉树除第h层外，其他各层的节点数都达到最大个数，并且第h层的节点还是连续分布的，则称其为完全二叉树。
- 具有n各节点的完全二叉树高度为log2 (n+1)取上界。
二叉树的遍历
递归算法
前序遍历
void preOrder(Node* r){ if(!r){//递归终点 return; } cout< data;//先输出 preOrder(r->left);//再递归左子树 preOrder(r->right);//再递归右子树} 中序遍历
void inOrder(Node* r){ if(!r){//递归终点 return; } inOrder(r->left);//先递归左子树 cout< data;//再输出 inOrder(r->right);//再递归右子树} 后序遍历
void postOrder(Node* r){ if(!r){ return ; } postOrder(r->left);//先递归左子树 postOrder(r->right);//再递归右子树 cout< data;//最后输出} 层次遍历
void Level(Node* r){ queue q; if(!r){ return; } Node* p; q.push(r); while(!q.empty()){ p = q.front();//取出元素 cout< data;//访问 q.pop();//出队 if(p->left){ q.push(p->left); } if(p->right){ q.push(p->right); }//由于是按照先左后右的顺序入队的，出队的顺序在同一层里也是先左后右 //因此实现了层次遍历 }} 非递归算法
栈可以实现非递归的二叉树三种遍历，实际上栈的作用是存储访问的顺序，这样就不需要再回溯找，直接能够通过取出栈顶元素得到下一个应该被访问的节点。
前序遍历
用栈：
void preOrder(Node* r){ stack s; Node* p = r; while(!s.empty() || p){ while(p){//如果p不为NULL，就一直往左遍历，边遍历边输出。 cout< data; s.push(p); p=p->left; }//出循环的时候一条路上的所有偏左的节点都被访问过了 if(!s.empty()){//依次取出路径上保存的元素，从他们的右节点继续上面的循环 p=s.top(); s.pop(); p=p->right; }//这里如果p->right ==null不会执行while(p)循环，而是再次去取栈顶元素，从下一个右节点开始。 }} 不用栈（三叉链表）:
void preOrder(Node* r){ Node* p =r;//三叉链表的parent节点方便了回溯，因为parent节点反应了从上到下的遍历路径，因此可以通过父节点找到遍历路径上的节点 while(p){ cout< data; if(p->left){//先使劲往左遍历，边遍历边输出 p=p->left; }else if(p->right){//如果节点只有右子树，就使劲往右遍历 p=p->right; }else{//对于叶子节点，需要向上回溯找到第一个未被访问的第一个右子树的根节点 Node* q=p->parent; while(q && (q->right==p || !q->right)){ //q->right==p表明从左往上回溯，不符合 //q->right == NULL完全没右子树，当然也不符合找右子树根节点的规则 p=q; q = q->parent; } if(!q){//全部访问完的时候 p=r,q=NULL，结束循环 break; } } }} 后面除了双栈就不写注释了，太麻烦。思想都是一样的。
中序遍历
用栈：
void inOrder(Node* r){ stack s; Node* p = r; while(!s.empty() || p){ while(p){ s.push(p); p=p->left; } if(!s.empty()){ p=s.top(); s.pop(); cout< data; p=p->right; } }} 不用栈（三叉链表）:
void inOrder(Node* r){ Node* p =r; Node* q; while(p){ if(p->left){ p=p->left; }else if(p->right){ cout< data; p=p->right; }else{ cout< data; Node* q=p->parent; while(q){ if(!q->right){ cout< data; }else if(q->left==p){ cout< data; break; } p=q; q = q->parent; } if(!q){ break; } } }} 后序遍历
用栈：
void inOrder(Node* r){ stack s1,s2; //用两个栈来存储，第一个栈是从右往左的访问顺序，第二个栈的接收顺序是先根再左再右，符合后序遍历规则 Node* p; s1.push(p); while(!s1.empty()){ p = s1.top(); s1.pop(); if(p->left){ s1.push(p->left); } if(p->right){ s1.push(p->right); } //注意这里先左子树入栈s1,再右子树入栈s2，然后根节点入栈s2 //那么在后面的循环里面，必定右子树的节点先入栈s2，左子树的节点后入栈s2 //导致的结果就是，根节点被压在栈底，左子树次之，右子树最上 s2.push(p); } while(!s2.empty()){ p=s2.top(); s2.pop(); cout< data; }} 不用栈（三叉链表）:
void postOrder(Node* r){ Node* p =r; Node* q; while(p){ if(p->left){ p=p->left; } if(p->right){ p=p->right; }else{ cout< data; q=p->parent; while(q){ if(!q->right){//右子树不存在。就输出它，继续向上找 cout< val<<" "; p=q; q=q->parent; continue; } if(q->left==p){//如果是从左边过来的，右子树就是回溯的节点 p=q->right; break; }else{//如果是从右边过来的，说明左右子树都已经访问完了，这个节点可以输出了，继续向上回溯 p=q; q=q->parent; cout< val<<" "; } } if(!q){//所有元素都输出完的终点是q==NULL，跳出循环 break; } } }}