Java源码集合类TreeMap学习1——数据结构3二叉树创建代码

野性酷女 2022-06-17 09:13 142阅读 0赞

**二叉树的二叉链表存储结构**

二叉树的二叉链表存储结构，一个结点结构包含三个域：数据域、左、右指针域。如下图所示。

![Center][]

二叉树的遍历知识参考：http://blog.csdn.net/fansongy/article/details/6798278/

二叉树的二叉链表存储表示的代码如下。

//Tree.cpp
    #include<stdio.h>
    #include<malloc.h>
    
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -1
    
    typedef int Status;
    typedef char TElemType;
    
    typedef struct BiTNode{
    	TElemType data;//数据域
    	struct BiTNode *lchild, *rchild;//左右孩子指针
    }BiTNode, *BiTree;
    
    //按先序次序输入二叉树中结点的值(一个字符),#字符表示空树
    Status CreateBiTree(BiTree &T);
    
    //先序遍历二叉树的各个结点
    Status PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e));
    
    Status Visit(TElemType e);
    
    Status CreateBiTree(BiTree &T)
    {
    	char ch;
    	scanf("%c", &ch);
    	
    	if(ch=='#')
    	{
    		T = NULL;
    	}
    	else{
    		if(!(T = (BiTNode *)malloc(sizeof(BiTNode)))){
    			return OVERFLOW;
    		}
    
    		T->data = ch;
    		CreateBiTree(T->lchild);
    		CreateBiTree(T->rchild);
    	}
    
    	return OK;
    }
    
    Status PreOrderTraverse  (BiTree T, Status (* Visit)(TElemType e))  
    {  
        if (T)  
    	{  
    		Visit(T->data);  
    		PreOrderTraverse(T->lchild, Visit);  
    		PreOrderTraverse(T->rchild, Visit);  
    	}  
    	return OK;  
    }  
    
    Status Visit(TElemType e)
    {
    	printf("%c\n", e);
    	return OK;
    }
    
    int main()
    {
    	BiTree T;
    	CreateBiTree(T);
    	//PreOrder
    	printf("PreOrder is\n");
    	PreOrderTraverse(T, Visit);
    	return 0;
    }

**注意：以上代码是在Centos7 64位操作系统上用g++编译器编译通过并且运行无误( 编译指令： g++  Tree.cpp  -o  Tree)。**

**例如一次输入: -+a\#\#\*b\#\#-c\#\#d\#\#/e\#\#f\#\#，程序功能正确的遍历打印出来，说明此处连续的两个\#\#字符表示结点没有子结点(如：a、b、c、e、f结点都是没有子结点的)。**

**注意输入不要输入一个字符就按回车键，因为回车键也会当作一个输入的字符。**

[Center]: /images/20220617/d3ca4523db2e47a5afc5d6810e102566.png