二叉树 (1）

1.节点的结构

typedef int BTDatatype; typedef struct BineryTreeNode { BTDatatype val; struct BineryTreeNode* left; struct BineryTreeNode* right; }BTnode;

2.节点的创建

BTnode* BuyNode(int x) { BTnode* newnode = (BTnode*)malloc(sizeof(BTnode)); if (newnode == NULL) { perror("malloc"); return NULL; } newnode->val = x; newnode->left = NULL; newnode->right = NULL; return newnode;//记得返回节点 }

3.手动创建一个二叉树

BTnode* CreatTree() { BTnode* node1 = BuyNode(1); BTnode* node2 = BuyNode(2); BTnode* node3 = BuyNode(3); BTnode* node4 = BuyNode(4); BTnode* node5 = BuyNode(5); BTnode* node6 = BuyNode(6); BTnode* node7 = BuyNode(7); node1->left = node2; node2->left = node3; node1->right = node4; node4->left = node5; node4->right = node6; node6->right = node7; return node1; }

4.前中后序遍历

//前序遍历 void PrevOrder(BTnode* root) { if (root == NULL) { printf("N "); return; } printf("%d ", root->val); PrevOrder(root->left); PrevOrder(root->right); }

//中序遍历 void InOrder(BTnode* root) { if (root == NULL) { printf("N "); return; } InOrder(root->left); printf("%d ", root->val); InOrder(root->right);//是换一下顺序，但是记得把名字改一下 }

//后续遍历 void PostOrder(BTnode* root) { if (root == NULL) { printf("N "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->val); }

5.求树的节点数

//求树的节点数，可以遍历但代码很挫 int BineryTreeSize(BTnode* root) { if (root == NULL) return 0; return BineryTreeSize(root->left) + BineryTreeSize(root->right) + 1; }

6.树的高度

int BineryTreeHeight(BTnode* root) { if (root == NULL) { return 0; } //记得把求出的值用变量存起来，不然会重复计算，对大大降低效率 int leftH = BineryTreeHeight(root->left); int rightH = BineryTreeHeight(root->right); return leftH > rightH ? leftH + 1 : rightH + 1; }

7.第K层的元素个数

int BineryTreeKcount(BTnode* root,int k) { if (root == NULL) return 0; if (k == 1) return 1; //求第k层的元素个数相当于求两个子树的第k-1层的元素个数 return BineryTreeKcount(root->left, k - 1) + BineryTreeKcount(root->right, k - 1); }

8.查找树种的特定节点

BTnode* BTFind(BTnode* root,int x) { if (root == NULL) return NULL; if (root->val == x) return root; BTnode* left = BTFind(root->left, x); if (left) return left; BTnode* right = BTFind(root->right, x); if (right) return left; }

9.测试的部分

int main() { BTnode* root = CreatTree(); PrevOrder(root); printf("\n"); InOrder(root); printf("\n"); PostOrder(root); printf("\n"); printf("%d",BineryTreeSize(root)); printf("\n"); printf("%d", BineryTreeHeight(root)); printf("\n"); printf("%d", BineryTreeKcount(root,4)); printf("\n"); return 0; }

10.二叉树的销毁

void BTDestroy(BTnode* root) { if (root == NULL) return 0; BTDestroy(root->left); BTDestroy(root->right); free(root); root = NULL; }