The purpose of this paper is to consolidate my basic knowledge in data structure and C language and improve my basic skills in code writing. The codes in this paper refer to the demonstration codes in THE MOOC data structure of Zhejiang University and the demonstration codes in The “Big Talk Data Structure”. Since there is no result display during operation and I find that I do not fully understand the POINTER of C language, I refer to the codes of other two bloggers. Thank you very much to Professor He Qinming of ZHEJIANG University and the two bloggers. One is EarthChen and the other is Men_wen

I. Introduction to the operating environment

  • Editor: VSCode + MicroSoft native plug-in;
  • Operating environment: MinGW;
  • GCC mian. C -o mian. Exe

The definition of binary tree

Here we directly use the code in the data structure course of Zhejiang University. Because this writing method is clear and easy to expand.

typedef char ElementType;

typedef struct TNode *Position; /* Struct pointer */
typedef Position BinTree; /* Binary tree type */
struct TNode{ /* Tree node definition */
    ElementType Data; /* Node data */
    BinTree Left;     /* denotes the left subtree */
    BinTree Right;    /* points to the right subtree */
}TNode;
Copy the code

How to create a binary tree?

Look at the code and analyze it later

void CreateBinaryTree ( BinTree *T ) {
    ElementType ch;
    scanf("%c",&ch);

    if (ch == The '#')
        *T = NULL;
    else {
        *T = (BinTree)malloc(sizeof(TNode)); (*T)->Data = ch; CreateBinaryTree(&((*T)->Left)); CreateBinaryTree(&((*T)->Right)); }}Copy the code

We know that the type of the binary tree is defined as BinTree, and its original type is a pointer to the node TNode of the binary tree. The mistake I made initially was that I thought I could just pass in the pointer to BinTree here to CreateBinaryTree() and get the binary tree that I created. In fact, we need to pass in the pointer to the pointer, the address of the structure pointer *BinTree. In other words, we actually pass in a TNode, which is a pointer to a node pointer. Using the above definition is equivalent to a dimensionality reduction process, so we can write one less *. Why pass a pointer to a node pointer? My understanding is that we use the data structure of binary tree is depends on the pointer in the basic operation, this is equivalent to we start in the manipulation of the pointer (such as do not change the binary tree of some operations – the first sequence in sequence after sequence traversal, we use the pointer), but the pointer is included in the binary tree of this type, for instance, Equivalent to a normal type that doesn’t get its address. So when we need to modify the binary tree, we need to consider the address of the so-called “normal” type, which is the address of the pointer, so we will pass in the pointer to the node pointer in CreateBinaryTree(), which is ** TNode, also known as *Bintree. The binary tree set up here is actually an extended binary tree. The values of nodes (char type) are entered in the order of first traversal, with ‘#’ representing null nodes. For example, create A binary tree. The first layer is A, the second layer is B and C, and the third layer is D and F. D is the left child of B, and F is the right child of C. We need to type ABD###C#F##;

Four, binary tree traversal – recursive implementation

The three recursive implementations differ only in the order of the output statements. The implementation principle is that the path of nodes is the same in the middle-before-back-order traversal of the binary tree, but the timing of accessing each node is different. Each node is passed through three times, and the first time printf is preordered, the second printf is middle-order, and the third time is post-order. 1. Traversal in sequence

void PreOrderTraversal ( BinTree BT ) {
    if ( BT ) {
        printf("%c", BT->Data); PreOrderTraversal( BT->Left ); PreOrderTraversal( BT->Right ); }}Copy the code

2. Middle order traversal

void InOrderTraversal ( BinTree BT ) {
    if ( BT ) {
        PreOrderTraversal( BT->Left );
        printf("%c", BT->Data); PreOrderTraversal( BT->Right ); }}Copy the code

3. Back-order traversal

void PostOrderTraversal ( BinTree BT ) {
    if ( BT ) {
        PostOrderTraversal( BT->Left );
        PostOrderTraversal( BT->Right );
        printf("%c", BT->Data); }}Copy the code

Other operations

1. Sequence traversal of output binary tree leaf nodes

void PreOrderPrintLeaves ( BinTree BT ) {
    if ( BT ) {
        if(! BT->Left && ! BT->Right )printf("%c", BT->Data); PreOrderPrintLeaves( BT->Left ); PreOrderPrintLeaves( BT->Right ); }}Copy the code

2. Obtain the height of the binary tree by sequential traversal

int PostOrderGetHeight ( BinTree BT) {
    int HL, HR, MaxH;

    if ( BT ) {
        HL = PostOrderGetHeight( BT->Left );
        HR = PostOrderGetHeight( BT->Right );
        MaxH = ( HL > HR ) ? HL : HR;
        return (MaxH + 1);
    }
    else
        return 0;
}
Copy the code

Six, test,

Program structure: the header file is btree.h, which contains the above code. The main program file is main.c, which contains the following codes:

#include<stdio.h>
#include<stdlib.h>
#include"BTree.h"

int main(a) {
  BinTree myTree;
  printf("Create your Binary Tree:\n");
  CreateBinaryTree(&myTree);
  printf("\n PreOrder:");
  PreOrderTraversal(myTree);
  printf("\n InOrder:");
  InOrderTraversal(myTree);
  printf("\n PostOrder:");
  PostOrderTraversal(myTree);
  printf("\n Leaves:");
  PreOrderPrintLeaves(myTree);
  printf("\n");
  int high = PostOrderGetHeight(myTree);
  printf("The height of the tree: %4d", high);
  return 0;
}
Copy the code

The test results are as follows:

Seven, conclusion

This paper solved about binary tree I create confusion, before writing the list should also is the problem, just didn’t think deeply, using the CPP reference flocking, today a little thought for a moment, may also have a wrong place, but because you also need to review the other content, so I write this for a moment. Recursive traversal and closure tests are written just to make it easier for the reader to run the code quickly. The non-recursive implementation of binary tree traversal may be updated later. Thanks for reading!