二叉树相关算法C语言代码

谁借莪１个温暖的怀抱￠ 2022-04-17 03:58 202阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    typedef char datatype;
    typedef struct Node {
    	datatype data;
    	struct Node *LeftChild;
    	struct Node *RightChild;
    }BiTreeNode, *BiTree;
    typedef struct Seqstack {
    	BiTree lastptr[1000];
    	int TopIndex;
    }Stack;
    typedef struct ArrDeque {
    	BiTree Rootsave[1000];
    	int front, rear;
    }Deque;
    int a = 0, b = 0, c = 0;//a叶子 b度1 c度2 
    typedef struct chararray {
    	char Arr[50];
    	int Tail;
    }CharArray;
    void InitialCharArray(CharArray **base)
    {
    	*base = (CharArray*)malloc(sizeof(CharArray));
    	(*base)->Tail = -1;
    	return;
    }
    void InitialDeque(Deque **base)
    {
    	*base = (Deque*)malloc(sizeof(Deque));
    	(*base)->front = 0;
    	(*base)->rear = -1;
    	return;
    }
    void SwapDeque(Deque **a,Deque **b)
    {
    	Deque *temp;
    	temp = *a;
    	*a = *b;
    	*b = temp;
    	return;
    }
    void Deque_PushBack(Deque *base,BiTree e)
    {
    	base->rear++;
    	base->Rootsave[base->rear] = e;
    	return;
    }
    void Deque_PopFront(Deque *base,BiTree *root)
    {
    	*root = base->Rootsave[base->front];
    	base->front++;
    	return;
    }
    int DequeIsEmpty(Deque *base)
    {
    	if (base->front > base->rear)return 1;
    	else return 0;
    }
    int CharArrIsEmpty(CharArray *base)
    {
    	if (base->Tail == -1)return 1;
    	else return 0;
    }
    void AddToCharArray(CharArray *base,char ele)
    {
    	base->Tail++;
    	base->Arr[base->Tail] = ele;
    	return;
    }
    void CreateBiTree(BiTree *root) {//树的建立
    	char tempch;
    	tempch = getchar();
    	if (tempch == '#')
    	{
    		*root = NULL;
    	}
    	else {
    		*root = (BiTree)malloc(sizeof(BiTreeNode));
    		(*root)->data = tempch;
    		CreateBiTree(&(*root)->LeftChild);
    		CreateBiTree(&(*root)->RightChild);
    	}
    	return;
    }
    void PreOrderCounts(BiTree root)//递归先序遍历统计不同度节点个数
    {
    	if ((root->LeftChild != NULL) && (root->RightChild != NULL))
    	{
    		c++;
    		PreOrderCounts(root->LeftChild);
    		PreOrderCounts(root->RightChild);
    	}
    	else if ((root->LeftChild != NULL) || (root->RightChild != NULL))
    	{
    		b++;
    		PreOrderCounts(root->LeftChild);
    		PreOrderCounts(root->RightChild);
    	}
    	else {
    		a++;
    		return;
    	}
    }
    void PreOrder(BiTree root)
    {
    	if (root)
    	{
    		printf("%c",root->data);
    		PreOrder(root->LeftChild);
    		PreOrder(root->RightChild);
    	}
    	return;
    }
    void PreOrderWithDataAndLevel(BiTree root,int level)
    {
    	if (root)
    	{
    		printf("(%c,%d)", root->data, level);
    		level++;
    		PreOrderWithDataAndLevel(root->LeftChild,level);
    		PreOrderWithDataAndLevel(root->RightChild,level);
    	}
    	return;
    }
    void InOrder(BiTree root)//递归中序遍历
    {
    	if (root)
    	{
    
    		InOrder(root->LeftChild);
    		printf("%c", root->data);
    		InOrder(root->RightChild);
    	}
    	else return;
    }
    void PostOrder(BiTree root)//递归后序遍历
    {
    	if (root)
    	{
    
    		PostOrder(root->LeftChild);
    		PostOrder(root->RightChild);
    		printf("%c", root->data);
    	}
    	else return;
    }
    void InitialStack(Stack **S)//栈的初始化
    {
    	*S = (Stack*)malloc(sizeof(Stack));
    	(*S)->TopIndex = -1;
    	(*S)->lastptr[0] = 0;
    	return;
    }
    void Push(Stack *S, BiTree p)//压栈
    {
    	S->TopIndex++;
    	S->lastptr[S->TopIndex] = p;
    	
    	return;
    }
    void Pop(Stack *S, BiTree *p)//出栈
    {
    	*p = S->lastptr[S->TopIndex];
    	S->lastptr[S->TopIndex] = NULL;
    	S->TopIndex--;
    	return;
    }
    int IsEmpty(Stack *S)//判栈空
    {
    	if (S->TopIndex == -1)return 1;
    	else return 0;
    }
    void CreateBiTreeByPreAndMid(BiTree *root,CharArray *Pre,CharArray *In)
    {
    	if (CharArrIsEmpty(Pre) || CharArrIsEmpty(In))
    	{
    		*root = NULL;
    		return;
    	}
    	else
    	{
    		int RootIndex = 0;
    		*root = (BiTree)malloc(sizeof(BiTreeNode));
    		(*root)->data = Pre->Arr[0];
    		//printf("%c",(*root)->data);
    		CharArray *pre_l, *pre_r;
    		CharArray *In_l, *In_r;
    		InitialCharArray(&pre_l);
    		InitialCharArray(&pre_r);
    		InitialCharArray(&In_l);
    		InitialCharArray(&In_r);
    		for (int i = 0; i <= In->Tail; i++)
    		{
    			if (In->Arr[i] == Pre->Arr[0])
    			{
    				RootIndex = i;
    				break;
    			}
    		}
    		for (int i = 0; i < RootIndex; i++)
    		{
    			AddToCharArray(pre_l, Pre->Arr[i+1]);
    			
    			AddToCharArray(In_l, In->Arr[i]);
    		}
    		for (int i = RootIndex + 1; i <= In->Tail; i++)
    		{
    			AddToCharArray(pre_r, Pre->Arr[i]);
    			AddToCharArray(In_r, In->Arr[i]);
    		}
    		CreateBiTreeByPreAndMid(&(*root)->LeftChild, pre_l, In_l);
    		CreateBiTreeByPreAndMid(&(*root)->RightChild, pre_r, In_r);
    	}
    	return;
    }
    void CreateBiTreeByPostAndIn(BiTree *root,CharArray *Post,CharArray *In)
    {
    	if (CharArrIsEmpty(Post) || CharArrIsEmpty(In))
    	{
    		*root = NULL;
    		return;
    	}
    	else
    	{
    		int RootIndex = 0;
    		*root = (BiTree)malloc(sizeof(BiTreeNode));
    		(*root)->data = Post->Arr[Post->Tail];
    		//printf("%c",(*root)->data);
    		CharArray *post_l, *post_r;
    		CharArray *in_l, *in_r;
    		InitialCharArray(&post_l);
    		InitialCharArray(&post_r);
    		InitialCharArray(&in_l);
    		InitialCharArray(&in_r);
    		for (int i = 0; i <= In->Tail; i++)
    		{
    			if (In->Arr[i] == Post->Arr[Post->Tail])
    			{
    				RootIndex = i;
    				break;
    			}
    		}
    
    		for (int i = 0; i < RootIndex; i++)
    		{
    			AddToCharArray(in_l, In->Arr[i]);
    			AddToCharArray(post_l, Post->Arr[i]);
    			
    		}
    		for (int i = RootIndex + 1; i <= In->Tail; i++)
    		{
    			AddToCharArray(in_r, In->Arr[i]);
    			AddToCharArray(post_r,Post->Arr[i-1]);
    		}
    		CreateBiTreeByPostAndIn(&(*root)->LeftChild, post_l, in_l);
    		CreateBiTreeByPostAndIn(&(*root)->RightChild, post_r, in_r);
    	}
    	return;
    }
    void PostOrderNonRecursive(BiTree root)//非递归的后序遍历
    {
    	Stack *S;
    	InitialStack(&S);
    	BiTree q = NULL;
    	if (root)
    	{
    		do
    		{
    			if (root)
    			{
    				Push(S, root);
    				root = root->LeftChild;
    			}
    			else
    			{
    				root = S->lastptr[S->TopIndex];
    				if (root->RightChild&&root->RightChild != q)
    				{
    					root = root->RightChild;
    					
    				}
    				else
    				{
    					Pop(S, &root);
    					printf("%c", root->data);
    					q = root;
    					root = NULL;//key
    				}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
    			}
    		} while (!IsEmpty(S));
    	}
    	else return;
    }
    void InOrderNonRecursive(BiTree root)//非递归的中序遍历
    {
    	Stack *S;
    	InitialStack(&S);
    	if (root)
    	{
    		
    		do
    		{
    			if (root)
    			{
    				Push(S, root);
    				root = root->LeftChild;
    			}
    			else
    			{
    				Pop(S, &root);
    				printf("%c",root->data);
    				root = root->RightChild;
    			}
    		} while (!IsEmpty(S));
    	}
    	else return;
    }
    void PreOrderNonRecursive(BiTree root)//非递归的先序遍历
    {
    	Stack *S;
    	InitialStack(&S);
    	if (root)
    	{
    		Push(S, root);
    		while (!IsEmpty(S))
    		{
    			Pop(S, &root);
    			printf("%c", root->data);
    			if (root->RightChild)
    			{
    				Push(S, root->RightChild);
    			}
    			if (root->LeftChild)
    			{
    				Push(S, root->LeftChild);
    			}
    		}
    	}
    	else return;
    }
    void FindWayToLeave(BiTree root,datatype path[],int pathlen)//非递归的先序遍历
    {
    	int i;
    	if (root != NULL)
    	{
    		if (root->LeftChild == NULL && root->RightChild == NULL)
    		{
    			printf("%c:",root->data);
    			CharArray *way;
    			InitialCharArray(&way);
    			//printf("%d\n",way->Tail);
    			for (i = pathlen - 1; i >= 0; i--)
    			{
    				AddToCharArray(way, path[i]);
    				//printf("%d\n", way->Tail);
    			}
    			for (i = way->Tail; i >= 0; i--)
    			{
    				printf("%c",way->Arr[i]);
    			}
    			printf("\n");
    		}
    		else
    		{
    			path[pathlen] = root->data;
    			pathlen++;
    			FindWayToLeave(root->LeftChild, path, pathlen);
    			FindWayToLeave(root->RightChild, path, pathlen);
    			pathlen--;
    		}
    	}
    }
    Stack* FindWayToSpecificNode(BiTree root,datatype Aim) {//在非递归的后序遍历中如果栈顶结点是目标结点，那么栈中所存的路径就是最终结果的逆路径
    	Stack* result;
    	InitialStack(&result);
    	BiTree flag = NULL;
    	if (root)
    	{
    		Push(result,root);
    	}
    	do{
    		
    		if (root)
    		{
    			
    			Push(result, root);
    			if (root->data == Aim)return result;
    			root = root->LeftChild;
    		}
    		else {
    			root = result->lastptr[result->TopIndex];//赋为栈顶值但不出栈，为了做判断
    			if (root->data == Aim)return result;
    			if (root->RightChild != NULL && root->RightChild != flag)
    			{
    				root = root->RightChild;
    			}
    			else
    			{
    				Pop(result, &root);
    				flag = root;
    				root = NULL;
    			}
    		}
    	} while (!IsEmpty(result));
    	return result;
    }
    char getCommonAncestor(Stack *a,Stack* b)
    {
    	Stack *A, *B;
    	BiTree buffer,buffer2;
    	char result,rootch;
    	InitialStack(&A);
    	InitialStack(&B);
    	printf("%d and %d\n", a->TopIndex + 1, b->TopIndex + 1);
    	while (!IsEmpty(a)) { Pop(a, &buffer); Push(A, buffer); }
    	while (!IsEmpty(b)) { Pop(b, &buffer); Push(B, buffer); }
    	
    	//rootch = A->lastptr[A->TopIndex]->data;
    	while (!IsEmpty(A) && !IsEmpty(B))
    	{
    		Pop(A, &buffer);
    		Pop(B, &buffer2);
    		if (buffer->data != buffer2->data)return result;
    		else result = buffer->data;
    	}
    	return '#';
    }
    //int PrintatLevel(BiTree root,int level)//单层的打印
    //{
    //	if (root == NULL)return 0;
    //	else if (level == 1) { printf("%c", root->data); return 1; }
    //	else
    //	{
    //		int leftResult = PrintatLevel(root->LeftChild, level - 1);
    //		int rightResult = PrintatLevel(root->RightChild, level - 1);
    //		if (leftResult == 0 && rightResult == 0)return 0;
    //		else return 1;
    //	}
    //}
    int PrintatLevel(BiTree root,int move,const int level)//单层的打印,带括号
    {
    	if (root == NULL)return 0;
    	else if (move == 1) { printf("(%c,%d)", root->data,level); return 1; }
    	else
    	{
    		int leftResult = PrintatLevel(root->LeftChild, move - 1,level);
    		int rightResult = PrintatLevel(root->RightChild, move - 1,level);
    		if (leftResult == 0 && rightResult == 0)return 0;
    		else return 1;
    	}
    }
    void PrintByLevel(BiTree root)
    {
    	int i;
    	for (i = 1;; i++)//由于不知道树的深度，从第一层开始打印
    	{
    		if (PrintatLevel(root, i,i) == 0)break;
    		//printf("\n");
    	}
    	return;
    }
    void ExchangeBiTreeRootChild(BiTree *root)
    {
    	if ((*root) == NULL)return;
    	BiTree temp;
    	temp = (*root)->LeftChild;
    	(*root)->LeftChild = (*root)->RightChild;
    	(*root)->RightChild = temp;
    	ExchangeBiTreeRootChild(&(*root)->LeftChild);
    	ExchangeBiTreeRootChild(&(*root)->RightChild);
    	return;
    }
    void PrintByLevelWithTwoDeque(BiTree root)
    {
    	Deque *first, *second;
    	InitialDeque(&first);
    	InitialDeque(&second);
    	BiTree temp;
    	Deque_PushBack(first, root);
    	while (!DequeIsEmpty(first))
    	{
    		while (!DequeIsEmpty(first))
    		{
    			Deque_PopFront(first, &temp);
    			printf("%c",temp->data);
    			if (temp->LeftChild)Deque_PushBack(second,temp->LeftChild);
    			if (temp->RightChild)Deque_PushBack(second,temp->RightChild);
    		}
    		printf("\n");
    		SwapDeque(&first, &second);
    	}
    	return;
    }
    int CountWhichLevelLeafs(BiTree root,const int WhichLevel)
    {
    	int result = 0;
    	int Curlevel = 1;
    	Deque *first, *second;
    	InitialDeque(&first);
    	InitialDeque(&second);
    	BiTree temp;
    	Deque_PushBack(first, root);
    	while (!DequeIsEmpty(first))
    	{
    		while (!DequeIsEmpty(first))
    		{
    			Deque_PopFront(first, &temp);
    			
    			if (temp->LeftChild)Deque_PushBack(second, temp->LeftChild);
    			if (temp->RightChild)Deque_PushBack(second, temp->RightChild);
    			if (temp->LeftChild == NULL && temp->RightChild == NULL&&Curlevel==WhichLevel)result++;
    		}
    		Curlevel++;
    		SwapDeque(&first, &second);
    	}
    	return result;
    }
    
    int main()
    {
    	BiTree root;
    	CreateBiTree(&root);//先序扩展序列创建二叉树
    	char a, b;
    	getchar();
    	scanf_s("%c", &a,1);
    	scanf_s(" %c", &b,2);
    	printf("a->%c  b->%c\n", a, b);
    	Stack *Sa, *Sb;
    	Sa = FindWayToSpecificNode(root, a);
    	Sb = FindWayToSpecificNode(root, b);
    	printf("%c\n", getCommonAncestor(Sa, Sb));
    	//root = (BiTree)malloc(sizeof(BiTreeNode));
    	//root->data = 'a';
    	/*CharArray Post, In;
    	scanf_s("%s", &In.Arr, 50);
    	scanf_s("%s", &Post.Arr,50);
    	
    	Post.Tail = (int)strlen(Post.Arr)-1;
    	In.Tail = (int)strlen(In.Arr)-1;
    	CreateBiTreeByPostAndIn(&root, &Post, &In);*/
    	//CreateBiTree(&root);
    	/*ExchangeBiTreeRootChild(&root);
    	PreOrder(root);
    	printf("\n");
    	InOrder(root);
    	printf("\n");
    	PostOrder(root);*/
    	
    	//CreateBiTreeByPreAndMid(&root, &Pre, &In);
    	//PostOrder(root);
    	
    	
    	//datatype path[1000];
    	//FindWayToLeave(root, path, 0);
    	//PreOrder(root);
    	//int Whichlevel;
    	//scanf_s("%d",&Whichlevel);
    	//printf("%d\n",CountWhichLevelLeafs(root,Whichlevel));
    	//PrintByLevelWithTwoDeque(root);
    	//PreOrderWithDataAndLevel(root, 1);
    	//PrintByLevel(root);
    	
    	return 0;
    }