BinTree.h
#ifndef _BINTREE_H_ #pragma once #include<stdio.h> #include<assert.h> #include<malloc.h> #include<windows.h> typedef int BTDataType; //typedef struct TreeNode //{ // BTDataType _data; // struct TreeNode* _firstChild; // struct TreeNode* _nextBrother; //}TreeNode; typedef struct BinaryTreeNode { struct BinaryTreeNode* _left; struct BinaryTreeNode* _right; BTDataType _data; }BTNode; #include "Queue.h" //#include "Stack.h" BTNode* BuyBTNode(BTDataType x) ; // 创建二叉树 BTNode* CreateBTree(BTDataType* a, size_t* pIndex, BTDataType invalid) ; void BTreePrevOrder(BTNode* root) ; void BTreeInOrder(BTNode* root) ; void BTreePostOrder(BTNode* root) ; size_t BTreeSize(BTNode* root) ; size_t BTreeLeafSize(BTNode* root) ; size_t BTreeKLevelSize(BTNode* root, size_t k) ; size_t BTreeDepth(BTNode* root) ; BTNode* BTreeFind(BTNode* root, BTDataType x) ; void BTreeLevelOrder(BTNode* root) ; // 判断完全二叉树 int IsCompleteBTree(BTNode* root) ; int IsCompleteBTree1(BTNode* root) ;// flag的方式判断 // 非递归遍历 void BTreePrevOrderNonR(BTNode* root) ; void BTreeInOrderNonR(BTNode* root) ; void BTreePostOrderNonR(BTNode* root) ; void TestBinaryTree() ; #endif // !_BINTREE_H_BinTree.c
#include"BinTree.h" BTNode* BuyBTNode(BTDataType x){ BTNode *node=(BTNode *)malloc(sizeof(BTNode)); node->_data=x; node->_left=NULL; node->_right=NULL; return node; } BTNode* CreateBTree(BTDataType* a, size_t* pIndex, BTDataType invalid){ BTNode *root=NULL; if(a[*pIndex]!=invalid){ root = BuyBTNode(a[*pIndex]); (*pIndex)++; root->_left = CreateBTree( a, pIndex, invalid); (*pIndex)++; root->_right = CreateBTree( a, pIndex, invalid); } return root; } void BTreePrevOrder(BTNode* root){ if(root==NULL) return; printf("%d ",root->_data); BTreePrevOrder(root->_left); BTreePrevOrder(root->_right); } void BTreeInOrder(BTNode* root) { if(root==NULL) return; BTreeInOrder(root->_left); printf("%d ",root->_data); BTreeInOrder(root->_right); } void BTreePostOrder(BTNode* root) { if(root==NULL) return; BTreeInOrder(root->_left); BTreeInOrder(root->_right); printf("%d ",root->_data); } size_t BTreeSize(BTNode* root) { if(root==NULL) return 0; return BTreeSize(root->_left)+BTreeSize(root->_right)+1; } size_t BTreeLeafSize(BTNode* root) { if(root==NULL) return 0; if(root->_left==NULL&&root->_right==NULL) return 1; return BTreeLeafSize(root->_left)+BTreeLeafSize(root->_right); } size_t BTreeKLevelSize(BTNode* root, size_t k){ if(root==NULL) return 0; if(k==1) return 1; return BTreeKLevelSize(root->_left, k-1)+ BTreeKLevelSize(root->_right,k-1); } size_t BTreeDepth(BTNode* root){ if(root==NULL) return 0; return BTreeDepth(root->_left)+1; } BTNode* BTreeFind(BTNode* root, BTDataType x) { BTNode* leftNode, *rightNode; if(root==NULL) return NULL; if(root->_data==x) return root; leftNode=BTreeFind(root->_left,x); if(leftNode) return leftNode; rightNode=BTreeFind(root->_right,x); if(rightNode) return rightNode; } void BTreeLevelOrder(BTNode* root){ //层序遍历 Queue q; QueueInit(&q); QueuePush(&q,root); while(QueueEmpty(&q)){ BTNode* cur=QueueFront(&q); printf("%d ",cur->_data); if(cur->_left) QueuePush(&q,cur->_left); if(cur->_right) QueuePush(&q,cur->_right); QueuePop(&q); } printf("\n"); } int IsCompleteBTree(BTNode* root) { Queue q; QueueInit(&q); QueuePush(&q,root); while(QueueEmpty(&q)){ BTNode* cur=QueueFront(&q); if(cur==NULL){ break; } else{ QueuePush(&q,cur->_left); QueuePush(&q,cur->_right); } QueuePop(&q); } while(QueueEmpty(&q)){ BTNode* cur=QueueFront(&q); if(cur!=NULL) return 0; QueuePop(&q); } return 1; } int IsCompleteBTree1(BTNode* root) ;// flag的方式判断 // 非递归遍历 void BTreePrevOrderNonR(BTNode* root) ; void BTreeInOrderNonR(BTNode* root) ; void BTreePostOrderNonR(BTNode* root) ; void TestBinaryTree() { int a[] = {1, 2, 3, '#', '#',4,'#', '#', 5, 6,'#' ,'#' ,'#' }; size_t index = 0; BTNode* tree = CreateBTree(a, &index, '#'); BTreePrevOrder(tree); printf("\n"); //BTreePrevOrderNonR(tree); BTreeInOrder(tree); printf("\n"); BTreePostOrder(tree); printf("\n"); printf("BTreeSize? %d\n", BTreeSize(tree)); printf("BTreeLeafSize? %d\n", BTreeLeafSize(tree)); printf("BTreeKLevelSize? %d\n", BTreeKLevelSize(tree, 2)); printf("BTreeDepth? %d\n", BTreeDepth(tree)); printf("Find: %d\n",BTreeFind(tree,5)->_data); BTreeLevelOrder(tree); printf("IsCompleteBTree? %d\n", IsCompleteBTree(tree)); }