C语言演示二叉树算法

Question

如题所述

Answer 1

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i − 1个结点;深度为k的二叉树至多有2k − 1个结点;对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。二叉树算法常被用于实现二叉查找树和二叉堆。

首先打开VC++6.0

选择文件，新建

选择C++ source file 新建一个空白文档

首先声明头文件

定义树的结点结构 typedef struct TreeNode{ char data;/*树中结点的数据是一个字符*/ struct TreeNode *lchild; struct TreeNode *rchild; }TREENODE;

声明变量 int NodeNum = 0;/*统计数的结点数*/ int LeafNum = 0;/*统计数的叶子结点数*/ char ch[] = {'a', 'b', 'c', ' ', ' ', 'd', ' ', ' ', 'e', 'f', ' ', ' ', 'g', ' ', ' '}; int inc = 0;

用函数建立一个二叉树 int CreateBiTree(TREENODE **T) /*按先序次序输入二叉树中结点的值,以空字符表示空树*/ { char i; if(ch[inc++]==' ') *T = NULL; else { printf("%c\n",ch[inc-1]); if(!(*T = (TREENODE *)malloc(sizeof(TREENODE)))) return -1; (*T)-data = ch[inc-1]; printf("%c\n",(*T)-data); CreateBiTree(((*T)-lchild)); CreateBiTree(((*T)-rchild)); } return 1; }

先序遍历二叉树 int PreOderTraverse(TREENODE *T) { if(T) { printf("%c ",T-data); PreOderTraverse(T-lchild); PreOderTraverse(T-rchild); } return 1; }

中序遍历二叉树 int InOderTraverse(TREENODE *T) { if(T) { InOderTraverse(T-lchild); printf("%c ",T-data); InOderTraverse(T-rchild); } return 1; }

后序遍历二叉树 int BackOderTraverse(TREENODE *T) { if(T) { BackOderTraverse(T-lchild); BackOderTraverse(T-rchild); printf("%c ",T-data); } return 1; }

利用先序遍历来计算树中的结点数 void CountNodeNum(TREENODE *T) { if(T) { NodeNum ++; CountNodeNum(T-lchild); CountNodeNum(T-rchild); } }

利用先序遍历计算叶子节点数 void CountLeafNum(TREENODE *T) { if(T) { if((!(T-lchild))(!(T-rchild))) LeafNum ++; CountLeafNum(T-lchild); CountLeafNum(T-rchild); } }

主函数 int main() { TREENODE *T; int i; CreateBiTree(T); do { puts("**************************************************"); puts("*          you can choose:       *"); puts("* 1: Traverse the Binary tree by pre order   *"); puts("* 2: Traverse the Binary tree by mid order   *"); puts("* 3: Traverse the Binary tree by back order  *"); puts("* 4: Count the node num of the Binary tree   *"); puts("* 5: Count the leaf node num of the Binary tree*"); puts("**************************************************"); puts("please input your choice:"); scanf("%d",i); switch(i) { case 1: printf("The preoder is:\n"); PreOderTraverse(T); printf("\n"); break; case 2: printf("The midoder is:\n"); InOderTraverse(T); printf("\n"); break; case 3: printf("The backoder is:\n"); BackOderTraverse(T); printf("\n"); break; case 4: CountNodeNum(T); printf("The nodenum of the tree is:%d\n",NodeNum); break; case 5: CountLeafNum(T); printf("The leafnum of the tree is:%d\n",LeafNum); break; } printf("please input any char to go on\n"); getch(); }while((i=1)(i6)); getch(); return 1; }

运行结果