二叉树遍历算法的应用

本文主要是介绍二叉树遍历算法的应用，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 二叉树的抽象数据结构

1 typedef struct Node
2 {
3     char data;
4     struct Node* Lchild;
5     struct Node* Rchild;
6 }BTNode;//Binary Tree Node

打印二叉树的叶子结点

 1 void PrintLeafNode(BTNode* A)
 2 {/*打印二叉树的叶子结点*/
 3     if (A == NULL)
 4     {
 5         return;
 6     }
 7     else if ((!A->Lchild) && (!A->Rchild))
 8     {
 9         printf("%c", A->data);
10         return;
11     }
12     else
13     {
14         PrintLeafNode(A->Lchild);
15         PrintLeafNode(A->Rchild);
16     }
17 }

二叉树相似性判定(所谓二叉树 A 和 B 相似，是指 A 和 B 要么均为空二叉树、要么 A 的左子树与 B 的左子树相似，且 A 的右子树与 B 的右子树相似)

 1 int Like(BTNode* A, BTNode* B)
 2 {/*二叉树相似性判定*/
 3     int Like1 = 0;
 4     int Like2 = 0;
 5     if (A == NULL && B == NULL)
 6     {
 7         return 1;
 8     }
 9     else if (A == NULL || B == NULL)
10     {
11         return 0;
12     }
13     else
14     {
15         Like1 = Like(A->Lchild, B->Lchild);
16         Like2 = Like(A->Rchild, B->Rchild);
17         return Like1 && Like2;
18     }
19 }

求二叉树高度

 1 int DepthTree(BTNode* A)
 2 {/*求二叉树高度*/
 3     int Depth = 0;
 4     int DepthLeft = 0;
 5     int DepthRight = 0;
 6     if (A)
 7     {
 8         DepthLeft = DepthTree(A->Lchild);
 9         DepthRight = DepthTree(A->Rchild);
10         Depth = 1 + (DepthLeft > DepthRight ? DepthLeft : DepthRight);
11     }
12     return Depth;
13 }

统计二叉树的结点数

 1 int CountNode(BTNode* A)
 2 {/*统计二叉树的结点数*/
 3     int sum = 0;
 4     if (A)
 5     {
 6         sum++;
 7         sum += CountNode(A->Lchild);
 8         sum += CountNode(A->Rchild);
 9     }
10     return sum;
11 }

统计叶子结点数目

 1 int CountLeafNode(BTNode* A)
 2 {/*统计叶子结点数目*/
 3     int sum = 0;
 4     if (A)
 5     {
 6         if (!A->Lchild && !A->Rchild)
 7         {
 8             sum++;
 9         }
10         sum += CountLeafNode(A->Lchild);
11         sum += CountLeafNode(A->Rchild);
12     }
13     return sum;
14 }

求结点的双亲

 1 char Parent(BTNode* A, char ChildNode)
 2 {/*求结点的双亲*/
 3     char ParentNode = '\0';
 4     if (A == NULL)
 5     {
 6         return '\0';
 7     }
 8     else if (A->Lchild && A->Lchild->data == ChildNode)
 9     {
10         return A->data;
11     }
12     else if (A->Rchild && A->Rchild->data == ChildNode)
13     {
14         return A->data;
15     }
16     else
17     {
18         ParentNode = Parent(A->Lchild, ChildNode);
19         if (ParentNode != '\0')
20         {
21             return ParentNode;
22         }
23         else
24         {/*递归在右子树中找*/
25             return Parent(A->Rchild, ChildNode);
26         }
27     }
28 }

源代码

  1 #define _CRT_SECURE_NO_WARNINGS
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 
  5 typedef struct Node
  6 {
  7     char data;
  8     struct Node* Lchild;
  9     struct Node* Rchild;
 10 }BTNode;//Binary Tree Node
 11 
 12 BTNode* CreateBinaryTree();
 13 void PrintLeafNode(BTNode* A);
 14 int Like(BTNode* A, BTNode* B);
 15 int DepthTree(BTNode* A);
 16 int CountNode(BTNode* A);
 17 int CountLeafNode(BTNode* A);
 18 char Parent(BTNode* A, char ChildNode);
 19 
 20 
 21 int main(void)
 22 {
 23     char ChildNode = '\0';
 24     char ParentNode = '\0';
 25     BTNode* A = NULL;
 26     BTNode* B = NULL;
 27 
 28     printf("请输入该二叉树先序遍历序列(用^表示空子树,叶子结点要跟两个^)：\n");
 29     A = CreateBinaryTree();
 30 
 31     printf("树的高度：%d\n", DepthTree(A));
 32     printf("树总结点数：%d\n", CountNode(A));
 33     printf("叶子结点数：%d\n", CountLeafNode(A));
 34 
 35     printf("叶子结点为：");
 36     PrintLeafNode(A);
 37 
 38     printf("\n请输入要查询双亲的结点：");
 39     scanf(" %c", &ChildNode);/* %c前有一个空格用于吸收空白字符 */
 40     ParentNode = Parent(A, ChildNode);
 41     if (ParentNode == '\0')
 42     {
 43         printf("查询失败\n");
 44     }
 45     else
 46     {
 47         printf("%c的双亲结点是%c", ChildNode, ParentNode);
 48     }
 49 
 50     printf("\n请输入另一个二叉树先序遍历序列(用^表示空子树,叶子结点要跟两个^)：\n");
 51     B = CreateBinaryTree();
 52     if (Like(A, B))
 53     {
 54         printf("二叉树A和B相似\n");
 55     }
 56     else
 57     {
 58         printf("二叉树A和B不相似\n");
 59     }
 60 
 61     system("pause");
 62     return 0;
 63 }
 64 
 65 BTNode* CreateBinaryTree()
 66 {
 67     BTNode* A = NULL;
 68     char ch = '\0';
 69     scanf(" %c", &ch);
 70     if (ch == '^')
 71     {
 72         return NULL;
 73     }
 74     else
 75     {
 76         A = (BTNode*)calloc(1, sizeof(BTNode));
 77         A->data = ch;
 78         A->Lchild = CreateBinaryTree();
 79         A->Rchild = CreateBinaryTree();
 80         return A;
 81     }
 82 }
 83 
 84 void PrintLeafNode(BTNode* A)
 85 {/*打印二叉树的叶子结点*/
 86     if (A == NULL)
 87     {
 88         return;
 89     }
 90     else if ((!A->Lchild) && (!A->Rchild))
 91     {
 92         printf("%c", A->data);
 93         return;
 94     }
 95     else
 96     {
 97         PrintLeafNode(A->Lchild);
 98         PrintLeafNode(A->Rchild);
 99     }
100 }
101 
102 int Like(BTNode* A, BTNode* B)
103 {/*二叉树相似性判定*/
104     int Like1 = 0;
105     int Like2 = 0;
106     if (A == NULL && B == NULL)
107     {
108         return 1;
109     }
110     else if (A == NULL || B == NULL)
111     {
112         return 0;
113     }
114     else
115     {
116         Like1 = Like(A->Lchild, B->Lchild);
117         Like2 = Like(A->Rchild, B->Rchild);
118         return Like1 && Like2;
119     }
120 }
121 
122 int DepthTree(BTNode* A)
123 {/*求二叉树高度*/
124     int Depth = 0;
125     int DepthLeft = 0;
126     int DepthRight = 0;
127     if (A)
128     {
129         DepthLeft = DepthTree(A->Lchild);
130         DepthRight = DepthTree(A->Rchild);
131         Depth = 1 + (DepthLeft > DepthRight ? DepthLeft : DepthRight);
132     }
133     return Depth;
134 }
135 
136 int CountNode(BTNode* A)
137 {/*统计二叉树的结点数*/
138     int sum = 0;
139     if (A)
140     {
141         sum++;
142         sum += CountNode(A->Lchild);
143         sum += CountNode(A->Rchild);
144     }
145     return sum;
146 }
147 
148 int CountLeafNode(BTNode* A)
149 {/*统计叶子结点数目*/
150     int sum = 0;
151     if (A)
152     {
153         if (!A->Lchild && !A->Rchild)
154         {
155             sum++;
156         }
157         sum += CountLeafNode(A->Lchild);
158         sum += CountLeafNode(A->Rchild);
159     }
160     return sum;
161 }
162 
163 char Parent(BTNode* A, char ChildNode)
164 {/*求结点的双亲*/
165     char ParentNode = '\0';
166     if (A == NULL)
167     {
168         return '\0';
169     }
170     else if (A->Lchild && A->Lchild->data == ChildNode)
171     {
172         return A->data;
173     }
174     else if (A->Rchild && A->Rchild->data == ChildNode)
175     {
176         return A->data;
177     }
178     else
179     {
180         ParentNode = Parent(A->Lchild, ChildNode);
181         if (ParentNode != '\0')
182         {
183             return ParentNode;
184         }
185         else
186         {/*递归在右子树中找*/
187             return Parent(A->Rchild, ChildNode);
188         }
189     }
190 }

这篇关于二叉树遍历算法的应用的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！