二叉树创建释放遍历

痛定思痛。 2022-06-13 14:18 219阅读 0赞

![Center][]![Center 1][]

前序遍历：ABDGHCEIF

中序遍历：GDHBAEICF

后序遍历：GHDBIEFCA

理解遍历：

void in_Order(BiTNode * root)    //先序遍历
    {
        if(root == NULL)
        {
            return ;
        }
        printf("this is node %d\n",root->data);
        in_Order(root->lchild);//遍历左子树
    	printf("node %d finish scanning left.\n",root->data);
        in_Order(root->rchild);//遍历右子树
    	printf("node %d finish scanning right.\n",root->data);
    }
    
    int  main()
    {
    	BiTNode *p1 = (BiTNode *)malloc(sizeof(BiTNode));
    	memset(p1,0,sizeof(BiTNode));
    	p1->data = 1;
            BiTNode *p2 = (BiTNode *)malloc(sizeof(BiTNode));
    	memset(p2,0,sizeof(BiTNode));
    	p2->data = 2;
    	BiTNode *p3 = (BiTNode *)malloc(sizeof(BiTNode));
    	memset(p3,0,sizeof(BiTNode));
    	p3->data = 3;
    	BiTNode *p4 = (BiTNode *)malloc(sizeof(BiTNode));
    	memset(p4,0,sizeof(BiTNode));
    	p4->data = 4;
    
    	p1->lchild = p2;
    	p2->rchild = p3;
    	p1->rchild = p4;
            in_Order(p1);            
        return 0;
    }
    结果输出：
    this is node 1
    this is node 2
    node 2 finish scanning left.
    this is node 3
    node 3 finish scanning left.
    node 3 finish scanning right.
    node 2 finish scanning right.
    node 1 finish scanning left.
    this is node 4
    node 4 finish scanning left.
    node 4 finish scanning right.
    node 1 finish scanning right.
    
    请按任意键继续. . .

**以下使用图上的前6个节点，1-2-3-4-5-6来创建二叉树；**

1、二叉树的创建之关系创建（对象，需要使用memset初始化对象指针）

#include<stdio.h>
    #include <stdlib.h>
    #include <string.h>
    typedef struct BiTNode 
    {
    	int data;
    	struct BiTNode *lchild;
    	struct BiTNode *rchild;
    }BiTNode, *BiTree;
    
    //推导
    //struct BiTNode
    //{
    //  int data;
    //  struct BitNode *lchild;
    //  struct BiTNode *rchild;
    //};
    //typedef struct BiTNode  BiTNode;
    //typedef struct BiTNode* BiTree;
    
    
    int main()
    {
    	//create node
    	BiTNode t1; 
    	BiTNode t2;
    	BiTNode t3; 
    	BiTNode t4;
    	BiTNode t5; 
    	BiTNode t6; 
        memset(&t1,0,sizeof(BiTNode)); t1.data = 1; 
    	memset(&t2,0,sizeof(BiTNode)); t2.data = 2;
    	memset(&t3,0,sizeof(BiTNode)); t3.data = 3;
    	memset(&t4,0,sizeof(BiTNode)); t4.data = 4;
    	memset(&t5,0,sizeof(BiTNode)); t5.data = 5;
    	memset(&t6,0,sizeof(BiTNode)); t6.data = 6; 
    
    	t1.lchild = &t2;
    	t1.rchild = &t3;
    	t2.lchild = &t4;
    	t2.rchild = &t5;
    	t3.lchild = &t6;
    
    	return 0;
    }

2、二叉树的创建之关系创建（指针，需要使用memset初始化指针）

#include<stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct BiTNode 
    {
    	int data;
    	struct BiTNode *lchild;
    	struct BiTNode *rchild;
    };
    
    typedef struct BiTNode  BiTNode;
    typedef struct BiTNode* BiTree;
    
    int main()
    {
    	//create node
    	BiTNode *p1 = (BiTNode *)malloc(sizeof(BiTNode)); 
    	memset(p1,0, sizeof(BiTNode));
    	p1->data = 1;
    	BiTNode *p2 = (BiTNode *)malloc(sizeof(BiTNode)); 
    	memset(p2,0, sizeof(BiTNode));
    	p2->data = 2;
    	BiTNode *p3 = (BiTNode *)malloc(sizeof(BiTNode));
    	memset(p3,0, sizeof(BiTNode));
    	p3->data = 3;
    	BiTNode *p4 = (BiTNode *)malloc(sizeof(BiTNode)); 
    	memset(p4,0, sizeof(BiTNode));
    	p4->data = 4;
    	BiTNode *p5 = (BiTNode *)malloc(sizeof(BiTNode));
    	memset(p5,0, sizeof(BiTNode));
    	p5->data = 5;
    	BiTNode *p6 = (BiTNode *)malloc(sizeof(BiTNode)); 
    	memset(p6,0, sizeof(BiTNode));
    	p6->data = 6;
    
    
    	p1->lchild = p2;
    	p1->rchild = p3;
    	p2->lchild = p4;
    	p2->rchild = p5;
    	p3->lchild = p6;
    	return 0;
    }

3、二叉树创建之使用全局变量（三个遍历）

#include<stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct BiTNode 
    {
    	int pdata;
    	int ldata;
    	int rdata;
    };
    
    typedef struct BiTNode  BiTNode;
    #define MAX 1000
    #define NIL -1
    
    BiTNode Node[MAX] ; //节点
    int n = 6;//共6个节点
    
    void preParse(int root)
    {
    	if(Node[root].pdata == NIL)
    		return;
    	printf("%d ",Node[root].pdata);
    	preParse(Node[root].ldata);
    	preParse(Node[root].rdata);
    }
    
    void postParse(int root)
    {
    	if(Node[root].pdata == NIL)
    		return;
    	postParse(Node[root].ldata);
    	postParse(Node[root].rdata);
    	printf("%d ",Node[root].pdata);
    }
    
    void inParse(int root)
    {
    	if(Node[root].pdata == NIL)
    		return;
    	inParse(Node[root].ldata);
    	printf("%d ",Node[root].pdata);
    	inParse(Node[root].rdata);
    }
    
    int main()
    {
    	//create node
        int i;
    	for(i = 1; i <= n; i++)
    	{
    		Node[i].pdata = NIL;
    		Node[i].ldata = NIL;
    		Node[i].rdata = NIL;
    	}
    	Node[1].pdata = 1;
    	Node[2].pdata = 2;
    	Node[3].pdata = 3;
    	Node[4].pdata = 4;
    	Node[5].pdata = 5;
    	Node[6].pdata = 6;
    
    	Node[1].ldata = Node[2].pdata;
    	Node[1].rdata = Node[3].pdata;
    
    	Node[2].ldata = Node[4].pdata;
    	Node[2].rdata = Node[5].pdata;
    
    	Node[3].ldata = Node[6].pdata;
    	//前序遍历
    	preParse(1);
    	printf("\n");
    	//后序遍历
    	postParse(1);
    	printf("\n");
    	//中序遍历
    	inParse(1);
    	return 0;
    }

4、二叉树创建之使用\#（没有子节点的用**”\#“**替代，前序创建二叉树）**包含二叉树的释放，使用后序遍历释放**

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
     
    typedef struct BiTNode
    {
        int data;
        struct BiTNode *lchild;
        struct BiTNode *rchild;
    }BiTNode,*BiTree;
     
    void in_Order(BiTNode * root)    //先序遍历
    {
        if(root == NULL)
        {
            return ;
        }
        printf("%c",root->data);
        in_Order(root->lchild);//遍历左子树
        in_Order(root->rchild);//遍历右子树
    }
     
    
    BiTNode* create_tree()//先序创建
    {
        BiTNode *node = NULL;
        BiTNode *pleft  = NULL;
        BiTNode *pright = NULL;
        char c = getchar(); 
        if(c == '#')
        {
            return NULL;
        }
        else
        {
            node = (BiTNode*)malloc(sizeof(BiTNode));
            memset(node,0,sizeof(BiTNode));
            node->data = c;
     
            pleft = create_tree();
            if(pleft != NULL)
            {
                node->lchild = pleft;
            }
            else
            {
                node->lchild = NULL;
            }
             
            pright = create_tree();
            if(pleft != NULL)
            {
                node->rchild = pright;
            }
            else
            {
                node->rchild = NULL;
            }
        }
        return node;  
    }
     
    void free_tree(BiTNode* T)//后序释放
    {
        if(!T)
        {
            return ;
        }
        if(T->lchild)
        {
            free_tree(T->lchild);
            //T->lchild = NULL;
        }
        if(T->rchild)
        {
            free_tree(T->rchild);
            //T->rchild = NULL;
        }
        if(T)
        {
            free(T);
            T = NULL;
        }
    }
     
    int  main()
    {
        BiTNode *p = create_tree(); 
        in_Order(p);            
    	  printf("\n");
    	 //释放空间
        free_tree(p);
        return 0;
    }
    输入与结果:
    124##5##36###
    124536

5.二叉树的层序遍历

![Center 2][]

5、计算叶子节点的数目；（无论是先序遍历,中序遍历,后序遍历,求叶子的数字都不变;因为本质都是一样的,任何一个节点都会遍历3趟）

![Center 3][]

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    typedef struct BiTNode
    {
        int data;
        struct BiTNode *lchild;
        struct BiTNode *rchild;
    }BiTNode,*BiTree;
     
    void pre_Order(BiTNode * root)   //先序遍历
    {
        if(root == NULL)
        {
            return ;
        }
        printf("%d ",root->data);
        pre_Order(root->lchild);//遍历左子树
        pre_Order(root->rchild);//遍历右子树
    }
     
    void in_Order(BiTNode * root)    //中序遍历
    {
        if(root == NULL)
        {
            return ;
        }
        in_Order(root->lchild);//遍历左子树
        printf("%d ",root->data);
        in_Order(root->rchild);//遍历右子树
    }
     
    void post_Order(BiTNode * root)  //后序遍历
    {
        if(root == NULL)
        {
            return ;
        }
        post_Order(root->lchild);//遍历左子树
        post_Order(root->rchild);//遍历右子树
        printf("%d ",root->data);
    }
     
    void count_leaf(BiTNode * root,int * num)   
    {
        if(!root)
        {
            return ;
        }
        if(!root->rchild && !root->rchild)//当左右孩子都为空
        {
            (*num)++;
        }
        if(root->lchild)
        {
            count_leaf(root->lchild,num);//遍历左子树
        }
        if(root->rchild)
        {
            count_leaf(root->rchild,num);//遍历右子树
        }
        return ;
    }
    int main()
    {
        //创建节点
        BiTNode t1;    memset(&t1,0,sizeof(BiTNode));  t1.data = 1;
        BiTNode t2;    memset(&t2,0,sizeof(BiTNode));  t2.data = 2;
        BiTNode t3;    memset(&t3,0,sizeof(BiTNode));  t3.data = 3;
        BiTNode t4;    memset(&t4,0,sizeof(BiTNode));  t4.data = 4;
        BiTNode t5;    memset(&t5,0,sizeof(BiTNode));  t5.data = 5;
        //建立关系
        t1.lchild = &t2;
        t1.rchild = &t3;
        t2.lchild = &t4;
        t3.lchild = &t5;
     
        //树的遍历
        pre_Order(&t1);     printf("    先序遍历\n");
        in_Order(&t1);      printf("    中序遍历\n");
        post_Order(&t1);    printf("    后序遍历\n");
     
        int num = 0;
        count_leaf(&t1,&num);   //解决多线程,资源竞争问题
        printf("叶子节点的个数 %d\n",num);
     
        return 0;
    }

6.计算二叉树的高度

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    typedef struct BiTNode
    {
        int data;
        struct BiTNode *lchild;
        struct BiTNode *rchild;
    }BiTNode,*BiTree;
     
    int tree_dept(BiTNode * root)
    {
        int depth_left = 0;
        int depth_right = 0;
        if(!root)
        {
            return 0;
        }
        depth_left = tree_dept(root->lchild);
        depth_right = tree_dept(root->rchild);
        return  1+(depth_left>depth_right ? depth_left:depth_right);
    }
    int main()
    {
        //创建节点
        BiTNode t1;    memset(&t1,0,sizeof(BiTNode));  t1.data = 1;
        BiTNode t2;    memset(&t2,0,sizeof(BiTNode));  t2.data = 2;
        BiTNode t3;    memset(&t3,0,sizeof(BiTNode));  t3.data = 3;
        BiTNode t4;    memset(&t4,0,sizeof(BiTNode));  t4.data = 4;
        BiTNode t5;    memset(&t5,0,sizeof(BiTNode));  t5.data = 5;
        BiTNode t6;    memset(&t6,0,sizeof(BiTNode));  t6.data = 6;
        //建立关系
        t1.lchild = &t2;
        t1.rchild = &t3;
        t2.lchild = &t4;
        t3.lchild = &t5;
        t2.rchild = &t6;
     
        int depth = 0;
        depth = tree_dept(&t1);  
        printf("树的高度 %d\n",depth);
     
        return 0;
    }

[Center]: https://img-blog.csdn.net/20170709113754895?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvbG92ZV9nYW9oeg==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: /images/20220613/d877d5f6789c4d25a4830fdb2ef9505a.png
[Center 2]: /images/20220613/aefffbf95b904b889a931df49fdd19aa.png
[Center 3]: /images/20220613/c4f753138b27421a9b9e3226eaec0203.png