相信原理在网上很多地方有很详细的讲解，个人转载这篇文章这个链接作为参考，如下所示：
2叉树原理详解及其数据遍历
源码提供：这里面包含了前中后序的递归实现，也包含了前中序的栈/数组实现。其中网络上很多源码都是有一些小小的瑕疵，运行之后会出现各种各样的问题，这份代码是自己手写的源码，经过测试无误！！！
/* * BinTree.c * * Created on: 2020年7月3日 * Author: Leonard */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #define ARRAY_LENGTH 21 typedef int KEY_VALUE; /*这段代码还是很神奇的，可以做到结构题与业务分离的作用，可以用到实际的项目里去 :)*/ #define BSTREE_ENTRY(name,type) \ struct name { \ struct type *left; \ struct type *right; \ } typedef struct bst_treenode { KEY_VALUE data; BSTREE_ENTRY(, bst_treenode) bst; }TBST_TREE,*PBST_TREE; struct bstree { TBST_TREE *root; //根节点 }; //创建节点 PBST_TREE CreateNewNode(KEY_VALUE value) { PBST_TREE node = NULL; node = (PBST_TREE)malloc(sizeof(TBST_TREE)); if (node == NULL) { assert(0); } node->bst.left = node->bst.right = NULL; node->data = value; return node; } //插入 int bstInsert(struct bstree* T,KEY_VALUE value) { assert(T != NULL); PBST_TREE p = T->root; PBST_TREE node = T->root; if(T->root == NULL) { T->root = CreateNewNode(value); return 1; } while(node != NULL) //先找某个最终插入的节点 { p = node; if(node->data > value) node = node->bst.left; else node = node->bst.right; } if(p->data > value) p->bst.left = CreateNewNode(value); else if(p->data < value) p->bst.right = CreateNewNode(value); else return 2; //同样的节点不选择插入进去 return 0; } //删除节点 int bstDelete(struct bstree* T,KEY_VALUE key) { assert(T != NULL); PBST_TREE tmp = T->root; PBST_TREE p = T->root; PBST_TREE pre = T->root; if(T->root == NULL) return -1; //找到节点 while(p != NULL) { tmp = p; if(key == p->data) break; else if(key > p->data) p = p->bst.right; else p = p->bst.left; pre = tmp; } //没找到 if(p == NULL) return -2; //删除根节点之后 这里选择之前的右子树的最左端插入，如果P没有右子树，直接将T->root = p的左子树节点 if(p == T->root) { tmp = p->bst.right; while(tmp->bst.left != NULL && tmp) tmp = tmp->bst.left; if(tmp != NULL) T->root = p->bst.right; else T->root = p->bst.left; } else { //step 1: 找到p的右子树的最左节点 tmp = p->bst.right; while(tmp->bst.left != NULL && tmp) { tmp = tmp->bst.left; } tmp->bst.left = p->bst.left; //将p的左子树插入到P的右子树的最左节点的 左节点 if(pre->bst.left->data == key) { if(tmp != NULL) pre->bst.left = p->bst.right; else pre->bst.left = p->bst.left; } else { if(tmp != NULL) pre->bst.right = p->bst.right; else pre->bst.right = p->bst.left; } } free(p); p = NULL; return 0; } //先序 根 左 右 int bstPreSortPrint(PBST_TREE node) { if(node == NULL) return 0; printf("%4d",node->data); bstPreSortPrint(node->bst.left); bstPreSortPrint(node->bst.right); } //中序 左 根 右 int bstMidSortPrint(PBST_TREE node) { if(node == NULL) return 0; bstMidSortPrint(node->bst.left); printf("%4d",node->data); bstMidSortPrint(node->bst.right); } //后序 左右根 int bstBehSortPrint(PBST_TREE node) { if(node == NULL) return 0; bstBehSortPrint(node->bst.left); bstBehSortPrint(node->bst.right); printf("%4d",node->data); } // stack 先/中 序遍历 0-preSort 1-midSort int OrderTraverseByStack(struct bstree *T,int mode) { assert(T); int top = 0; TBST_TREE* Stack[128] = {0}; //形象一点可以用栈实现，我这里用数组代替栈了 PBST_TREE pRoot = T->root; //初始化 if(T->root == NULL) return -1; while(pRoot || top > 0) //top>=0 会造成根节点的右子树重复打印，故必须top>0来作为判断条件 { if(pRoot != NULL) { Stack[top++] = pRoot; if(mode == 0) printf("%4d",pRoot->data); pRoot = pRoot->bst.left; } else { if(mode == 1) printf("%4d",Stack[top-1]->data); pRoot=Stack[--top]->bst.right; } } return 0; } /*这里的后序遍历栈实现，可以使用两个数组进行模拟栈实现， * 也可以用两个栈来实现后序遍历 * 网上教程代码也很多，可以参考着实现，这里就不再做过多的赘述 */ int main(int argc,const char *argv[]) { int keyArray[ARRAY_LENGTH] = {24,25,13,35,23, 26,67,47,38,98, 20,17,49,12, 21,9,11,18,14,15,10}; struct bstree T = {0}; int i = 0; for (i = 0;i < ARRAY_LENGTH;i ++) { bstInsert(&T, keyArray[i]); } printf("first sort:\n"); bstPreSortPrint(T.root); printf("\n"); printf("stack first sort:\n"); OrderTraverseByStack(&T,0); printf("\n"); printf("Middle sort:\n"); bstMidSortPrint(T.root); printf("\n"); printf("stack middle sort:\n"); OrderTraverseByStack(&T,1); printf("\n"); printf("Behind sort:\n"); bstBehSortPrint(T.root); printf("\n"); //delete one bstDelete(&T,20); printf("first sort:\n"); bstPreSortPrint(T.root); printf("\n"); return 0; }
