数据结构 手写代码练习 | 二叉树 图【未完成】

时间：2024-10-26 12:50:09
10.25 二叉树 1 - 10 ，8 9 10没做
10.26 图 11-13 图的数据结构 BFS DFS 拓扑排序TopSort
  1. 判断树B是否为树A的子结构（若是，节点的值相等以及两者结构相同）请给出手写C/c++代码，并给出算法思想。

找到B和A一样的ROOT，判断节点的值相等以及两者结构相同
判断相等：首先是data相等，然后再判断B&A 的left 和right
算法思路：A和B同时进行DFS，以判断结构是否相同。

//数据结构
typedef struct BTNode{
	int data; 
	struct BTNode *left,*right;
}BTNode;

bool judge(BTNode *A, BTNode *B){
	if(A == NULL && B == NULL){
		return true;
	}
	else if(A->data == B->data){
		return judge(A->left ,B->left) && judge(A->right ,B->right);
	}
	else return false;
}
bool func(BTNode *A, BTNode *B){
	bool b1,b2,b3;
	if(A->data == B->data){
		//DFS函数
		b1 = judge(A , B);
	}
	//在A的左子树中找B的根结点
	if(A->left){
		b2 = func(A->left , B);
	}
	//在A的右子树中找B的根结点
	if(A->right){
		b3 = func(A->right ,B);
	}
	//三者中有一个judge成功，就可以
	return b1||b2||b3;
}
  1. 试编写一个算法，将一棵二叉排序树（BST）分裂成两棵二叉排序树，使得其中一棵树的所有结点的关键字都小于或等于x，另一棵树的所有结点的关键字均大于x。

BST，左子树均小于node，右子树均大于node。
这道题我不太理解得一点，怎么分裂，是将left right直接断开，但是这道题肯定不是单单断开就可以解决的
例如：[6,3,10,2,5,8,1,4,9]这棵BST中，如果x = 8，算法思路如下：
答案有两个树，树A为小于等于x，树B为大于x。对树tree进行DFS，遇到=<x的直接插入到A中，如果>x直接插入到B中，相等于重新建了两棵树，所以需要函数insertInTree(BSTNode* T,int x){将值x的结点插入到T中}，但这样是不是就是太复杂了？

GPT：
我们可以递归地遍历 BST，通过逐步调整子树来分裂成两个 BST。这个过程可以避免重新创建每个结点，只需适当地调整子树的指针。
So：
所以不需要全部递归，因为如果node <= x则它的左子树全都属于A，则只需要判断右子树就好，对右子树进行递归判断；node > x同理。

//数据结构
typedef struct BSTNode{
	int data;
	struct BSTNode *left,*right;
}BSTNode;

//A中全为小于或等于x B中全为大于x
void splitBST(BSTNode* t, int x,BSTNode *&A,BSTNode *&B){
	if(t == NULL){
		A = NULL;B = NULL;return ;
	}
	if(t->data <= x){
		//当前结点属于A，且左子树都属于A
		A = t;
		//递归处理右子树
		splitBST(t->right,x,A->right,B);
	}else{
		//当前结点属于B，且右子树都属于B
		B = t;
		//递归处理左子树，判断是否还有大于x的值
		splitBST(t->left , x ,A,B->left); 
	}
}
  1. 完全二叉树顺序存储在字符型数组tree[n]中，求出下标i,j两结点最近的公共祖先。

对象：完全二叉树 存储：顺序存储 类型：字符型char
目标找到公共祖先===>向上找父亲直至两个父亲一致

//数据结构
typedef struct BTNode{
	int data;
	struct BTNode *left , *right;
}BTNode;

int CommonAncestor(char tree[],int i,int j){
	int p =i , q =j;
	while(p != q){
		if(p>q){
			p/=2;
		}else{
			q/=2;
		}
	}
	return tree[p];	
}
  1. 【王道5.3.3 3】编写后序遍历二叉树的非递归算法

使用两个栈Stack，while两个top，出1进2，再左右进1

//数据结构
typedef struct BTNode{
	int data;
	struct BTNode *left,*right;
}BTNode;

void PostOederUnRecursion(BTNode *bt){
	BTNode *stack1[maxSize];int top1 = -1;
	BTNode *stack2[maxSize];int top2 = -1;
	BTNode *p;
	stack1[++top1] = bt;
	while(top1 != -1 || top2 != -1){
		p = stack1[top1--];
		stack2[++top2] = p;
		if(p->left){
			stack1[++top1] = p->left;
		}
		if(p->right){
			stack1[++top1] = p->right;
		}
	}
	
}
  1. 编写中序遍历二叉树的非递归算法

一个stack，大while里p+top，先while左子树p，然后if读结点转右子树

void InOederUnRecursion(BTNode *bt){
	BTNode *stack[maxSize];int top = -1;
	BTNode *p = bt;
	while(top != -1 || p != NULL){
		//先左子树
		while(p!=NULL){
			stack[++top] = p;
			p = p->left;}
		//到头了，直接对栈进行出栈
		if(top != -1){
			p = stack[top--];
			visit(p);
			p = p->rchild; 
		}
	}	
}
  1. 编写先序遍历二叉树的非递归算法

类似于levelOrder，while中top，直接出+读，进栈先右后左

void PreOederUnRecursion(BTNode *bt){
	BTNode *stack[maxSize];int top = -1;
	BTNode *p = bt;
	stack[++top] = p;
	while(top != -1){
		p = stack[top--];
		visit(p);
		if(p->right) stack[++top] = p->right;
		if(p->left) stack[++top] = p->left;		
	}
	
}
  1. 编写层次遍历二叉树的非递归算法

使用队列，先左后右

void levelOrder(BTNode *bt){
	InitQueue(Q);
	BTNode *p = bt;
	EnQueue(Q,p);
	while(!isEmpty(Q)){
		DeQueue(Q , p);
		visit(p);
		if(p->left){EnQueue(Q,p->left);}
		if(p->right){EnQueue(Q,p->right);}
	}
}

  1. 【王道 4】试给出二叉树的自下而上、从右到左的层次遍历算法。

  2. 【王道 5】假设二叉树采用二叉链表存储结构，试设计一个非递归算法求二叉树的高度。

  3. 【王道 6】二叉树按二叉链表形式存储，试编写一个判别给定二叉树是否是完全二叉树的算法。

  4. 图的DFS算法 递归读取

//数据结构
#define maxSize 100
typedef int VertexType;
typedef struct ArcNode{
	int adjvex;//邻接点的位置
	struct ArcNode *next;//下一个弧
}ArcNode;
typedef struct VNode{
	VertexType data;//顶点
	struct ArcNode *firstarc;
}VNode,AdjList[maxSize];
typedef struct{
	AdjList vertices;
	int vexnum,arcnum;
}ALGraph;

int visit[maxSize];
int Visit(int v);
void DFS(AGraph *G,int v){//是从v开始DFS G
	ArcNode *p;
	visit[v] = 1;
	Visit(v);
	p = G->adjlist[v].firstarc;
	while(p!=NULL){
		if(visit[p->adjvex] == 0){DFS(G,p->adjvex);}
		p = p->next;
	}
}
  1. 图的BFS算法 入队读取 出队排序
typedef struct ArcNode{
	int adjvex;
	struct ArcNode *next;
}ArcNode;

int visit[maxSize];
int Visit(int v);
void BFS(AGraph *G,int v){
	ArcNode *p;int j;
	int que[maxSize];int front = 0;int rear = 0;
	//入队读取
	Visit(v);
	visit[v] = 1;
	que[rear] = v;
	rear = (rear+1)%maxSize;
	while(front != rear){
		//出队排序
		j = que[front];
		front = (front+1)%maxSize;
		p = G->adjlist[j].firstarc;
		while(p != NULL){
			if(visit[p->adjvex] == 0){
				//入队读取
				Visit(p->adjvex);
				visit[p->adjvex];
				que[rear] = p->adjvex;
				rear = (rear + 1 )%maxSize;
			}
			//如果已经被标记了，往下一个走
			p = p->next;
		}
		
	}
	
}
  1. 拓扑排序 AOV网顶点表示活动 边无权值=>有向无环图

将入度为零的顶点一一输出并在图中删除，直至图中无顶点。

#define maxSize 100
typedef int vertexType;
typedef struct ArcNode{//边表
	int adjvex;
	struct ArcNode *next;
}ArcNode;
typedef struct VNode{//顶点表
	vertexType data;
	struct ArcNode *firstarc;
}VNode,AdjList[maxSize];
typedef struct{		//图
	AdjList vertices;
	int vexnum,arcnum;
}ALGraph;

int TopSort(ALGraph G){
	int num = 0;//记录排序的顶点
	ArcNode *p;
	stack<int> st;
	
	//将入度为0的点加入栈 G.vertices[v].count入度的数目
	for(int v = 0; v < G.vexnum ; ++v){
		if(G.vertices[v].count == 0)
			st.push(v);
	}

	while(!st.empty()){
		//出栈排序 -> num++ 
		int w = st.top();
		st.pop();
		++num;
		cout << w <<endl;//visit(w);
		p = G.vertices[w].firstarc;
		while(p){
			//找u的所有邻接结点，并将邻接结点们的入度都-1
			int u = p->adjvex;
			--G.vertices[u].count;
			if(G.vertices[u].count == 0)
				S.push(u);
			p = p->next;
		}
	}
	if(num == G.vexnum)
		return 1;
	else
		return 0;		
}

【补充】访问结构体时，->和.的区别
在这里插入图片描述

相关文章