树算法总结（红皮书+王道）

遍历算法

先序遍历

从上往下找，也适用于一些算法

递归算法：

void PreOrder(tree root){if(root!=NULL){printf("%d ",root->data);PreOrder(root->left);PreOrder(root->right);}
} 

非递归算法1：（类似于深度的非递归）

void PreOrder_2(tree root){tree stack[maxsize];int top = -1;tree p = root;while(p || top != -1){if(p){printf("%d ", p->data);		//一直遍历左子树stack[++top] =  p;p = p->left;	}else{							//左子树不存在遍历右子树p = stack[top--];p = p->right;}}
} 

非递归算法2:(类似于层次的非递归)

void PreOrder_3(tree root){	tree stack[maxsize];int top = -1;tree p = root;stack[++top] = p;while(p || top != -1){p = stack[top--];printf("%d ", p->data);			if(p->right) stack[++top] = p->right;		//先访问右子树，入栈，出栈的顺序就是左子树、然后右子树 if(p->left)  stack[++top] = p->left;}
}

应用1、删除以x为根的子树，不包含节点本身（从上往下找）

**思路：**从上往下找，找到节点值为x的，然后删除其左右子树

代码：

void Release(tree root){//释放以root为根的所有节点 if(root){Release(root->left);Release(root->right);free(root);}
} void Del_X(tree root, int x){//先序递归遍历 if(root == NULL) return;if(root->left && root->left->data==x){Release(root->left);root->left = NULL;}else if(root->right && root->right->data == x){Release(root->right);root->right = NULL;}else{Del_X(root->left,x);Del_X(root->right,x);}	
}

中序遍历

递归算法

void InOrder(tree root){if(root!=NULL){InOrder(root->left);printf("%d ",root->data);InOrder(root->right);}
}

非递归算法

void InOrder_2(tree root){tree stack[maxsize];int top = -1;tree p = root;while(p || top != -1){if(p){stack[++top] = p;					//左子树入栈，先不访问 p = p->left;}else{p = stack[top--];					//出栈后，再访问，访问完转右子树 printf("%d ", p->data);p = p->right;}}
} 

后序遍历

很重要，因为它是从先访问了左右子树然后根节点往上遍历的一个典型代表，可以运用到很多方面

递归算法

void PostOrder(tree root){if(root!=NULL){PostOrder(root->left);PostOrder(root->right);printf("%d ",root->data);	}
} 

非递归算法1

void PostOrder_2(tree root){tree stack[maxsize];int top = -1;tree p = root,r;							//添加标志位r，判断右子树是否访问 while(p || top!=-1){if(p){stack[++top] = p;					//左子树入栈 p = p->left;}else{p = stack[top];						//先取栈顶，不出栈 if(p->right && p->right != r){p = p->right;					//右子树未被访问，那先访问右子树 }else{								//访问过了，那就出栈 top--;printf("%d ",p->data);			//访问 r = p;							//标记前一个节点 p = NULL;						//已经访问过，置空 }}}
} 

非递归算法2（基于先序遍历）

思路：先序遍历：根左右 ===> 先访问右子树，再访问左子树，得到 根右左 ===> 入栈，再出栈，得到 左右根（后序遍历结果）

void PostOrder_3(tree root){		//先序遍历的改装，两个栈 tree stack1[maxsize];			//栈1用来先序遍历的非递归遍历 tree stack2[maxsize];			//栈2保存后序遍历的结果	int top1 = -1, top2 = -1;tree p = root;while(top1!=-1 || p){	if(p){stack1[++top1] = p;		stack2[++top2] = p;		p = p->right;			//先访问右子树}else{p = stack1[top1--];p = p->left;			//再访问左子树}}while(top2!=-1){printf("%d ", stack2[top2--]->data);}
} 

应用1 计算双分支节点个数（从下往上找）

思路： 递归遍历，如果当前节点为双分支节点，返回左子树双分支节点和右子树双分支节点个数+1，否则不加1

代码：

int DsonNodes(tree root){if(root == NULL) return 0;if(root->left != NULL && root->right != NULL){//双分支节点return DsonNodes(root->left)+DsonNodes(root->right)+1;}else{//不是双分支节点return DsonNodes(root->left)+DsonNodes(root->right);}
}

应用2 交换所有左右子树 （从下往上交换）

思路： 递归遍历，到下一层为根节点的时候，交换左右子树

代码：

void SwapTree(tree root){if(root){			//从下往上交换SwapTree(root->left);SwapTree(root->right);tree t = root->left;root->left = root->right;root->left = t;}
}

应用3 利用中序和先序序列构建二叉树,二叉树节点值各不相同 （从下往上建立）

思路： 找到根节点位置，划分左右子树，然后递归建立左右子树，注意下标对应关系

代码：

tree PreInCreate(int pre[], int in[], int f1, int e1, int f2, int e2){//f1 e1 为先序的起始和终止位置 f2 e2 为中序的起始和终止位置 tree root =  (struct tnode *)malloc(sizeof(struct tnode));root->data = pre[f1];int pos=f2;while(in[pos] != pre[f1]) pos++;			//找到根节点位置int llen = pos - f2;						//左子树长度 int rlen = e2 - pos;						//右子树长度if(llen){									//左子树不为空，递归建立左子树 root->left = PreInCreate(pre,in,f1+1,f1+llen,f2,f2+llen-1);} else{										//左子树为空 root->left = NULL;}if(rlen){									//右子树不为空，递归建立左子树 root->right = PreInCreate(pre,in,e1-rlen+1,e1,e2-rlen+1,e2);}else{										//右子树为空root->right = NULL;}return root; 								//返回结果 
}

应用4 查找节点值x的祖先节点

思路： 后序非递归遍历查找到x节点时，栈中保存的节点就是x的祖先节点

代码：

void SearchAncestor(tree root, int x){tree stack[maxsize];int top = -1;tree p = root,r=NULL;while(p || top != -1){if(p){stack[++top] = p;p = p->left;}else{p = stack[top];if(p->right && p->right != r){p = p->right;}else{if(p->data == x) break;		//找到了 top--;r = p;p = NULL;}}}printf("%d的祖先节点有：",x); while(top!=-1){printf("%d ", stack[top--]->data);} 
} 

层次遍历

基础算法

思路： 队列，不断的出队，入队访问

代码：

void BFS_Tree(tree root){tree queue[maxsize];int front = -1, rear = -1;tree q;queue[++rear] = root;while(rear != front){q = queue[++front];printf("%d ",q->data);if(q->left) queue[++rear] = q->left;if(q->right) queue[++rear] = q->right;}
} 

应用1 从下而上，从左而右的层次遍历

二叉树自下而上，从右往左的层次遍历算法 这个比较简单，直接层次遍历入栈，然后出栈便得到了
变形 ：二叉树自下而上，自左而右的层次遍历算法

思路： 按层遍历，是利用两个栈，每一层的节点入栈后，然后出栈入另外一个栈2，栈2最后出栈便是最后的结果

代码：

void InvertLevel_2(tree root){tree stack1[maxsize];			//栈1保存每一层的节点 tree stack2[maxsize];			//栈2保存最后的结果 int top1 = -1, top2  = -1;tree queue[maxsize];			//队列用于层次遍历 int front = -1, rear = -1;tree p = root;queue[++rear] = p;while(rear != front){int n = rear - front;			//每一层的个数 for(int i = 0; i < n; i++){		//先访问每一层的节点 p = queue[++front];stack1[++top1] = p;			//每一层的节点入栈1 if(p->left) queue[++rear] = p->left;if(p->right) queue[++rear] = p->right;}while(top1!=-1){				//栈2得到从右到左的每一层节点个数，出栈便是从左到右 stack2[++top2] = stack1[top1--];}}while(top2!=-1){printf("%d ",stack2[top2--]->data);}
} 

应用2 层次遍历判断是否是完全二叉树

思路： 层次遍历，无需判断左子树还是右子树是否为空，直接入队列，然后不断出队，出队元素如果是空，继续判断后序节点是否为空，出现了不为空，就不是完全二叉树

代码：

bool IsComlepteTree(tree root){tree queue[maxsize];int front = -1, rear = -1;tree p = root;queue[++rear] = p;while(rear != front){p = queue[++front];if(p){			//不为空，则将左右节点入队列 queue[++rear] = p->left;queue[++rear] = p->right;}else{			//为空，判断后序节点 while(rear!=front){p = queue[++front];if(p){	//存在不为空的节点，说明不是完全二叉树 return 0;}}	}}return 1; 
}

应用3 层次遍历求树的宽度

int WidthTree(tree root){//按层的层比遍历，统计每层节点个数tree queue[maxsize];int front = -1, rear = -1;tree p = root;int maxwidth = 0,width;queue[++rear] = p;while(rear != front){int n = rear - front;if(n > maxwidth) maxwidth = n;for(int i =0; i < n; i++){p = queue[++front];if(p->left) queue[++rear] = p->left;if(p->right) queue[++rear] = p->right;}}return maxwidth;
} 

求树高

递归求树高

代码：

int HighTree(tree root){//后序遍历得到树高if(root == NULL) return 0;int l = HighTree(root->left);int r = HighTree(root->right);return l > r ? l+1 : r+1; 
} 

非递归求树高

思路：按层遍历的层次遍历

代码：

int HighTree_2(tree root){tree queue[maxsize];int front = -1, rear = -1;tree p = root;int level = 0;queue[++rear] = p;while(rear != front){int n = rear - front;				//每层节点个数level++;for(int i =0; i < n; i++){			//遍历p = queue[++front];if(p->left) queue[++rear] = p->left;if(p->right) queue[++rear] = p->right;}}return level;
} 

应用1 判断是否是平衡二叉树

思路： 求树高的过程中，判断是否为完全二叉树，赋值为-1保存结果

int AVLHigh(tree root){if(root == NULL) return 0;int l = HighTree(root->left);int r = HighTree(root->right);if(l == -1 || r == -1 || abs(l-r)>1){	//不是完全二叉树return -1;}return l > r ? l+1 : r+1; 
} bool Is_AVL(tree root){if(AVLHigh(root)>=0) return true;else return false;
}

其他算法

1、找按顺序存储的完全二叉树，节点为i和j的公共祖先

思路： 子节点与父节点关系 i = i/2;为父节点下标，注意下标是以1开头

代码：

int Common_Ancestor(int a[], int i, int j){//数组下标从1开始存储 if(a[i] && a[j]){while(i != j){if(i > j){i = i/2;}		else{j = j/2;}	}}printf("%d ",a[i]);return a[i];
}