二叉树创建、遍历、求深度--C语言实现
#include <stdio.h> #include <stdlib.h> #include <malloc.h> typedef int ElemType; //数据类型 typedef int Status; //返回值类型 //定义二叉树结构 typedef struct BiTNode{ ElemType data; //数据域 struct BiTNode*lChild, *rChlid; //左右子树域 }BiTNode, *BiTree; //先序创建二叉树 Status CreateBiTree(BiTree *T) { ElemType ch; ElemType temp; scanf("%d", &ch); temp = getchar(); if (-1 == ch) *T = NULL; else { *T = (BiTree)malloc(sizeof(BiTNode)); if (!(*T)) exit(-1); (*T)->data = ch; printf("输入%d的左子节点:", ch); CreateBiTree(&(*T)->lChild); printf("输入%d的右子节点:", ch); CreateBiTree(&(*T)->rChlid); } return 1; } //先序遍历二叉树 void TraverseBiTree(BiTree T) { if (NULL == T) return ; printf("%d ", T->data); TraverseBiTree(T->lChild); TraverseBiTree(T->rChlid); } //中序遍历二叉树 void InOrderBiTree(BiTree T) { if (NULL == T) return ; InOrderBiTree(T->lChild); printf("%d ", T->data); InOrderBiTree(T->rChlid); } //后序遍历二叉树 void PostOrderBiTree(BiTree T) { if (NULL == T) return ; PostOrderBiTree(T->lChild); PostOrderBiTree(T->rChlid); printf("%d ", T->data); } //二叉树的深度 int TreeDeep(BiTree T) { int deep = 0; if(T) { int leftdeep = TreeDeep(T->lChild); int rightdeep = TreeDeep(T->rChlid); deep = leftdeep>=rightdeep?leftdeep+1:rightdeep+1; } return deep; } //主函数 int main(void) { BiTree T; BiTree *p = (BiTree*)malloc(sizeof(BiTree)); int deepth; printf("请输入第一个结点的值,-1表示没有叶结点:\n"); CreateBiTree(&T); printf("先序遍历二叉树:\n"); TraverseBiTree(T); printf("\n"); printf("中序遍历二叉树:\n"); InOrderBiTree(T); printf("\n"); printf("后序遍历二叉树:\n"); PostOrderBiTree(T); printf("\n"); deepth=TreeDeep(T); printf("树的深度为:%d",deepth); printf("\n"); return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。