链式存储的二叉树

女爷i 2023-02-11 13:29 5阅读 0赞

课本上的东西，放到这里是查阅方便。

#include <stdio.h>
    #include <malloc.h>
    typedef char DataType;
    
    //结点结构体的定义
    typedef struct Node
    {
    	DataType data;
    	struct Node *leftChild;
    	struct Node *rightChild;
     } BiTreeNode;
     //初始化
     void Initiate(BiTreeNode **root)
     {
     	*root = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    	 (*root)->leftChild = NULL; 
    	 (*root)->rightChild = NULL; 
      } 
      //左插入结点
      BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x)
      {
      	BiTreeNode *s, *t;
      	if(curr == NULL) return NULL;
      	t = curr->leftChild;
      	s = (BiTreeNode *)malloc(sizeof(BiTreeNode));
      	s->data = x;
      	s->leftChild = t;
      	s->rightChild = NULL;
    	curr->leftChild = s;
    	return curr->leftChild; 
       } 
       //右插入结点
       BiTreeNode *InsertRightNode(BiTreeNode *curr, DataType x)
      {
      	BiTreeNode *s, *t;
      	if(curr == NULL) return NULL;
      	t = curr->rightChild;
      	s = (BiTreeNode *)malloc(sizeof(BiTreeNode));
      	s->data = x;
      	s->rightChild = t;
      	s->leftChild = NULL;
    	curr->rightChild = s;
    	return curr->rightChild; 
       } 
       //撤销二叉树
    	void Destroy(BiTreeNode **root) 
    	{
    		if((*root)!=NULL&&(*root)->leftChild!=NULL)
    		Destroy(&(*root)->leftChild);
    		if((*root)!=NULL&&(*root)->rightChild!=NULL)
    		Destroy(&(*root)->rightChild);
    		free(*root);
    	}
       //左删除子树 
       BiTreeNode *DeleteLeftTree(BiTreeNode *curr)
       {
       	if(curr==NULL||curr->leftChild==NULL) return NULL;
       	Destroy(&curr->leftChild);
       	curr->leftChild = NULL;
       	return curr;
       }
       //右删除子树 
       BiTreeNode *DeleteRightTree(BiTreeNode *curr)
       {
       	if(curr==NULL||curr->rightChild==NULL) return NULL;
       	Destroy(&curr->rightChild);
       	curr->rightChild = NULL;
       	return curr;
       }
       //前序遍历
       void PreOrder(BiTreeNode *root,void visit(DataType item))
       {
       	if(root!=NULL)
       	{
       		visit(root->data);
       		PreOrder(root->leftChild,visit);
       		PreOrder(root->rightChild,visit);
    	   }
    	} 
    	//中序遍历
    	void InOrder(BiTreeNode *root,void visit(DataType item)) 
    	{
    		if(root!=NULL)
    		{
       		InOrder(root->leftChild,visit);
       		visit(root->data);
       		InOrder(root->rightChild,visit);
    	   }
    	}
       //后序遍历
    	void PostOrder(BiTreeNode *root,void visit(DataType item)) 
    	{
    		if(root!=NULL)
    		{
       		PostOrder(root->leftChild,visit);
       		PostOrder(root->rightChild,visit);
       		visit(root->data);
    	   }
    	}
    	//打印二叉树
    	void PrintBiTree(BiTreeNode *root, int n)
    	{
    		int i;
    		if(root == NULL) return;
    		PrintBiTree(root->rightChild, n+1);
    		for(i=0;i<n-1;i++) printf("    ");
    		if(n>0)
    		{
    			printf("- - -");
    			printf("%c\n",root->data);
    		}
    		PrintBiTree(root->leftChild, n+1);
    	}
    	//查找数据元素
    	BiTreeNode *Search(BiTreeNode *root, DataType x)
    	{
    		BiTreeNode *find = NULL;
    		if(root!=NULL)
    		{
    			if(root->data == x)
    			{
    				find = root;
    			 } else
    			 {
    			 	find = Search(root->leftChild, x);
    			 	if(find == NULL)
    				 {
    				 	find = Search(root->rightChild, x);
    				  } 
    			 }
    		   } 
    		   return find;
    	 }

测试：

#include <stdio.h>
    #include "head.h"
    
    void Visit(DataType item)
    {
    	printf("%c ", item);
    }
    
    int main()
    {
    	BiTreeNode *root, *p, *find;
    	char x = 'E';
    	Initiate(&root);
    	p = InsertLeftNode(root,'A');
    	p = InsertLeftNode(p,'B');
    	p = InsertLeftNode(p,'D');
    	p = InsertRightNode(p,'G');
    	p = InsertRightNode(root->leftChild,'C');
    	InsertLeftNode(p,'E');
    	InsertRightNode(p,'F');
    	PrintBiTree(root, 0);
    	printf("前序遍历："); 
    	PreOrder(root->leftChild, Visit); 
    	printf("\n中序遍历："); 
    	InOrder(root->leftChild, Visit); 
    	printf("\n后序遍历："); 
    	PostOrder(root->leftChild, Visit); 
    	find = Search(root, x);
    	if(find != NULL) printf("\n数据元素%c在二叉树中", x);
    	else  printf("\n数据元素%c不在二叉树中", x);
    	Destroy(&root); 
    	return 0;
     }

示意图如下

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludDg4ODg4OA_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludDg4ODg4OA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200523224751292.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludDg4ODg4OA==,size_16,color_FFFFFF,t_70