鹿泉手机网站建设,广州微网站开发,宁波妇科最有名的医院,wordpress主题 windows live二叉树的遍历 #x1f4ab;二叉树的结点结构定义#x1f4ab;创建一个二叉树结点#x1f4ab;在主函数中手动创建一颗二叉树#x1f4ab;二叉树的前序遍历#x1f4ab;调用栈递归——实现前序遍历#x1f4ab;递归实现中序和后序遍历 #x1f4ab;二叉树的结点结构定义 … 二叉树的遍历 二叉树的结点结构定义创建一个二叉树结点在主函数中手动创建一颗二叉树二叉树的前序遍历调用栈递归——实现前序遍历递归实现中序和后序遍历 二叉树的结点结构定义
typedef struct BinaryTreeNode
{int val;struct BinaryNode* left;struct BinaryNode* right;
}BTNode;创建一个二叉树结点
我们来写一个函数BuyNode(x)函数用于创建二叉树结点。 用动态开辟函数malloc函数进行动态开辟并强制转换为BTNode型用变量node来去管理开辟的空间。 我们初始化结点其val即为传入的参数x左右指针left和right都设为NULL。
//创建一个二叉树结点
BTNode* BuyNode(int x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL){perror(malloc fail);}else{node-val x;node-left NULL;node-right NULL;}
}在主函数中手动创建一颗二叉树 我们在主函数中创建上面这样一颗二叉树。 首先我们需要开辟6个结点但此时6个结点之间没有任何的联系我们需要改变其中一些结点的指针域left和right来使得结点之间产生联系。
int main()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);node1-left node2;node1-right node4;node1-rightnode3;node2-left node4;node3-left node5;node3-right node6;return 0;
}二叉树的前序遍历
首先我们先要了解以下二叉树前序的前序遍历。 二叉树的前序遍历 根--左子树--右子树 对于我们上面的这颗二叉树
1--左--右左子树和右子树也采用前序遍历的方式:
左子树
2--4右子树
3--5--6所以这颗二叉树的前序遍历为
1--2--4--3--5--6正是由于这样的思想将一个树根--左--右的左和右仍然是一颗树接着再拆分…直到左子树和右子树的左右结点为空时。 所以这样的思想我们就利用递归的想法就可以完成一颗二叉树的遍历。
调用栈递归——实现前序遍历 调用栈程序在执行时如果程序调用一个函数它会先把这个函数压入栈中等到这个函数返回结果(return )后它才会从栈中弹出。 递归程序在执行时会不断地调用自身把函数压入栈中当最后一个函数也就是基线条件出现时再逐渐清空栈空间。 下面我们根据这段代码来画图理解一些递归的思想。
//递归前序遍历一棵树
void PreOrder(BTNode* root)
{if (root NULL){printf(NULL);return;}printf(%d, root-val);PreOrder(root-left);PreOrder(root-right);return 0;
}我们按照步骤来执行以下程序 ①主函数中进行了函数调用参数为node1 压栈 node1不为空打印结点 ②执行PreOrder(root-left)再次调用函数参数为node2 进行压栈 node2不为空打印 ③执行PreOrder(root-left),再次调用函数参数为node4压栈 node4不为空打印 ④执行PreOrder(root-left)再次调用函数参数为NULL压栈 这是函数参数为NULL进入if语句进行打印 并return返回这时出栈。 ⑤y由于这段代码当函数的参数为node4时PreOrder(node4-left)已经有return所以这时程序会接着往下面执行PreOrder(node4-right) 这时再次调用函数函数参数为NULL压栈打印再出栈。
⑥ 这时对于函数PreOrder (node4)已经执行完语句 PreOrder(node4-left)和语句PreOrder(node4-right)了后执行 return 0函数有返回结果所以出栈。 ⑦此时我们该执行 node2的右结点了。 对于PreOrder(node2-right)中函数函数即是NULL所以先压栈然后打印然后出栈。 ⑧此时函数PreOrder(node2) 的PreOrder(node2-left) 和PreOrder(node2-right) 都已经执行完了即已经对node2结点的左右子树遍历完成执行return 0 返回这时PreOrder(node2) 出栈。 在此时我们已经对node1的左子树遍历完成接下来同遍历左子树一样我们对右子树进行遍历。 这时输出为
递归实现中序和后序遍历
根据上面前序的递归我觉得最重要的代码是 if (root NULL){printf(NULL);return;}它是递归中能否回溯的一个关键。 下面写中序遍历
//递归中序遍历二叉树
void Order(BTNode* root)
{if (root NULL){printf(NULL );return;}Order(root-left);printf(%d , root-val);Order(root-right);return 0;
}递归后序遍历一棵树
//递归后序遍历一颗二叉树
void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-val);return 0;
}前中后序遍历结果分别为
