8606 construction and traversal of binary tree [just hand]
Description
Construct a binary tree represented by a binary list: input the value of the node in the binary tree (one character) in the order of precedence; '#' character represents an empty tree, and construct a binary tree T represented by a binary list; Then output three traversal sequences. This question only gives part of the code, please complete the content.
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;//Left and right child pointers
} BiTNode,*BiTree;
Status CreateBiTree(BiTree &T) { // Algorithm 6.4
// Enter the value (one character) of the node in the binary tree in the order of precedence. The '#' character represents the empty tree,
// Construct a binary tree T represented by a binary linked list.
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
________________________ // Generate root node
_______________________ // Construct left subtree
_________________________ // Construct right subtree
}
return OK;
} // CreateBiTree
Status PreOrderTraverse( BiTree T) {
// Recursive algorithm for preorder traversal of binary tree T
//Complete the code, and multiple statements can be used
} // PreOrderTraverse
Status InOrderTraverse( BiTree T) {
// Recursive algorithm for traversing binary tree T in middle order
//Complete the code, and multiple statements can be used
} // InOrderTraverse
Status PostOrderTraverse( BiTree T) {
// Recursive algorithm for post order traversal of binary tree T
//Complete the code, and multiple statements can be used
} // PostOrderTraverse
int main() //Main function
{
//Supplementary code
}//main
Input format
The first line: enter the pre order traversal sequence of a binary tree
Output format
The first line: the preorder traversal sequence of the binary tree
Line 2: middle order traversal sequence of binary tree
Line 3: post order traversal sequence of binary tree
sample input
AB##C##
sample output
ABC
BAC
BCA
code implementation
#include "stdio.h"
#include "malloc.h"
#include <iostream>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char ElemType;
typedef struct BiTNode {
ElemType data;
struct BiTNode *lchild, *rchild;//Left and right child pointers
} BiTNode, *BiTree;
Status CreateBiTree(BiTree &T) { // Algorithm 6.4
// Enter the value (one character) of the node in the binary tree in the order of precedence. The '#' character represents the empty tree,
// Construct a binary tree T represented by a binary linked list.
char ch;
scanf("%c", &ch);
if (ch == '#') T = NULL;
else {
if (!(T = (BiTNode *) malloc(sizeof(BiTNode)))) return ERROR;
T->data = ch; // Generate root node
CreateBiTree(T->lchild); // Construct left subtree
CreateBiTree(T->rchild); // Construct right subtree
}
return OK;
} // CreateBiTree
Status PreOrderTraverse(BiTree T) {
// Recursive algorithm for preorder traversal of binary tree T
//Complete the code, and multiple statements can be used
if (T == NULL)return ERROR;
cout << T->data;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
} // PreOrderTraverse
Status InOrderTraverse(BiTree T) {
// Recursive algorithm for traversing binary tree T in middle order
//Complete the code, and multiple statements can be used
if (!T)return ERROR;
InOrderTraverse(T->lchild);
cout << T->data;
InOrderTraverse(T->rchild);
} // InOrderTraverse
Status PostOrderTraverse(BiTree T) {
// Recursive algorithm for post order traversal of binary tree T
//Complete the code, and multiple statements can be used
if (!T)return ERROR;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout << T->data;
} // PostOrderTraverse
int main() //Main function
{
//Supplementary code
BiTree P;
CreateBiTree(P);
PreOrderTraverse(P);cout<<endl;
InOrderTraverse(P);cout<<endl;
PostOrderTraverse(P);cout<<endl;
}//main
17121 find the number of various nodes of binary tree [back relationship]
Description
Construct a binary tree represented by a binary list: input the value (one character) of the nodes in the binary tree in the order of precedence, the '#' character represents the empty tree, construct the binary tree T represented by the binary list, and calculate the total number of nodes with moderate degree of 2, the total number of nodes with degree of 1, and the total number of nodes with degree of 0
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;//Left and right child pointers
} BiTNode,*BiTree;
Status CreateBiTree(BiTree &T) { // Algorithm 6.4
// Enter the value (one character) of the node in the binary tree in the order of precedence. The '#' character represents the empty tree,
// Construct a binary tree T represented by a binary linked list.
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
________________________ // Generate root node
_______________________ // Construct left subtree
_________________________ // Construct right subtree
}
return OK;
} // CreateBiTree
int main() //Main function
{
//Supplementary code
}//main
Input format
In the first row, enter the nodes in the binary tree in the order of precedence
Output format
Number of nodes with output degree of 2 in the first row
The second row outputs the number of nodes with degree 1
The third row outputs the number of nodes with degree 0
sample input
ABC###D##
sample output
1
1
2
code implementation
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;//Left and right child pointers
} BiTNode,*BiTree;
int n0=0,n=0;
Status CreateBiTree(BiTree &T) { // Algorithm 6.4
// Enter the value (one character) of the node in the binary tree in the order of precedence. The '#' character represents the empty tree,
// Construct a binary tree T represented by a binary linked list.
char ch;
scanf("%c",&ch);
if (ch=='#') T = NULL;
else {
if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
T->data=ch; // Generate root node
n++;
CreateBiTree(T->lchild);// Construct left subtree
CreateBiTree(T->rchild); // Construct right subtree
}
return OK;
} // CreateBiTree
void f(BiTree &T){
if(!T)return;
if(!T->lchild&&!T->rchild)n0++;
f(T->lchild);
f(T->rchild);
}
int main() //Main function
{
//Supplementary code
BiTree T;
CreateBiTree(T);
f(T);
printf("%d\n%d\n%d\n",n0-1,n-2*n0+1,n0);
//n0 is the number of leaf nodes
//Leaf nodes = degree 2 nodes + 1
//All node trees - leaf node trees - degree 2 nodes = degree 1 nodes
}//main
18924 width of binary tree [can be lazy]
Description
The width of a binary tree refers to the number of nodes in the layer with the largest number of nodes.
1
/
2 3
/
4
The answer is 2. There are 2 nodes in the second layer.
Input format
n lines in total.
The first line is an integer n, which indicates that there are n nodes, numbered from 1 to N, and node 1 is the root of the tree. (1<=n<=50)
From the second row to the nth row, each row has two integers x and y, indicating that x is the parent node of Y in the binary tree. When x first appears, y is the left child
Output format
The width of the output binary tree.
sample input
5
1 2
1 3
2 4
2 5
sample output
2
Code implementation [two-dimensional array lazy method]
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<vector<int>> array(50);
array[0].push_back(1);
int n;
cin >> n;
for(int i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
for(int j=0;j<50;j++){
if(array[j].back()>=x){
array[j+1].push_back(y);
break;
}
}
}
int max=0;
for(int i=0;i<50;i++){
if(max<array[i].size())max=array[i].size();
}
cout << max<<endl;
return 0;
}
18724 traversal operation of binary tree [worth seeing ★]
Description
The three traversals of binary tree can be realized recursively.
If we know the preorder and middle order sequences of a binary tree, we can use the recursive method to find the postorder traversal sequence.
Input format
Two lines, the first line is a string, which indicates the pre order traversal of the tree, and the second line is a string, which indicates the medium order traversal of the tree. All nodes of the tree are represented by lowercase letters.
Output format
A string, the sequence after the tree.
sample input
abcde
bcade
sample output
cbeda
code implementation
#include <iostream>
#include <cstring>
using namespace std;
char pre[1000],mid[1000],res[1000];
void cut(char pre[],char mid[],int len,int loc){
if(len<=0)return;
int i=0;
while(pre[0]!=mid[i])i++;//Find the root node in the order
cut(pre+1,mid,i,loc-(len-i-1)-1);//loc - length of the right subtree - 1 = the position of the root node of the left subtree, that is, the character to the left of the root node
cut(pre+i+1,mid+i+1,len-i-1, loc - 1);//loc - 1 = the location of the root node of the right subtree, that is
res[loc]=pre[0];//loc is the position of the root node in the subsequent sequence
}
int main() {
cin>>pre>>mid;
int len=strlen(mid);
cut(pre,mid,len,len-1);
cout<<res<<endl;
return 0;
}
18923 diameter of binary tree
Description
Given a binary tree, you need to calculate its diameter and length. The diameter length of a binary tree is the maximum of any two node path lengths. This path may or may not pass through the root node.
1
/
2 3
/ \
4 5
The answer is 3, and its length is path [4,2,1,3] or [5,2,1,3].
Input format
n lines in total.
The first line is an integer n, which indicates that there are n nodes, numbered from 1 to n.
From the second row to the nth row, each row has two integers x and y, indicating that x is the parent node of Y in the binary tree. When x first appears, y is the left child
Output format
The diameter of the output binary tree.
sample input
5
1 2
1 3
2 4
2 5
sample output
3
code implementation
#include "stdio.h"
#include "malloc.h"
#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct BiTNode {
ElemType data;
struct BiTNode *lchild, *rchild;//Left and right child pointers
} BiTNode, *BiTree;
//Insert data under the specified tree
void insertData(BiTree &T, ElemType data) {
BiTree P = new BiTNode;//P is a new subtree pointer
P->data = data;
P->lchild = NULL;
P->rchild = NULL;
if (T == NULL) {
T = P;
}
//First left then right
else {
if (T->lchild == NULL) {
T->lchild = P;
} else {
T->rchild = P;
}
}
}
//Find parent element first
void preOrderSearch(BiTree T, ElemType x, BiTree &result) {
if (T) {
//cout <<"CMP "<< T->data <<" AND "<<x<<endl;
if (T->data == x){
result = T;
}
preOrderSearch(T->lchild, x, result);
preOrderSearch(T->rchild, x, result);
}
} // PreOrder
//Recursive maximum depth
int maxDiameter = 0;
int MaxDepth(BiTree &T) {
if (T == NULL) return 0;
int leftDepth = MaxDepth(T->lchild);
int rightDepth = MaxDepth(T->rchild);
int diameter = leftDepth + rightDepth;
maxDiameter = diameter > maxDiameter ? diameter : maxDiameter;
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
int main() //Main function
{
BiTree P = NULL;
int n;
cin >> n;
n--;
insertData(P, 1);//First node, manual insertion (to be optimized)
// PreOrderShow(P);
while (n--) {
ElemType f, z;
cin >> f >> z;
BiTree res = NULL;
preOrderSearch(P, f, res);//Find subtree to insert
insertData(res, z);
//PreOrderShow(res);
}
MaxDepth(P);
cout << maxDiameter;
}//main
8609 Huffman tree [worth seeing ★★★]
Description
The Huffman tree is established by using the static linked list. In the process of building the tree, the weight of the left subtree is required to be less than that of the right subtree, and the code of each node is obtained. Requirement: the number n and node value of leaf nodes are entered by keyboard. This question gives the program code and requires modification to meet the test requirements
#include "stdio.h"
#include "malloc.h"
#include "string.h"
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void Select(HuffmanTree &HT, int n, int &s1, int &s2)
//In HT[1..n], select the two nodes with parent 0 and minimum weight,
// The serial numbers are s1 and s2 respectively.
{
int i;
s1=-1;s2=-1;
for (i=1;i<=n;i++) {
if (HT[i].parent==0)
if (s1==-1) s1=i;
else
if (s2==-1 )
if (HT[i].weight0)，Constructing Huffman tree HT，
// The Huffman code HC of n characters is obtained
int i, j, m, s1, s2, start;
char *cd;
unsigned int c, f;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // Unit 0 is not used
for (i=1; i<=n; i++) { //initialization
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //initialization
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
printf("\n The construction process of Huffman tree is as follows:\n");
printf("HT Initial state:\n node weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" Press any key to continue ...");
getch();
for (i=n+1; i<=m; i++) { // Build Huffman tree
// In HT[1..i-1], select the two nodes with parent 0 and minimum weight,
// The serial numbers are s1 and s2 respectively.
Select(HT, i-1, s1, s2);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" node weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" Press any key to continue ...");
getch();
}
//---Reverse the Huffman code of each character from leaf to root---
cd = (char *)malloc(n*sizeof(char)); // Assign a workspace for encoding
cd[n-1] = '\0'; // Code terminator.
for (i=1; i<=n; ++i) { // Huffman coding character by character
start = n-1; // Code terminator position
for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent)
// Reverse coding from leaf to root
if (HT[f].lchild==c) cd[--start] = '0';
else cd[--start] = '1';
HC[i] = (char *)malloc((n-start)*sizeof(char));
// Allocate space for the ith character encoding
strcpy(HC[i], &cd[start]); // Copy code (string) from cd to HC
}
free(cd); //Free workspace
} //HuffmanCoding
void main()
{
int i,n;
int *w;
HuffmanTree HT;
HuffmanCode HC;
printf("Node Number:");
scanf("%d",&n); //Number of weights
w=(int *)malloc(n*sizeof(int));
printf("Input weights:");
for ( i=0;i<n;i++) //Input weight
scanf("%d",&w[i]);
HC=(char **)malloc((n+1)*sizeof(char*)); //0 space not used
HT=(HuffmanTree)malloc((2*n+1+1)*sizeof(HTNode));//0 space not used
HuffmanCoding(HT, HC, w, n);
printf("\n");
for (i = 1; i<n+1; i++){
puts(HC[i]); //Output Huffman coding
free(HC[i]); //Free up space
}
free(HC);
free(HT);
}//main
Input format
Line 1: number of weights
The second line: enter n weights, separated by spaces
Output format
Output n rows
Each line represents the Huffman code corresponding to each weight
sample input
8
5 29 7 8 14 23 3 11
sample output
0001
10
1110
1111
110
01
0000
001
code implementation
#include "stdio.h"
#include "malloc.h"
#include "string.h"
#include <iostream>
using namespace std;
typedef struct {
unsigned int weight;
unsigned int parent, lchild, rchild;
} HTNode, *HuffmanTree;
void Select(HuffmanTree &HT, int n, int &s1, int &s2)
//In HT[1..n], select the two nodes with parent 0 and minimum weight,
// The serial numbers are s1 and s2 respectively.
{
s1 = 0;//Unit 0 is not used
s2 = 0;
//Find the first one
for (int i = 1; i <= n; i++) {
if (HT[i].parent == 0) {
if (s1 == 0) s1 = i;//Assume that the current node is the smallest (initial)
else if (HT[i].weight < HT[s1].weight)s1 = i;
}
}
for (int i = 1; i <= n; i++) {
//Skip s1 and find s2. If s2 is not found, it will be = 0
if (HT[i].parent == 0&& i != s1) {
if (s2 == 0)s2 = i;//Assume that the current node is the smallest (initial)
if (HT[i].weight < HT[s2].weight )s2 = i;
}
}
}
void createHuffmanTree(HuffmanTree &HT, int n) {
if (n <= 1) return;
int m = 2 * n - 1;//Push the number of nodes of the tree from the number of weight nodes
HT = new HTNode[m + 1]; // Unit 0 is not used, the actual size needs to be + 1
for (int i = 0; i <= m; i++) { //Initialize all nodes
HT[i].weight = 0;
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
for (int i = 1; i <= n; i++) { //Input weight node (subscript 1 to n)
cin >> HT[i].weight;
}
for (int i = n + 1; i <= m; i++) { // The tree to be synthesized is placed in i and keeps retreating
int s1, s2;
Select(HT, i - 1, s1, s2);//In front of the new tree (i), select the two with the smallest weight
//New tree generation
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
typedef char **HuffmanCode;
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int n) {
HC = new char*[n + 1];//The secondary pointer stores the code of each node
char *tmp = new char[n];//Temporary storage (fixed length) of codes derived from each node's Backstepping
tmp[n - 1] = '\0';// Code Terminator
for (int i = 1; i <= n; i++) {// Huffman code is calculated node by node. All nodes 1-n here are initial nodes
int start = n - 1;// Code terminator position (for backward push)
//Keep going back
int child = i, par = HT[i].parent;//Child node, parent node, subscript
while(par != 0){
if (HT[par].lchild == child) tmp[--start] = '0';//On the left of parents
else tmp[--start] = '1';//On the right of parents
child = par;
par = HT[par].parent;
}
HC[i] = new char[n-start];// Allocate space for the ith character coding and realize variable length coding
strcpy(HC[i], &tmp[start]); //shorten
}
delete tmp; //Free workspace
} //HuffmanCoding
int main() {
int i, n;
HuffmanTree HT;
HuffmanCode HC;
cin>>n; //Number of weights
//Create Huffman tree
createHuffmanTree(HT, n);
//Get encoding
HuffmanCoding(HT, HC, n);
//Output Huffman coding
for (i = 1; i < n + 1; i++)cout <<HC[i]<<endl;
//release
delete HC;
delete HT;
}//main