链式二叉树

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 1024
#define NAME_SIZE 255
//数据元素
typedef struct{
    int id;
    char name[NAME_SIZE];
}ElementType;

#include "ElementType.h"

//树结点
typedef struct treeNode{
    ElementType data;//树结点的数据域
    struct treeNode *left;//左子树
    struct treeNode *right;//右子树
}TreeNode;

#include "TreeNode.h"

//二叉链表
typedef struct{
TreeNode *root;//二叉树的根结点
int length;//结点总数
int depth;//二叉链表深度
int diameter;//直径-从叶结点到叶结点的最长路径
}BinaryTree;

//初始化空二叉树
void InitBinaryTree(BinaryTree * tree);

//创建二叉树，外部需要事先对结点分配内存
//返回值为0时表示不创建(创建失败)
int CreateBinaryTree(TreeNode *root);

//前序遍历,也叫先根遍历、先序遍历、前序周游，可以记作：根-左-右
void PreOrderTraverse(TreeNode *node);

#include "BinaryTree.h"
#include <iostream>

//用来实现结点id的自增长
static int id=0;

//初始化空二叉树
void InitBinaryTree(BinaryTree * tree){
tree->root=NULL;
tree->depth=0;
tree->diameter=0;
tree->length=0;
}


//创建二叉树，外部需要事先对结点分配内存
int CreateBinaryTree(TreeNode *root){
    //根结点如果为空，就退出创建过程
    if(!root) return 0;
    char inputName[NAME_SIZE];//用户输入的结点名
    gets_s(inputName);
    //用户输入回车表示结束当前子树的创建
    if(strcmp(inputName,"\0")==0) return 0;
    //创建当前结点
    root->data.id=++id;
    strcpy(root->data.name,inputName);

    //为输入左右结点做准备，为左右结点指针分配内存
    root->left=(TreeNode *)malloc(sizeof(TreeNode));
    root->right=(TreeNode *)malloc(sizeof(TreeNode));
    //分别递归创造左子树和右子树
    printf("左结点：");
    if(CreateBinaryTree(root->left)==0){
    //不再创建这个结点则销毁结点刚分配的内存
        free(root->left);
        root->left=NULL;
    }
    printf("右结点：");
    if(CreateBinaryTree(root->right)==0){
    //不再创建这个结点则销毁结点刚分配的内存
        free(root->right);
        root->right=NULL;
    }

}

//前序遍历
void PreOrderTraverse(TreeNode *node){
    //先访问根结点，然后遍历左子树，最后遍历右子树
    if(node){
        printf("[%d,%s]-",node->data.id,node->data.name);
        PreOrderTraverse(node->left);
        PreOrderTraverse(node->right);
    }
}

#include <iostream>
using namespace std;
#include "BinaryTree.h"

void TestBinaryTree();

int main(){
    TestBinaryTree();

    return 0;

}

void TestBinaryTree(){
BinaryTree tree;
InitBinaryTree(&tree);
//容易遗漏的点：根结点需要事先分配内存
tree.root=(TreeNode *)malloc(sizeof(TreeNode));
cout<<"请输入根结点"<<endl;
CreateBinaryTree(tree.root);

printf("\n\n前序遍历结果：\n");
PreOrderTraverse(tree.root);

free(tree.root);
}