HelloWorld
登录

树与二叉树

似梦清欢

2022-12-07

1566 1 0
二叉树层次建树

二叉树（Binary Tree）是由有限个结点组成的集合，它或者为空集合，或者仅含一个根结点，或者由一个根结点和两棵互不相交的左、右子树组成。 树为空即根节点为空。 二叉树的基本形态如下图： image a：空的二叉树，tree=NULL。 b：只有空节点的二叉树，tree=A。 c：只有左子树的二叉树。 d：只有右子树的二叉树。 e：左右子树都存在。分为完全二叉树和满二叉树。 ::: tip 满二叉树：除叶子节点外，其余节点都是满的。 完全二叉树：除末尾的叶子节点外，其余节点都是满的（其余节点必须连续放满）。完全二叉树节点编号时是连续的。 ::: ::: warning 二叉树编号时从1开始。孩子节点的序号/2=父节点的序号。 :::

二叉树的单一个体如下图所示，结构体是由该单一个体确定的。 image typedef struct BiTNode { char data; //数据 struct BiTNode* lchild; //左子树 struct BiTNode* rchild; //右子树 }; 树定义与二叉树定义稍有区别。首先，树不能是空树（更正：树可以为空（0个节点））却可以有空二叉树。其次，一般树的子树的不分次序，而二叉树的子树却分左、右子树，即使在仅有一棵子树的情况下也要指明是左子树还是右子树。最后，一般树中结点的度(子树数目)可以大于2，但二叉树中结点的度均不超过2。

辅助队列是链表实现的，没有头节点，起始时头指针和尾指针都指向第一个节点，此时辅助队列为空，即树为空。 二叉树层次建树代码实现： 结构体类型声明放在function.h头文件中。 function.h：

1#include <stdio.h>
2#include <stdlib.h>
3
4typedef char BiElemType;
5//树的队列
6typedef struct BiTNode
7{
8	BiElemType data;
9	struct BiTNode* lchild;
10	struct BiTNode* rchild;
11}BiTNode, * BiTree;
12
13//辅助队列使用，队列是链表实现的
14typedef struct tag
15{
16	BiTree p;  //树的某一结点的地址，需要使用指针
17	struct tag* pnext;  //链表中的next指针，用于指向下一个节点
18}tag_t, * ptag_t;

main.cpp：

1#include "function.h"
2
3int main()
4{
5    BiTree pnew;  //pnew指向树申请的新节点的指针
6    BiTree tree = NULL;  //tree指向树根（第一个节点，即根节点），用来代表树，树根需要初始化为NULL
7    char data;  //要输入的元素（abcdefghij）
8    ptag_t phead = NULL, ptail = NULL;  //队列头指针和队列尾指针初始化为NULL
9    ptag_t list_pnew = NULL, pcur = NULL;  //辅助队列中list_pnew和树中pnew对应，pcur指向当前读进树中的节点的父亲节点
10    while (scanf("%c", &data))  //把每一个字符作为树的节点存入树中
11    {
12        if (data == '\n')
13        {
14            break;  //读取输入内容时，末尾的\n不放入树
15        }
16        pnew = (BiTree)calloc(1, sizeof(BiTNode));  //每读入一个数据，都要开辟节点
17        //使用malloc开辟节点时，读取的字符存在data中，但是左右孩子需要初始化为NULL，比较麻烦
18        //calloc申请空间的大小是两个参数的乘积，calloc申请空间后会先将空间初始化为0
19        pnew->data = data;  //将读进来的数据存进申请树的结构体的data中
20        list_pnew = (ptag_t)calloc(1, sizeof(tag_t));  //该节点的地址放入辅助队列，给队列节点申请空间
21        list_pnew->p = pnew;  //队列结构体中p存放的是树中对应结点pnew的地址
22        //判断是否为树的第一个节点
23        if (NULL == tree)  //当tree=NULL时，树为空，即此时树中开辟的节点是根节点，辅助队列中申请的是第一个节点
24        {
25            tree = pnew;  //树为空时，tree指向读入的第一个节点（根节点），其余字符读进来时tree不为空
26            phead = ptail = list_pnew;  //起始时辅助队列中队列头和队列尾都指向第一个节点a
27            pcur = list_pnew;  //pcur指向读入节点的父亲节点，只有一个根节点a时，pcur指向根节点a
28        }
29        else {
30            //元素b先入队列
31            ptail->pnext = list_pnew;  //读入新元素（b）的地址放在队列尾指针的pnext域
32            ptail = list_pnew;  //新读入的元素b变为队列新的尾部，
33            //节点b放入树中
34            if (NULL == pcur->p->lchild)
35            {
36                pcur->p->lchild = pnew;  //当pcur指向的节点a的左孩子为NULL时，a的左孩子指向新节点b
37            }
38            else if (NULL == pcur->p->rchild)  //读入第三个元素c时
39            {
40                pcur->p->rchild = pnew;  //当pcur指向的节点a的左孩子不为NULL右孩子为NULL时，a的又孩子指向新节点c
41                pcur = pcur->pnext;  //pcur->p即节点a的左右孩子都已经放了节点后，当前节点放满，pcur指向下一个节点b
42            }
43        }
44    }
45    return 0;
46}

层次建树代码重写：

1#include <stdio.h>
2#include <stdlib.h>
3
4typedef char Elemtype;
5typedef struct Node
6{
7	Elemtype data;
8	struct Node* lchlid;
9	struct Node* rchlid;
10}Node, * pNode;
11//辅助队列使用（不带头结点的链表实现）
12typedef struct tag
13{
14	pNode c;  //辅助队列中的节点（存放树节点的地址）
15	struct tag* next;
16}tag, * ptag;
17
18int main()
19{
20	pNode pnew;  //指向新申请的树的节点
21	pNode tree = NULL;  //tree为树根，代表树，树根初始化为null
22	char data;  //用来接收输入的数据
23	ptag phead = NULL, ptail = NULL;  //队列头尾节点
24	ptag pcur = NULL, listpnew = NULL;  //listpnew指向新申请的节点，pcur指向新节点入队时候的父节点
25	while (scanf("%c", &data))
26	{
27		if (data == '\n')
28		{
29			break;
30		}
31		pnew = (pNode)calloc(1, sizeof(Node));  //树的节点申请空间
32		pnew->data = data;
33		listpnew = (ptag)calloc(1, sizeof(tag));  //辅助队列申请申请空间
34		listpnew->c = pnew;  //将要放入树中的节点入队
35		if (NULL == tree)
36		{
37			tree = pnew;  //当树为空时，将树申请的节点pnew放入树中，pnew就是树中的第一个节点，树根tree指向第一个节点pnew
38			phead = listpnew, ptail = listpnew;  //队列中只有一个节点时，队列的头尾节点都指向该节点
39			pcur = listpnew;  //下一个节点放入树中时，父节点是队列中listpnew指向的节点
40		}
41		else 
42		{
43			////先放入树中
44			//if (NULL == pcur->c->lchlid)
45			//{
46			//	pcur->c->lchlid = pnew;
47			//}
48			//else if (NULL == pcur->c->rchlid)
49			//{
50			//	pcur->c->rchlid = pnew;
51			//	pcur = pcur->next;
52			//}
53			////再放入队列中
54			//ptail->next = listpnew;
55			//ptail = listpnew;
56
57			//先放入队列
58			ptail->next = listpnew;
59			ptail = listpnew;
60			//再放入树中
61			if (NULL == pcur->c->lchlid)
62			{
63				pcur->c->lchlid = pnew;
64			}
65			else if (NULL == pcur->c->rchlid)
66			{
67				pcur->c->rchlid = pnew;
68				pcur = pcur->next;
69			}
70		}
71	}
72	return 0;
73}
二叉树前序中序后序遍历

二叉树前序中序后序遍历代码是在二叉树层次建树的基础上增加前序中序后序遍历代码实现的。 前序遍历是先打印自身，再打印左子树，再打印右子树。（这里通过PreOrder实现） ::: tip 前序遍历又叫深度优先遍历。 ::: 中序遍历是先打印左子树，再打印当前节点，再打印右子树。（这里通过InOrder实现） 后序遍历是先打印左子树，再打印右子树，再打印当前节点。（这里通过PostOrder实现） ::: warning 每棵树的打印输出节点都在这棵树的父节点旁，递归操作时每次只看一棵子树。 ::: 前序遍历代码：

1void PreOder(BiTree tree)
2{
3    if (tree != NULL)
4    {
5        printf("%c", tree->data);  //打印当前节点
6        PreOder(tree->lchild);  //打印左子树
7        PreOder(tree->rchild);  //打印右子树
8    }
9}

中序遍历代码：

1void InOder(BiTree tree)
2{
3    if (tree != NULL)
4    {
5        InOder(tree->lchild);  //打印左子树
6        printf("%c", tree->data);  //打印当前节点
7        InOder(tree->rchild);  //打印右子树
8    }
9}

后序遍历代码：

1void PostOder(BiTree tree)
2{
3    if (tree != NULL)
4    {
5        PostOder(tree->lchild);  //打印左子树
6        PostOder(tree->rchild);  //打印右子树
7        printf("%c", tree->data);  //打印当前节点
8    }
9}
二叉树层序遍历

::: tip 层序遍历又称广度优先遍历。 ::: 层序遍历类似于层次建树原理，需要使用辅助队列。 层序遍历是在之前代码中前中后序遍历时已经建好的树的基础上再建一个辅助队列完成。 ::: tip 原理：先将元素a入队，然后判断队列是否为空，如果队列不为空，将a出队（并打印），出队后将a销毁，再判断最左孩子是否为空，如不为空则入队（b），再判断右孩子是否为空，如不为空则入队（c），重新进行循环判断是否为空（队列中有b、c），进入循环，打印并出队b… ::: 层序遍历代码：

1//层序遍历（广度优先遍历）
2void LevelOrder(BiTree tree)
3{
4    LinkQueue Q;
5    InitQueue(Q);
6    BiTree p;  //存储出队节点
7    EnQueue(Q,tree);  //根节点入队
8    while(!IsEmpty(Q))  //队列不为空则进入循环
9    {
10        DeQueue(Q,p);
11        putchar(p->data);
12        if(NULL!=p->lchild)  //可以简写成p->lchild
13        {
14            EnQueue(Q,p->lchild);
15        }
16        if(NULL!=p->rchild)
17        {
18            EnQueue(Q,p->rchild);
19        }
20    }
21}

二叉树的前中后序和层序遍历全部代码： function.h：

1#include <stdio.h>
2#include <stdlib.h>
3
4typedef char BiElemType;
5//树的队列
6typedef struct BiTNode
7{
8    BiElemType data;
9    struct BiTNode* lchild;
10    struct BiTNode* rchild;
11}BiTNode, * BiTree;
12
13//建树辅助队列使用，队列是链表实现的
14typedef struct tag
15{
16    BiTree p;  //树的某一结点的地址，需要使用指针
17    struct tag* pnext;  //链表中的next指针，用于指向下一个节点
18}tag_t, * ptag_t;
19
20//层序遍历辅助队列使用
21typedef BiTree Elemtype;
22typedef struct LinkNode  //链表
23{
24    Elemtype data;  //层序遍历中存放的是树的节点指针（BiTree类型）
25    struct LinkNode* next;
26}LinkNode;
27typedef struct  //队列
28{
29    LinkNode* front, * rear;
30}LinkQueue;
31
32//函数调用
33void InitQueue(LinkQueue& Q);
34bool IsEmpty(LinkQueue Q);
35void EnQueue(LinkQueue& Q, Elemtype x);
36bool DeQueue(LinkQueue& Q, Elemtype& x);

queue.cpp：

1#include "function.h"
2
3//队列初始化，带头节点的链表实现
4void InitQueue(LinkQueue& Q)
5{
6	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));  //头节点
7	Q.front->next = NULL;
8}
9
10//判断队列是否为空
11bool IsEmpty(LinkQueue Q)
12{
13	return Q.front == Q.rear;  //判断为真（相等）返回1（true）
14}
15
16//入队
17void EnQueue(LinkQueue& Q, Elemtype x)
18{
19	LinkNode* pnew = (LinkNode*)malloc(sizeof(LinkNode));
20	pnew->data = x;
21	pnew->next = NULL;
22	Q.rear->next = pnew;  //原队尾rear的next指向NULL，pnew从队尾插入，rear的next指向新队尾
23	Q.rear = pnew;  //rear指向新的队尾
24}
25
26//出队
27bool DeQueue(LinkQueue& Q, Elemtype& x)
28{
29	if (Q.front == Q.rear)
30	{
31		return false;
32	}
33	//x = Q.front->data;
34	LinkNode* p = Q.front->next;
35	x = p->data;
36	Q.front->next = p->next;
37	if (p == Q.rear)  //该节点为链表中最后一个节点
38	{
39		Q.rear = Q.front;  //rear指向front指向位置
40	}
41	free(p);
42	p = NULL;
43	return true;
44}

main.cpp：

1#include "function.h"
2
3//前序遍历（深度优先遍历）
4void PreOrder(BiTree tree)
5{
6    if (tree != NULL)
7    {
8        printf("%c", tree->data);  //打印当前节点
9        PreOrder(tree->lchild);  //打印左子树
10        PreOrder(tree->rchild);  //打印右子树
11    }
12}
13
14//中序遍历
15void InOrder(BiTree tree)
16{
17    if (tree != NULL)
18    {
19        InOrder(tree->lchild);  //打印左子树
20        printf("%c", tree->data);  //打印当前节点
21        InOrder(tree->rchild);  //打印右子树
22    }
23}
24
25//后序遍历
26void PostOrder(BiTree tree)
27{
28    if (tree != NULL)
29    {
30        PostOrder(tree->lchild);  //打印左子树
31        PostOrder(tree->rchild);  //打印右子树
32        printf("%c", tree->data);  //打印当前节点
33    }
34}
35
36//层序遍历（广度优先遍历）
37void LevelOrder(BiTree tree)
38{
39    LinkQueue Q;
40    InitQueue(Q);
41    BiTree p;  //存储出队节点
42    EnQueue(Q, tree);  //根节点入队
43    while (!IsEmpty(Q))  //队列不为空则进入循环
44    {
45        DeQueue(Q, p);
46        putchar(p->data);
47        if (NULL != p->lchild)
48        {
49            EnQueue(Q, p->lchild);
50        }
51        if (NULL != p->rchild)
52        {
53            EnQueue(Q, p->rchild);
54        }
55
56    }
57}
58
59int main()
60{
61    //层次建树
62    BiTree pnew;  //pnew指向树申请的新节点的指针
63    BiTree tree = NULL;  //tree指向树根（第一个节点，即根节点），用来代表树，树根需要初始化为NULL
64    char data;  //要输入的元素（abcdefghij）
65    ptag_t phead = NULL, ptail = NULL;  //队列头指针和队列尾指针初始化为NULL
66    ptag_t list_pnew = NULL, pcur = NULL;  //辅助队列中list_pnew和树中pnew对应，pcur指向当前读进树中的节点的父亲节点
67    while (scanf("%c", &data))  //把每一个字符作为树的节点存入树中
68    {
69        if (data == '\n')
70        {
71            break;  //读取输入内容时，末尾的\n不放入树
72        }
73        pnew = (BiTree)calloc(1, sizeof(BiTNode));  //每读入一个数据，都要开辟节点
74        //使用malloc开辟节点时，读取的字符存在data中，但是左右孩子需要初始化为NULL，比较麻烦
75        //calloc申请空间的大小是两个参数的乘积，calloc申请空间后会先将空间初始化为0
76        pnew->data = data;  //将读进来的数据存进申请树的结构体的data中
77        list_pnew = (ptag_t)calloc(1, sizeof(tag_t));  //该节点的地址放入辅助队列，给队列节点申请空间
78        list_pnew->p = pnew;  //队列结构体中p存放的是树中对应结点pnew的地址
79        //判断是否为树的第一个节点
80        if (NULL == tree)  //当tree=NULL时，树为空，即此时树中开辟的节点是根节点，辅助队列中申请的是第一个节点
81        {
82            tree = pnew;  //树为空时，tree指向读入的第一个节点（根节点），其余字符读进来时tree不为空
83            phead = ptail = list_pnew;  //起始时辅助队列中队列头和队列尾都指向第一个节点a
84            pcur = list_pnew;  //pcur指向读入节点的父亲节点，只有一个根节点a时，pcur指向根节点a
85        }
86        else {
87            //元素b先入队列
88            ptail->pnext = list_pnew;  //读入新元素（b）的地址放在队列尾指针的pnext域
89            ptail = list_pnew;  //新读入的元素b变为队列新的尾部，
90            //节点b放入树中
91            if (NULL == pcur->p->lchild)
92            {
93                pcur->p->lchild = pnew;  //当pcur指向的节点a的左孩子为NULL时，a的左孩子指向新节点b
94            }
95            else if (NULL == pcur->p->rchild)  //读入第三个元素c时
96            {
97                pcur->p->rchild = pnew;  //当pcur指向的节点a的左孩子不为NULL右孩子为NULL时，a的又孩子指向新节点c
98                pcur = pcur->pnext;  //pcur->p即节点a的左右孩子都已经放了节点后，当前节点放满，pcur指向下一个节点b
99            }
100        }
101    }
102    printf("------------------前序遍历------------------\n");
103    PreOrder(tree);
104    printf("\n");
105    printf("------------------中序遍历------------------\n");
106    InOrder(tree);
107    printf("\n");
108    printf("------------------后序遍历------------------\n");
109    PostOrder(tree);
110    printf("\n");
111    printf("------------------层序遍历------------------\n");
112    LevelOrder(tree);
113    printf("\n");
114    return 0;
115}

二叉树的前中后序和层序遍历全部代码：

1#define _CRT_SECURE_NO_WARNINGS
2#include <stdio.h>
3#include <stdlib.h>
4
5typedef char Elemtype;
6//建树使用
7typedef struct Node
8{
9	Elemtype data;
10	struct Node* lchlid;
11	struct Node* rchlid;
12}Node, * pNode;
13//辅助队列使用（不带头结点的链表实现）
14typedef struct tag
15{
16	pNode c;  //辅助队列中的节点（存放树节点的地址）
17	struct tag* next;
18}tag, * ptag;
19//层序遍历使用
20typedef struct LinkNode  //节点的结构体
21{
22	pNode data;
23	struct LinkNode* next;
24}LinkNode;
25typedef struct  //队列的结构体
26{
27	LinkNode* front, * rear;
28}LinkQueue;
29
30//前序遍历（深度优先遍历）
31void PreOrder(pNode tree)
32{
33	if (NULL != tree)
34	{
35		printf("%c", tree->data);
36		PreOrder(tree->lchlid);
37		PreOrder(tree->rchlid);
38	}
39}
40//中序遍历
41void InOrder(pNode tree)
42{
43	if (NULL != tree)
44	{
45		InOrder(tree->lchlid);
46		printf("%c", tree->data);
47		InOrder(tree->rchlid);
48	}
49}
50//后序遍历
51void PostOrder(pNode tree)
52{
53	if (NULL != tree)
54	{
55		PostOrder(tree->lchlid);
56		PostOrder(tree->rchlid);
57		printf("%c", tree->data);
58	}
59}
60//层序遍历
61//带头结点的队列
62void InitQueue(LinkQueue& Q)  //初始化
63{
64	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
65}
66bool IsEmpty(LinkQueue Q)//判断是否为空
67{
68	return Q.front == Q.rear;
69}
70void EnQueue(LinkQueue& Q,pNode x)//入队
71{
72	LinkNode* pnew = (LinkNode*)malloc(sizeof(LinkNode));
73	pnew->data = x;
74	Q.rear->next = pnew;
75	Q.rear = pnew;
76}
77bool DeQueue(LinkQueue& Q, pNode& x)//出队
78{
79	if (Q.front==Q.rear)
80	{
81		return false;
82	}
83	LinkNode* p = Q.front->next; //带头结点的队列，先进先出，队头出队，队尾入队
84	x = p->data;
85	Q.front->next = p->next;
86	if (p == Q.rear)
87	{
88		Q.rear = Q.front;  //链表只剩余一个节点被删除后，rear要指向front，否则队列判断为空时会出错
89	}
90	free(p);
91	p = NULL;
92	return true;
93}
94void LevelOrder(pNode tree)
95{
96	LinkQueue Q;
97	InitQueue(Q);
98	EnQueue(Q,tree);
99	pNode p;  //用来存储出队节点
100	while (!IsEmpty(Q))
101	{
102		DeQueue(Q, p);
103		putchar(p->data);
104		if (NULL != p->lchlid)
105		{
106			EnQueue(Q, p->lchlid);
107		}
108		if (NULL != p->rchlid)
109		{
110			EnQueue(Q, p->rchlid);
111		}
112	}
113}
114int main()
115{
116	pNode pnew;  //指向新申请的树的节点
117	pNode tree = NULL;  //tree为树根，代表树，树根初始化为null
118	char data;  //用来接收输入的数据
119	ptag phead = NULL, ptail = NULL;  //队列头尾节点
120	ptag pcur = NULL, listpnew = NULL;  //listpnew指向新申请的节点，pcur指向新节点入队时候的父节点
121	while (scanf("%c", &data))
122	{
123		if (data == '\n')
124		{
125			break;
126		}
127		pnew = (pNode)calloc(1, sizeof(Node));  //树的节点申请空间
128		pnew->data = data;
129		listpnew = (ptag)calloc(1, sizeof(tag));  //辅助队列申请申请空间
130		listpnew->c = pnew;  //将要放入树中的节点入队
131		if (NULL == tree)
132		{
133			tree = pnew;  //当树为空时，将树申请的节点pnew放入树中，pnew就是树中的第一个节点，树根tree指向第一个节点pnew
134			phead = listpnew, ptail = listpnew;  //队列中只有一个节点时，队列的头尾节点都指向该节点
135			pcur = listpnew;  //下一个节点放入树中时，父节点是队列中listpnew指向的节点
136		}
137		else 
138		{
139			////先放入树中
140			//if (NULL == pcur->c->lchlid)
141			//{
142			//	pcur->c->lchlid = pnew;
143			//}
144			//else if (NULL == pcur->c->rchlid)
145			//{
146			//	pcur->c->rchlid = pnew;
147			//	pcur = pcur->next;
148			//}
149			////再放入队列中
150			//ptail->next = listpnew;
151			//ptail = listpnew;
152
153			//先放入队列
154			ptail->next = listpnew;
155			ptail = listpnew;
156			//再放入树中
157			if (NULL == pcur->c->lchlid)
158			{
159				pcur->c->lchlid = pnew;
160			}
161			else if (NULL == pcur->c->rchlid)
162			{
163				pcur->c->rchlid = pnew;
164				pcur = pcur->next;
165			}
166		}
167	}
168	PreOrder(tree);
169	InOrder(tree);
170	printf("\n");
171	PostOrder(tree);
172	printf("\n");
173	LevelOrder(tree);
174	return 0;
175}

image WPL：树的所有叶结点的带权路径长度之和，称为树的带权路径长度表示为WPL。（WPL只涉及叶子节点） image 如上图，每个叶节点的权值为节点的data值，深度为层的深度。 image image ::: tip C++的static变量是静态局部变量。static变量在函数内定义, 生存期为整个源程序，但作用域与局部变量相同，只能在定义该变量的函数内使用。退出该函数后， 尽管该变量还继续存在，但不能使用它。递归的过程中只生效一次。 :::

代码实现： function.h：

1#pragma once
2#include <stdio.h>
3#include <stdlib.h>
4typedef int BiElemType;
5typedef struct BiTNode
6{
7	BiElemType weight;
8	struct BiTNode* left;
9	struct BiTNode* right;
10}BiTNode, * BiTree;
11
12//建树辅助队列使用，队列是链表实现的
13typedef struct tag
14{
15    BiTree p;  //树的某一结点的地址，需要使用指针
16    struct tag* pnext;  //链表中的next指针，用于指向下一个节点
17}tag_t, * ptag_t;
18
19//层序遍历辅助队列使用
20typedef BiTree Elemtype;
21typedef struct LinkNode  //链表
22{
23    Elemtype data;  //层序遍历中存放的是树的节点指针（BiTree类型）
24    struct LinkNode* next;
25}LinkNode;
26typedef struct  //队列
27{
28    LinkNode* front, * rear;
29}LinkQueue;
30
31//函数调用
32void InitQueue(LinkQueue& Q);
33bool IsEmpty(LinkQueue Q);
34void EnQueue(LinkQueue& Q, Elemtype x);
35bool DeQueue(LinkQueue& Q, Elemtype& x);

main.cpp：

1#define _CRT_SECURE_NO_WARNINGS
2#include "function.h"
3
4////使用全局变量时
5//int wpl = 0;  //全局变量
6////前序遍历
7//void WPL_PreOrder(BiTree tree, int deep)
8//{
9//	if (NULL != tree)
10//	{
11//        /*printf("Elem%c---%d", tree->weight, deep);*/
12//        if (tree->left == NULL && tree->right == NULL)  //判断是否是叶子节点，不是叶子节点才需要向下递归
13//        {
14//            wpl = wpl + tree->weight * deep;
15//        }
16//        WPL_PreOrder(tree->left, deep + 1);  //每次向下遍历，深度（层数+1）
17//        WPL_PreOrder(tree->right, deep + 1);
18//	}
19//}
20
21//使用局部静态变量时
22//前序遍历
23int WPL_PreOrder(BiTree tree, int deep)
24{
25    static int wpl;
26	if (NULL != tree)
27	{
28        /*printf("Elem%c---%d", tree->weight, deep);*/
29        if (tree->left == NULL && tree->right == NULL)  //判断是否是叶子节点，不是叶子节点才需要向下递归
30        {
31            wpl = wpl + tree->weight * deep;
32        }
33        WPL_PreOrder(tree->left, deep + 1);  //每次向下遍历，深度（层数+1）
34        WPL_PreOrder(tree->right, deep + 1);
35	}
36    return wpl;
37}
38
39int main()
40{
41    //层次建树
42    BiTree pnew;  //pnew指向树申请的新节点的指针
43    BiTree tree = NULL;  //tree指向树根（第一个节点，即根节点），用来代表树，树根需要初始化为NULL
44    char data;  //要输入的元素（abcdefghij）
45    ptag_t phead = NULL, ptail = NULL;  //队列头指针和队列尾指针初始化为NULL
46    ptag_t list_pnew = NULL, pcur = NULL;  //辅助队列中list_pnew和树中pnew对应，pcur指向当前读进树中的节点的父亲节点
47    while (scanf("%c", &data))  //把每一个字符作为树的节点存入树中
48    {
49        if (data == '\n')
50        {
51            break;  //读取输入内容时，末尾的\n不放入树
52        }
53        pnew = (BiTree)calloc(1, sizeof(BiTNode));  //每读入一个数据，都要开辟节点
54        //使用malloc开辟节点时，读取的字符存在data中，但是左右孩子需要初始化为NULL，比较麻烦
55        //calloc申请空间的大小是两个参数的乘积，calloc申请空间后会先将空间初始化为0
56        pnew->weight = data;  //将读进来的数据存进申请树的结构体的data中
57        list_pnew = (ptag_t)calloc(1, sizeof(tag_t));  //该节点的地址放入辅助队列，给队列节点申请空间
58        list_pnew->p = pnew;  //队列结构体中p存放的是树中对应结点pnew的地址
59        //判断是否为树的第一个节点
60        if (NULL == tree)  //当tree=NULL时，树为空，即此时树中开辟的节点是根节点，辅助队列中申请的是第一个节点
61        {
62            tree = pnew;  //树为空时，tree指向读入的第一个节点（根节点），其余字符读进来时tree不为空
63            phead = ptail = list_pnew;  //起始时辅助队列中队列头和队列尾都指向第一个节点a
64            pcur = list_pnew;  //pcur指向读入节点的父亲节点，只有一个根节点a时，pcur指向根节点a
65        }
66        else {
67            //元素b先入队列
68            ptail->pnext = list_pnew;  //读入新元素（b）的地址放在队列尾指针的pnext域
69            ptail = list_pnew;  //新读入的元素b变为队列新的尾部，
70            //节点b放入树中
71            if (NULL == pcur->p->left)
72            {
73                pcur->p->left = pnew;  //当pcur指向的节点a的左孩子为NULL时，a的左孩子指向新节点b
74            }
75            else if (NULL == pcur->p->right)  //读入第三个元素c时
76            {
77                pcur->p->right = pnew;  //当pcur指向的节点a的左孩子不为NULL右孩子为NULL时，a的又孩子指向新节点c
78                pcur = pcur->pnext;  //pcur->p即节点a的左右孩子都已经放了节点后，当前节点放满，pcur指向下一个节点b
79            }
80        }
81    }
82    printf("------------------前序遍历------------------\n");
83    //WPL_PreOrder(tree,0);  //wpl统计的是路径，首次传入值应该为0。全局变量使用
84    printf("\n");
85    //printf("wpl=%d", wpl);  //全局变量使用
86    printf("wpl=%d", WPL_PreOrder(tree, 0));  //局部静态变量使用
87    return 0;
88}
点赞
收藏

评论区

加载中...

相关推荐

二叉树展开为链表

给你二叉树的根结点root，请你将它展开为一个单链表：展开后的单链表应该同样使用TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。展开后的单链表应该与二叉树先序遍历顺序相同。classSolutionpublicvoidflatten(TreeNoderoot)if

二叉树题集(持续更新中)

对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。1\.求二叉搜索树最大深度输入格式：输入给出一行整数序列作为二叉搜索树的键值，数字间以空格分隔，输入0结束(0不计入该二叉树键值)。输入样例：8685109110输出样例：4常规的求二叉搜索树深度的做法是递

线索二叉树的原理及创建

【系列推荐阅读】1.为什么要用到线索二叉树？我们先来看看普通的二叉树有什么缺点。下面是一个普通二叉树（链式存储方式）：乍一看，会不会有一种违和感？整个结构一共有7个结点，总共14个指针域，其中却有8个指针域都是空的。对于一颗有n个结点的二叉树而言，总共会有n1个空指针域，这个规律使用所有的二叉树。这么多的空指针域是不

B树与B+树的区别？

1.B树简介B树是一种多路平衡搜索树。它由二叉树变换而来的。定义如下：1.1每个节点最多有m1个关键字1.2根节点最少有1个关键字1.3非根节点至少有m/2个关键字1.4每个节点的关键字都是按照从小到大的顺序排列，每个关键字的左子树中的关键字都小于它，而右子树中所有关键字都大于它。1.5所有的叶子节点都处于同

JAVA递归实现线索化二叉树

JAVA递归实现线索化二叉树基础理论首先，二叉树递归遍历分为先序遍历、中序遍历和后序遍历。先序遍历为：根节点左子树右子树中序遍历为：左子树根节点右子树后序遍历为：左子树右子树根节点（只要记住根节点在哪里就是什么遍历，且都是先左再右）线索化现在有这么一棵二叉树，它的数据结

Java实现 LeetCode 814 二叉树剪枝 （遍历树）

814\.二叉树剪枝给定二叉树根结点root，此外树的每个结点的值要么是0，要么是1。返回移除了所有不包含1的子树的原二叉树。(节点X的子树为X本身，以及所有X的后代。)示例1:输入:\1,null,0,0,1\输出:\1,null,0,null,1\解释: