C语言演示二叉树算法
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i − 1个结点;深度为k的二叉树至多有2k − 1个结点;对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。二叉树算法常被用于实现二叉查找树和二叉堆。
操作方法
- 01
首先打开VC++6.0
- 02
选择文件，新建
- 03
选择C++ source file 新建一个空白文档
- 04
首先声明头文件
- 05
定义树的结点结构 typedef struct TreeNode{ char data;/*树中结点的数据是一个字符*/ struct TreeNode *lchild; struct TreeNode *rchild; }TREENODE;
- 06
声明变量 int NodeNum = 0;/*统计数的结点数*/ int LeafNum = 0;/*统计数的叶子结点数*/ char ch[] = {'a', 'b', 'c', ' ', ' ', 'd', ' ', ' ', 'e', 'f', ' ', ' ', 'g', ' ', ' '}; int inc = 0;
- 07
用函数建立一个二叉树 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; }
- 08
先序遍历二叉树 int PreOderTraverse(TREENODE *T) { if(T) { printf("%c ",T->data); PreOderTraverse(T->lchild); PreOderTraverse(T->rchild); } return 1; }
- 09
中序遍历二叉树 int InOderTraverse(TREENODE *T) { if(T) { InOderTraverse(T->lchild); printf("%c ",T->data); InOderTraverse(T->rchild); } return 1; }
- 10
后序遍历二叉树 int BackOderTraverse(TREENODE *T) { if(T) { BackOderTraverse(T->lchild); BackOderTraverse(T->rchild); printf("%c ",T->data); } return 1; }
- 11
利用先序遍历来计算树中的结点数 void CountNodeNum(TREENODE *T) { if(T) { NodeNum ++; CountNodeNum(T->lchild); CountNodeNum(T->rchild); } }
- 12
利用先序遍历计算叶子节点数 void CountLeafNum(TREENODE *T) { if(T) { if((!(T->lchild))&&(!(T->rchild))) LeafNum ++; CountLeafNum(T->lchild); CountLeafNum(T->rchild); } }
- 13
主函数 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)&&(i<6)); getch(); return 1; }
- 14
运行结果
