数据结构——二叉树的链式存储

桃扇骨 2022-06-16 13:14 197阅读 0赞

# 数据结构——二叉树的链式存储 #

注意输入二叉树元素时查看createBitTree方法中录入原则

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #include <string.h>
    #include <iostream>
    using namespace std;
    #define MaxSize 100
    /**二叉树链式存储**/
    
    typedef struct Node
    {
    	char e;
    	struct Node *leftChild;
    	struct Node *RightChild;
    }*BitTree,BitNode;
    /**初始化一棵空树**/
    void InitBitTree(BitTree* T){
    	*T = NULL;
    }
    /**销毁二叉树**/
    void DestroyBitTree(BitTree *T){
    	if(*T){
    		if((*T)->leftChild)
    			DestroyBitTree(&(*T)->leftChild);
    		if((*T)->RightChild)
    			DestroyBitTree(&(*T)->RightChild);
    		free(*T);
    		*T = NULL;
    	}
    }
    /**按照先序遍历顺序创建二叉树**/
    void CreateBitTree(BitTree *T){
    	char e;
    	cout<<"Input:";
    	cin>>e;
    	if(e=='#'){
    		*T = NULL;
    	}else{
    		*T = (BitTree)malloc(sizeof(BitNode));
    		if(!(*T)){
    			exit(-1);
    		}
    		(*T)->e = e;
    		CreateBitTree(&((*T)->leftChild));
    		CreateBitTree(&((*T)->RightChild));
    	}
    }
    /**二叉树的左插入操作**/
    int InsertLeftChild(BitTree p,BitTree c){
    	//将c插入树中，p指向树中的某个结点，c作为节点的左子树，原结点左子树作为c的右子树
    	if(p){
    		c->RightChild = p->leftChild;
    		p->leftChild = c;
    		return 1;
    	}
    	return 0;
    }
    /**二叉树的右插入操作**/
    int InsertRightChild(BitTree p,BitTree c){
    	if(p){
    		c->RightChild = p->RightChild;
    		p->RightChild = c;
    		return 1;
    	}
    	return 0;
    }
    /**返回二叉树结点的指针**/
    BitTree Point(BitTree T,char e){
    	BitTree Q[MaxSize];
    	int front;
    	int rear = 0;
    	BitNode *p;
    	if(T){
    		Q[rear] = T;
    		rear++;
    		while(front!=rear){
    			p = Q[front];
    			front++;
    			if(p->e==e)
    				return p;
    			if(p->leftChild){
    				Q[rear] = p->leftChild;
    				rear++;
    			}
    			if(p->RightChild){
    				Q[rear] = p->RightChild;
    				rear++;
    			}
    		}
    	}
    	return NULL;
    }
    /**返回结点的左孩子元素值**/
    char LeftChild(BitTree T,char e){
    	BitTree p;
    	if(T){
    		p = Point(T,e);
    		if(p&&p->leftChild)
    			return p->leftChild->e;
    	}
    	return NULL;
    }
    /**返回结点的右孩子元素值**/
    char RightChild(BitTree T,char e){
    	BitTree p;
    	if(T){
    		p = Point(T,e);
    		if(p&&p->RightChild)
    			return p->RightChild->e;
    	}
    	return NULL;
    }
    /**二叉树的左删除操作**/
    int DeleteLeftChild(BitTree p){
    	if(p){
    		DestroyBitTree(&p->leftChild);
    		return 1;
    	}
    	return 0;
    }
    /**二叉树的右删除操作**/
    int DeleteRightChild(BitTree p){
    	if(p){
    		DestroyBitTree(&p->RightChild);
    		return 1;
    	}
    	return 0;
    }
    /**二叉树前序遍历**/
    void PreOrderTraverse(BitTree T){
    	if(T){
    		printf("%c\t",T->e);
    		PreOrderTraverse(T->leftChild);
    		PreOrderTraverse(T->RightChild);
    	}
    }
    /**二叉树中序遍历**/
    void InOrderTraverse(BitTree T){
    	if(T){
    		InOrderTraverse(T->leftChild);
    		printf("%c\t",T->e);
    		InOrderTraverse(T->RightChild);
    	}
    }
    /**二叉树后序遍历**/
    void PostOrderTraverse(BitTree T){
    	if(T){
    		PostOrderTraverse(T->leftChild);
    		PostOrderTraverse(T->RightChild);
    		printf("%c\t",T->e);
    	}
    }
    /**二叉树打印**/
    void TreePrint(BitTree T,int level){
    	int i;
    	if(T==NULL)
    		return;
    	TreePrint(T->RightChild,level+1);
    	for(int i = 0;i<level;i++){
    		printf("\t");
    	}
    	printf("%c\n",T->e);
    	TreePrint(T->leftChild,level+1);
    }
    void main(){
    	BitTree T;
    	InitBitTree(&T);
    	CreateBitTree(&T);
    	TreePrint(T,1);
    	system("pause");
    }