首页 数据结构

# 树

// 判断是否是二叉排序树
//tips: 左根右是否是递增序列
typedef struct BiNode
{
	int data;
	BiNode *lchild,*rchild;
}BiNode,*BiTree;
bool judge(BiTree t){
	int b1,b2;
	if(b1==NULL){
		return 1;
	}// 空树
	else{
		b1 = judge(t->lchild);
		if(b1==0||pre>t->data){
			return 0;
		}
		pre = t->data;
		b2 = judge(t->rchild);
	}
	return b2;
}
// 虽然没错，但过于复杂
// bool inOrder(BiTree t,int arr[]){
// 	int i = 0;
// 	if(t!=NULL){
// 		if(t->lchild){
// 			inOrder(t->lchild,arr);
// 		}
// 		arr[++i] = t->data;
// 		if(t->rchild){
// 			inOrder(t->rchild,arr);
// 		}	
// 	}
// 	int j = 0
// 	while(j >arr.length){
// 		int temp = arr[j];
// 		j = j--;
// 		if(arr[j]>temp){
// 			return false;
// 		}
// 	}
// 	return true;
// }
#define MAXSIZE 50;
typedef struct BiTree
{
	int data;
	BiTree *lchild;
	BiTree *rchild;
}BiTree;
typedef struct Stack
{
	int data[MAXSIZE];
	int top;
}Stack;
void InitStack(Stack s){
	s.top = -1;
}
void Push(Stack &s,int k){
	if(s.top == MAXSIZE-1){
		exit(0);
	}
	s.data[++s.top] = x;
}
void Pop(Stack &s,int k){
	if(s.top == -1){
		exit(0);
	}
	k = s.data[s.top--];
}
bool isEmptyStack(Stack s){
	if(s.top == -1){
		return true;
	}else{
		return false;
	}
}
void Visit(BiTree *bt){
	printf("当前的结点为%s\n",bt);
}
// 获取栈顶元素，但不删除
void BiTree* getTop(BiTree *,int p){
}
// 查找 x 的所有祖先节点 -- 递归后序遍历
void *allAncesorOfX(BiTree *bt,int x){
	BiTree *S = (BiTree *)malloc(sizeof(BiTree)*MAXSIZE);
	InitStack(S);
	BiTree *p;
	Push(S,bt);	
	if(bt!=NULL){
		Pop(S,p);
		if(bt->data == x){
			while(!isEmpty(S)){
				Pop(S,p)
				printf("%s\n",p);
			}
		}else if(allAncesorOfX(p->lchild,x)||(allAncesorOfX(p->rchild,x))){
			Push(S,p);
		}
		
	}
}
// 非递归后续遍历查找 x 的所有祖先
#define MAXSIZE 50;
typedef struct BiTree
{
	int data;
	BiTree *lchild;
	BiTree *rchild;
}BiTree;
typedef struct Stack
{
	int data[MAXSIZE];
	int top;
}Stack;
void InitStack(Stack s){
	s.top = -1;
}
void Push(Stack &s,int k){
	if(s.top == MAXSIZE-1){
		exit(0);
	}
	s.data[++s.top] = x;
}
void Pop(Stack &s,int k){
	if(s.top == -1){
		exit(0);
	}
	k = s.data[s.top--];
}
bool isEmptyStack(Stack s){
	if(s.top == -1){
		return true;
	}else{
		return false;
	}
}
void Visit(BiTree *bt){
	printf("当前的结点为%s\n",bt);
}
// 获取栈顶元素，但不删除
void BiTree* getTop(BiTree *,int p){
}
void postOrderFindAncesorsOFx(BiTree *bt,int x){
	BiTree *Stack = (BiTree*)malloc(sizeof(BiTree)*MAXSIZE);
	InitStack(Stack);
	BiTree *p;
	BiTree *r = NULL
	Push(Stack,bt);
	while(!isEmptyStack(Stack)){
		while(p!=NULL&&p->data!=x){
			Push(p->lchild);
		}
		getTop(Stack,p);
		if(p->data == x){
			Pop(Stack,p);
			Visit(p);
			
		}
		if(p->rchild!=NULL&&p->rchild!=r){
			Push(Stack,p->rchild);
		}
		r = p;// 重点
		p = NULL;// 重点
	}
}
// 根据有序序列构造最优二叉查找树（最小高度二叉查找树）
//tips: 折半查找，二叉排序树
typedef struct BSTNode
{
	int data;
	BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
BSTree creatMinBST(int arr[],int head,int tail){
	BSTNode *root = (BSTNode *)malloc(sizeof(BSTNode));
	root->lchild = root->rchild = NULL;
	int mid = (head+tail)/2;
	root->data = arr[mid];
	root->lchild = creatMinBST(arr,head,mid);
	root->rchild = creatMinBST(arr,mid,tail);
	return root;
}
// 删除以 x 为根的子树
// 要点：层次遍历，队列，后续遍历
#define MAXSIZE 50;
typedef struct BiTree
{
	int data;
	BiTree *lchild;
	BiTree *rchild;
}BiTree;
typedef struct
{
	int data[MAXSIZE];
	int front;
	int rear;
}SqQueue;
bool isEmpty(SqQueue q){
	if(q.rear == q.front){
		return true;
	}else{
		return false;
	}
}
// 入队
bool Enque(SqQueue &q,int x){
	if((q.rear+1)%MAXSIZE == q.front){
		// 队满报错
		return false;
	}
	q.data[q.rear] = x;
	q.rear = (q.rear+1)%MAXSIZE;
	return true;
}
// 出队
bool Deque(SqQueue &q,int x){
	if(q.rear == q.front){
		// 队空报错
		return false; 
	}
	x = q.data[q.front];
	q.front = (q.front+1)%MAXSIZE;
	return true;
}
void InitQue(SqQueue &q){
		q.rear = q.front = 0;// 初始化队首队尾指针
}
void Visit(BiTree *bt){
	printf("%s\n",bt );
}
void deleteAnyX(BiTree *bt){
	deleteAnyX(bt->lchild);
	deleteAnyX(bt->rchild);
	free(bt);
}
void searchX(BiTree *bt,int x){
	BiTree *Queue = (BiTree*)malloc(sizeof(BiTree)*MAXSIZE);
	BiTree *p;
	InitQueue(Queue);
	if(bt! = NULL){
		Enque(Queue,bt);
		while(!isEmpty(Queue)){
			Deque(Queue,p)
			if(bt->data == x){
				deleteAnyX(bt);
				exit(0);
			}
			if(bt->lchild){
				if(bt->lchild-->data == x){
					deleteAnyX(bt->lchild);
					bt->lchild = NULL;
				}else{
					Enque(bt->lchild);
				}				
			}
			if(bt->rchild){
				if(bt->rchild->data == x){
					deleteAnyX(Queue,bt->rchild);
					bt->rchild = NULL;
				}else{
					Enque(Queue,bt->rchild);
				}
			}
		}
	}
}
#define MAXSIZE 20;
typedef struct BiNode
{
	int data;
	BiNode *lchild;
	BiNode *rchild;
}BiNode;
// 查找第 k 个节点的值
int findk(BiNode *bt,int k){
	int num = 0;
	int ch = 0;
	// 若当前节点为空，则使返回 “#”
	if(b == NULL){
		return "#";
	}
	
	if(num == k){
		return bt->data;
	}
	num++;
	if(bt->lchild){
		ch = findk(bt->lchild,k);
	}
	if(ch!="#"){
		return ch;
	}
	if(bt->rchild){
		ch = findk(bt->rchild,k);
	}
	return ch;
}
// 层次遍历寻找二叉树的最大宽度
// 特别注意的是这里的队列为非循环队列，否则出对后可能会被其他节点覆盖无法再求二叉树宽度
#define MAXSIZE 50;
typedef struct BiTree
{
	int data;
	struct BiTree *lchild;
	struct BiTree *rchild;
}BiTree;
typedef struct
{
	int data[MAXSIZE];
	int front;
	int rear;
}SqQueue;
bool isEmpty(SqQueue q){
	if(q.rear == q.front){
		return true;
	}else{
		return false;
	}
}
// 入队
bool Enque(SqQueue &q,int x){
	if((q.rear+1)%MAXSIZE == q.front){
		// 队满报错
		return false;
	}
	q.data[q.rear] = x;
	q.rear = (q.rear+1)%MAXSIZE;
	return true;
}
// 出队
bool Deque(SqQueue &q,int x){
	if(q.rear == q.front){
		// 队空报错
		return false; 
	}
	x = q.data[q.front];
	q.front = (q.front+1)%MAXSIZE;
	return true;
}
void InitQue(SqQueue &q){
		q.rear = q.front = 0;// 初始化队首队尾指针
}
void Visit(BiTree *bt){
	printf("%s\n",bt );
}
int levelOrder(BiTree *bt){
	BiTree *Queue = (BiTree*)malloc(sizeof(BiTree)*MAXSIZE);
	InitQue(Queue);
	BiTree *p;
	int tempLno = 0;// 每一次的临时变量，记录当前层的宽度
	int maxLno = 0;// 树的最大宽度
	Enque(SqQueue,bt);
	while(Queue.front != Queue.rear){
		Deque(Queue,p);
		tempLno++;
		if(p->lchild){
			Enque(Queue,p->lchild);
			
		}
		if(p->rchild){
			Enque(Queue,p->rchild);
		}
		
		if(tempLno>maxLno){
			maxLno = tempLno;
		}
		tempLno = 0;
	}
	return r;
}
// 求出指定节点在二叉排序树中的层次 (查找某一节点的所在树中的高度)
typedef struct BiNode
{
	int data;
	BiNode *lchild;
	BiNode *rchild;
}BiNode,*BiTree;
int findXLevel(BiTree bt,BiNode *p){
	int i = 1;
	BiTree *t = bt;
	if(t){
		i++;
		while(t->data!=p->data){
			if(p->data<t->data){
				t = t->rchild;
			}
			if(p->data>x){
				t = t->lchild;
			}
		}
	}
	return i;
}
// 非递归中序遍历
#define MAXSIZE 50
typedef struct BiNode
{
	int data;
	BiNode *lchild;
	BiNode *rchild;
}BiNode,*BiTree;
typedef struct Stack
{
	int data[MAXSIZE];
	int top;
}Stack;
void InitStack(Stack s){
	s.top = -1;
}
void Push(Stack &s,int k){
	if(s.top == MAXSIZE-1){
		exit(0);
	}
	s.data[++s.top] = x;
}
void Pop(Stack &s,int k){
	if(s.top == -1){
		exit(0);
	}
	k = s.data[s.top--];
}
bool isEmptyStack(Stack s){
	if(s.top == -1){
		return true;
	}else{
		return false;
	}
}
void Visit(BiTree *bt){
	printf("当前的结点为%s\n",bt);
}
// 获取栈顶元素，但不删除
void BiTree* getTop(BiTree *,int p){
}
void inorderNonRecusion(BiTree bt){
	BiNode *p = NULL;
	BiNode *stack[MAXSIZE] = (BiNode*)malloc(sizeof(BiNode)*MAXSIZE);
	p = bt;
	while(p||!isEmpty(stack)){
		while(p){
			Push(stack,p);
			p = p->lchild;
		}
		// 要注意这里不用再 push（p->rchild）了
		if(!isEmpty(Stack)){
			Pop(stack,p);
			printf("当前中序遍历所经过的节点为%s\n", p->data);
			p = p->rchild;
		}
	}
}
// 判断一棵树是否是平衡二叉树
// 平衡二叉树：左右子树高度差不超过一的二叉排序树
// 完全二叉树：每个节点都与同满二叉树编号顺序一致
//tips: 只有左右子树均平衡才能保证二叉树为平衡二叉树。
// 故：不能忘记要设置对应的 tag 分别判断对应的左右子树是否平衡
typedef struct BiNode
{
	int data;
	BiNode *lchild,*rchild;
}BiNode,*BiTree;
// 为什么这里要用 & amp;h 因为传参过来时会将 h 的值改变。
bool judgeBalanceTree(BiTree bt,int &h,int &balance){
	
	int hl=0;// 左子树高度
	int hr=0;// 右子树高度
	int bl = 0;// 左子树平衡
	int br = 0;// 右子树平衡
	if(bt=NULL){
		h = 0;
		balance = 1;
	}
	// 仅有根节点
	if(bt->lchild == NULL&&bt->rchild == NULL){
		h = 1;
		balance = 1;
	}
	h = (hl>hr?hl:hr)+1;//+1 表示加上根节点
	judgeBalanceTree(bt->lchild,h,balance);
	judgeBalanceTree(bt->rchild,h,balance);
	if(abs(hl-hr)<2){
		balance = br&&bl;
	}else{
		balance = 0;
	}
}
// 循环队列实现层次遍历
#define MAXSIZE 50;
typedef struct BiTree
{
	int data;
	BiTree *lchild;
	BiTree *rchild;
}BiTree;
typedef struct
{
	int data[MAXSIZE];
	int front;
	int rear;
}SqQueue;
bool isEmpty(SqQueue q){
	if(q.rear == q.front){
		return true;
	}else{
		return false;
	}
}
// 入队
bool Enque(SqQueue &q,int x){
	if((q.rear+1)%MAXSIZE == q.front){
		// 队满报错
		return false;
	}
	q.data[q.rear] = x;
	q.rear = (q.rear+1)%MAXSIZE;
	return true;
}
// 出队
bool Deque(SqQueue &q,int x){
	if(q.rear == q.front){
		// 队空报错
		return false; 
	}
	x = q.data[q.front];
	q.front = (q.front+1)%MAXSIZE;
	return true;
}
void InitQue(SqQueue &q){
		q.rear = q.front = 0;// 初始化队首队尾指针
}
void Visit(BiTree *bt){
	printf("%s\n",bt );
}
void levelOrder(BiTree *bt){
	BiTree *Queue = (BiTree*)malloc(sizeof(BiTree)*MAXSIZE);
	InitQue(Queue);
	BiTree *p;
	Enque(SqQueue,bt);
	while(!isEmpty(Queue)){
		// 出队并访问根节点
		Deque(Queue,p);
		Visit(p);
		// 根左右进队列
		if(p->lchild){
			Enque(Queue,p->lchild);
		}
		if(p->rchild){
			Enque(Queue,p->rchild);
		}
	}
}
// 查找 p，q 的最近公共节点
#define MAXSIZE 50;
typedef struct BiTree
{
	int data;
	BiTree *lchild;
	BiTree *rchild;
}BiTree;
typedef struct Stack
{
	int data[MAXSIZE];
	int top;
}Stack;
void InitStack(Stack s){
	s.top = -1;
}
void Push(Stack &s,int k){
	if(s.top == MAXSIZE-1){
		exit(0);
	}
	s.data[++s.top] = x;
}
void Pop(Stack &s,int k){
	if(s.top == -1){
		exit(0);
	}
	k = s.data[s.top--];
}
bool isEmptyStack(Stack s){
	if(s.top == -1){
		return true;
	}else{
		return false;
	}
}
void Visit(BiTree *bt){
	printf("当前的结点为%s\n",bt);
}
// 获取栈顶元素，但不删除
void BiTree* getTop(BiTree *,int p){
}
// 查找元素 x 的所有祖先，并返回包含这些祖先的栈。
// 实际上就是 assist 辅助节点型非递归后序遍历
Stack *searchAncestor(BiTree *bt,BiTree *x){
	BiTree *Stack = (BiTree*)malloc(sizeof(BiTree)*MAXSIZE);
	InitStack(Stack);
	BiTree *p;
	BiTree *r = NULL
	Push(Stack,bt);
	while(!isEmptyStack(Stack)){
		while(p!=NULL&&p!=x){
			Push(p->lchild);
		}
		getTop(Stack,p);
		if(p == x){
			Pop(Stack,p);
			return Stack;
			
		}
		if(p->rchild!=NULL&&p->rchild!=r){
			Push(Stack,p->rchild);
		}
		Pop(Stack,p);
		r = p;
		p = NULL;
	}
}
// 返回 p 和 q 的最近祖先
BiTree *findNearAncestor(BiTree *bt,BiTree *p,BiTree *q,BiTree *r){
	BiTree *Stack1 = (BiTree*)malloc(sizeof(BiTree)*MAXSIZE);
	BiTree *Stack2 = (BiTree*)malloc(sizeof(BiTree)*MAXSIZE);
	InitStack(Stack1);
	InitStack(Stack2);
	BiTree *temp = NULL;
	stack1 = searchAncestor(bt,p);// 返回 p 的所有祖先栈
	stack2 = searchAncestor(bt,q);// 返回 q 的所有祖先栈
	while(！isEmptyStack(stack1)){
		Pop(stack1,temp)
		for(int i=1;i<MAXSIZE;i++){
			if(temp == stack2.data[i]){
				r = temp;
				break;
			}
		}
	}
	return r;
}
// 采用辅助指针实现 postOrder
// 注：这里的辅助指针指明的是最近访问过的节点。
// 因为：返回的时候需要判别好当前所属的分支是左子树还是右子树
// 这样才能进一步判定是否能将当前节点入栈
#define MAXSIZE 50;
typedef struct BiTree
{
	int data;
	BiTree *lchild;
	BiTree *rchild;
}BiTree;
typedef struct Stack
{
	int data[MAXSIZE];
	int top;
}Stack;
void InitStack(Stack s){
	s.top = -1;
}
void Push(Stack &s,int k){
	if(s.top == MAXSIZE-1){
		exit(0);
	}
	s.data[++s.top] = x;
}
void Pop(Stack &s,int k){
	if(s.top == -1){
		exit(0);
	}
	k = s.data[s.top--];
}
bool isEmptyStack(Stack s){
	if(s.top == -1){
		return true;
	}else{
		return false;
	}
}
void Visit(BiTree *bt){
	printf("当前的结点为%s\n",bt);
}
// 获取栈顶元素，但不删除
void BiTree* getTop(BiTree *,int p){
}
void postOrder(BiTree *bt){
	BiTree *Stack = (BiTree*)malloc(sizeof(BiTree)*MAXSIZE);
	InitStack(Stack);
	BiTree *p;
	BiTree *r = NULL
	Push(Stack,bt);
	while(!isEmptyStack(Stack)){
		while(p!=NULL){
			Push(p->lchild);
		}
		getTop(Stack,p);
		if(p->rchild!=NULL&&p->rchild!=r){
			Push(p->rchild)
		}else{
			Pop(Stack,p);
			Visit(p);
			r = p;
			p = NULL;// 每次都将 p 置空的原因在于 -- 当访问完左右节点时当前二叉分支便不再需要访问了。	
		}
		
	}
}
// 采用双栈实现 postOrder
#define MAXSIZE 50;
typedef struct BiTree
{
	int data;
	BiTree *lchild;
	BiTree *rchild;
}BiTree;
typedef struct Stack
{
	int data[MAXSIZE];
	int top;
}Stack;
void InitStack(Stack s){
	s.top = -1;
}
void Push(Stack &s,int k){
	if(s.top == MAXSIZE-1){
		exit(0);
	}
	s.data[++s.top] = x;
}
void Pop(Stack &s,int k){
	if(s.top == -1){
		exit(0);
	}
	k = s.data[s.top--];
}
bool isEmptyStack(Stack s){
	if(s.top == -1){
		return true;
	}else{
		return false;
	}
}
void Visit(BiTree *bt){
	printf("当前的结点为%s\n",bt);
}
// 获取栈顶元素，但不删除
void BiTree* getTop(BiTree *,int p){
}
void postOrder(BiTree *bt){
	BiTree *Stack1 = (BiTree*)malloc(sizeof(BiTree)*MAXSIZE);
	BiTree *Stack2 = (BiTree*)malloc(sizeof(BiTree)*MAXSIZE);
	InitStack(Stack1);
	InitStack(Stack2);
	BiTree *p;
	Push(Stack1,bt);
	while(!isEmptyStack(Stack1)){
		Pop(Stack1,p)
		Push(Stack2,p);
		if(p->lchild){
			Push(Stack1,p);
		}
		if(p->rchild){
			Push(Stack1,p);
		}
	}
	while(!isEmptyStack(Stack2)){
		Pop(Stack2,p);
		Visit(p);
	}
}
// 通过前序遍历和中序遍历来创建一颗二叉树
#define MAXSIZE 50;
typedef struct BiNode
{
	int data;
	BiNode *lchild,*rchild;
}BiNode,*BiTree;
BiTree usePreAndIn(int pre[],int in[],int l1,int l2,int h1,int h2){
	//pre [] 和 in [] 分别表示前序遍历数组和后续遍历数组
	////l1 和 l2 分别表示 preOrder 的起点和 inOrder 的起点
	/// 同理 h1 和 h2 表示 preOrder 和 Inorder 的终点
	int l1 = l2 = 1;
	int h1 = h2 = MAXSIZE;
	BiNode * root = (BiNode *)malloc(sizeof(BiNode));
	root->lchild = root->rchild = NULL;
	root->data = pre[i];
	if(root!=NULL){
		for(i = l2;root->data!=in[i];i++);
		int lchildLength = i-l2;
		int rchildLength = h2-i
		if(lchildLength){
			// @param l1+1 l1 表示的是根节点，所以根据 "根 左 右" 左子树起始编号为 l1+1
		// @param l1+lchildLength 左子树的末尾编号
		// @param l2 inorder 中 左子树的起始编号
		// @param l2+lchildLength-1   为什么要 - 1？==>
		// 因为 l2+lchildLength 根据 "左 根 右" 排序其中是包含了一个根节点的，因而要减去
		// 
		// 这个序列中的参数均表示左子树起点和终点
		// 不同的是，他们各自表示的分别是 preOrder 中的左子树于 inorder 中的左子树
		root->lchild = usePreAndIn(pre,in,l1+1,l1+lchildLength,l2,l2+lchildLength-1);
		}else{
			r->lchild = NULL;
		}
		if(rchildLength){
		// @param h1-rchildLength+1 preOrder 中右子树的起点，为什么要 + 1？==>
		// 因为当 h1-rchildLenght 时当前节点的指向为根节点故需要加 + 1 才能使得当前节点为 preOrder 的第一个右子树节点
		// 同理后者也一样 
		root->rchild = usePreAndIn(pre,in,h1-rchildLength+1,h1,h2-rchildLength+1,h2);
		}else{
			r->rchild = NULL;
		}
	}
	return root;
}
// 计算一颗二叉树的所有双分支节点
typedef struct BiNode{
	BiNode *lchild;
	BiNode *rchild;
	int data
}BiNode,*BiTree;
void countDoubleNode(BiTree bt){
	BiNode *p = bt;
	if(b==NULL){
		return 0;
	}
	else(bt->rchild&&bt->rchild){
		return countDoubleNode(bt->lchild)+countDoubleNode(bt->rchild)+1;
	}else{
		return countDoubleNode(bt->lchild)+countDoubleNode(bt->rchild)+1;
	}
}
// 求树的高度
void getHeight(BiTree bt){
	int height = 0;
	if(bt == NULL){
		return 0;
	}
	int tempHeight 1;
	tempHeight++;
	if(p->lchild){
		tempHeight = getHeight(p->lchild);
	}
	else(p->rchild){
		tempHeight = getHeight(p->rchild);
	}
	if(tempHeight>height){
		height = tempHeight;
	}
	
}
// 将树中的所有左右节点进行交换
void swap(BiTree *bt){
	if(bt){
		swap(b->lchild);
		swap(b->rchild);
		int temp = bt->lchild;
		b->lchild = b->rchild;
		b->rchild = temp;
	}
}
// 非递归过于复杂
// void exchangeLRNode(BiTree *bt){
// 	BiNode *p = bt;
// 	//up-to-down
// 	Initstack(s);
// 	Push(s,p);
// 	while(!isEmpty(s)){
// 		Pop(s,p);
// 		BiNode *temp = p->lchild;
// 		p->lchild = p->rchild;
// 		p->rchild = temp;
// 		if(p->rchild){
// 			Push(s,p->rchild);
// 		}
// 		if(p->lchild){
// 			Push(s,p->lchild);
//		}
// 	}
// }
// 判断两颗二叉树是否相似
// 相似：二者都为空树或只有一个节点
// 二者的左右子树均相似
//
bool judgeSimilar(BiTree t1,BiTree t2){
	int flagL = flagR = false;
	if(t1 == t2 == NULL){
		return true;
	}else if(t1 == NULL||t2 == NULL){
		return false;
	}else{
		if(t1->lchild&&t2->lchild){
			flagL = judgeSimilar(t1->lchild,t2->rchild);
		}
		if(t1->rchild&&t2->rchild){
			flagr = judgeSimilar(t1->rchild,t2->rchild);
		}
	}
	return flagr&&flagL;
}
// 计算二叉树的带权路径长度
// 要点：递归计算树高，然后动态计算 wpl
int deep = 1;
void wpl(BiTree bt,int deep){
	int sum = 0;
	BiNode *root = bt;
	if(root->lchild==root->rchild==NULL){
		sum = sum+deep*root->weight;
	}
	if(root->lchild!=NULL){
		sum = wpl(root->lchild,deep+1);
	}
	if(root->rchild!=NULL){
		sum = wpl(root->rchild,deep+1);
	}
	return sum;
}
//1. 给定一个数组 A []，依次取 A [i], 判断根据插入排序算法构建一个二叉排序树
//2. 实现该树的中序遍历递归算法
BiTree creatBiTree(BiTree *bt,int Arr[n],int i){
	
	for(int i = 0;i<n;i++){
		BiNode *root = (BiNode)*malloc(sizeof(BiNode));	
		root->data = Arr[i];
		root->lchild = root->rchild = NULL;
		bt = BiInsert(root,s);
	}
}
// 树的插入排序算法
// 
BiTree BInsert(BiTree bt,BiTree s){
	BiNode *p,*q;
	p = bt;
	q = NULL;
	if(bt == NULL){
		return s;
	}
	//p 是根节点，q 是遍历节点
	while(p){
		q = p;
		if(s->data == p->data){
			free(s);
			return bt;
		}
		if(s->data < p->data){
			p = p->lchild;
		}else{
			p = p->rchild;
		}
		if(s->data<q->data){
			q->lchild = s;
		}else{
			q->rchild = s;
		}
	}
}
void inorder(BiTree bt){
	if(bt){
		inorder(bt->lchild);
		visit(bt);
		inorder(bt->rchild);
	}
}
// 将树中的所有左右节点进行交换
void swap(BiTree *bt){
	if(bt){
		swap(b->lchild);
		swap(b->rchild);
		int temp = bt->lchild;
		b->lchild = b->rchild;
		b->rchild = temp;
	}
}
// 非递归过于复杂
// void exchangeLRNode(BiTree *bt){
// 	BiNode *p = bt;
// 	//up-to-down
// 	Initstack(s);
// 	Push(s,p);
// 	while(!isEmpty(s)){
// 		Pop(s,p);
// 		BiNode *temp = p->lchild;
// 		p->lchild = p->rchild;
// 		p->rchild = temp;
// 		if(p->rchild){
// 			Push(s,p->rchild);
// 		}
// 		if(p->lchild){
// 			Push(s,p->lchild);
//		}
// 	}
// }
// 计算哈夫曼树的 wpl
typedef struct HNode{
	struct HNode *lchild,*rchild,*parent;
	int weight;
}HNode,*Hlink;
int Hwpl(Hlink *ht){
	Hlink p;
	int sum = 0;
	if(ht==NULL){
		return sum;
	}
	ClearStack(s);
	p = bt;
	// 中序遍历求 wpl
	while(p||!isEmpty(s)){
		while(p->lchild){
			Push(s,p);
			p->lchild;
		}// 把所有孩子都放进 stack s
		if(p->rchild){
			sum = sum+p.weight;
		}
		p = p->rchild;
	}
	return sum
}
// 层次遍历求 wpl
void wpl(BiTree bt){
	InitQueue(q);
	BiNode *p;
	int sum = 0;
	Enque(q,bt);
	while(!isEmpty(q)){
		Deque(q,p);
		if(p->lchild){
			sum = sum+p.weight;
		}
		if(p->rchild){
			sum = sum+p.weight;
		}
	}
}
// 检查二叉树是否对称
bool isSymmetry(BiTree *bt){
	bool flag = false;
	if(bt->lchild||bt->rchild){
		if(bt->lchild == bt->rchild){
			flag = true;
		}
		Lflag = isSymmetry(bt->lchild);
		Rflag = isSymmetry(bt->Rchild);
	}
	return Lflag&&Rflag;
}
// 所有左孩子之和
void sum(BiTree *bt){
	struct BiNode *p = bt;
	int sum = 0;
	while(p||!isEmpty(s)){
		if(p){
			push(stack,p->lchild);
		}
		else{
			pop(stack,p);
			if(p->lchild&&p->lchild==NULL&&p->lchild->rchild==NULL){
				sum = sum+p->lchild->data;
			}
				p = p->rchild;
			}
	}
	return sum;
}
// 在二叉排序数中查找第 k 个小的元素，并返回第以他为根节点的节点数 count 的大小
BiNode findLowerK(BiNode *bt,int k){
	BiNode *p = bt;
	if(k<1||k>p.count){
		return NULL;
	}
	if(p->lchild==NULL){
		if(k==1){
			return p;
		}else{
			return findLowerK(p->rchild,k-1);
		}
	}else{
		if(p->lchild.count>k-1){
			return findLowerK(p->lchild,k)
		}
		if(p->lchild.count==k-1){
			return p;
		}
		if(t->lchild.count<k-1){
			return findLowerK(p->rchild,k-(p->lchild.count+1));
		}
	}
}
 更新于   阅读次数  次
请我喝[茶]~(￣▽￣)~*
神烦大眼怪 微信支付
微信支付
神烦大眼怪 支付宝
支付宝
神烦大眼怪 贝宝
贝宝