给一个源代码, 演示了如何使用结构,指针,构造一个有序,无序二叉树,递归函数的调用过程
#include#include #include #include typedef struct stBinaryNode { int _value; struct stBinaryNode* _left; struct stBinaryNode* _right; }BinaryNode; BinaryNode* createNode() { BinaryNode* lpNode = malloc(sizeof(BinaryNode)); memset(lpNode, 0, sizeof(BinaryNode)); return lpNode; } BinaryNode* insertLeftNode(BinaryNode* lpParent, int v) { if (!lpParent) { return NULL; } while (lpParent->_left) { lpParent = lpParent->_left; } BinaryNode* lpNode = createNode(); lpParent->_left = lpNode; lpNode->_value = v; return lpNode; } BinaryNode* insertRightNode(BinaryNode* lpParent, int v) { if (!lpParent) { return NULL; } while (lpParent->_right) { lpParent = lpParent->_right; } BinaryNode* lpNode = createNode(); lpNode->_value = v; lpParent->_right = lpNode; return lpNode; } // 有序插入新节点 void insertNodeWithOrder(BinaryNode* lpParent, int v) { if (!lpParent) { return; } if (v < lpParent->_value) { if (lpParent->_left) { insertNodeWithOrder(lpParent->_left, v); } else { insertLeftNode(lpParent, v); } } else if (v > lpParent->_value) { if (lpParent->_right) { insertNodeWithOrder(lpParent->_right, v); } else { insertRightNode(lpParent, v); } } } // 递归添加子节点,建立10层二叉树结构 void insertNode(BinaryNode *lpParent, int layer, int maxLayer, int *index ) { if (layer >= maxLayer) { return; } // 当前节点插入左子节点, 节点的值为*index, 此值设定为每插入一个新节点, 就自增1 BinaryNode* lpLeft = insertLeftNode( lpParent, *index); (*index)++; // 递归调用自己,直到layer>=10 insertNode(lpLeft, layer + 1, maxLayer, index); // 当前节点插入右节点, 同样插入的值为*index, 此值设定为每插入一个新节点就自增1 BinaryNode* lpRight = insertRightNode(lpParent, *index); (*index)++; insertNode(lpRight, layer + 1, maxLayer, index); } // 前序打印 void prePrintNode(BinaryNode* lpNode) { if (!lpNode) { return; } printf("%dn", lpNode->_value); prePrintNode(lpNode->_left); prePrintNode(lpNode->_right); } // 中序打印 void middlePrintNode(BinaryNode* lpNode) { if (!lpNode) { return; } middlePrintNode(lpNode->_left); printf("%dn", lpNode->_value); middlePrintNode(lpNode->_right); } // 在这里完成后序打印 // 销毁二叉树 void destoryNode(BinaryNode* lpNode) { if (!lpNode) { return; } if(lpNode->_left) { destoryNode(lpNode->_left); lpNode->_left = NULL; } if (lpNode->_right) { destoryNode(lpNode->_right); lpNode->_right = NULL; } free(lpNode); } int main(int argc, char* argv[]) { // 初始化随机数 srand((int)time(NULL)); int index = 0; BinaryNode* lpRoot = createNode(); lpRoot->_value = index; index++; insertNode(lpRoot, 0, 5, &index); prePrintNode(lpRoot); printf("=============================n"); middlePrintNode(lpRoot); destoryNode(lpRoot); lpRoot = NULL; BinaryNode* lpRoot2 = createNode(); // 随机数赋值 lpRoot2->_value = rand() % 100; for (int i = 0; i < 100; i++) { // 随机数赋值 insertNodeWithOrder(lpRoot2, rand() % 100); } printf("lproot2====================================n"); prePrintNode(lpRoot2); printf("lpRoot2 middle ===============================n"); middlePrintNode(lpRoot2); destoryNode(lpRoot2); lpRoot2 = NULL; return 0; }



