精华内容
下载资源
问答
  • 先根遍历和后根遍历
    千次阅读 多人点赞
    2018-06-19 14:00:05

    二叉树的非递归遍历

    • 二叉树的三种遍历方式也可以通过非递归的方法借助栈来实现。
    • 通过控制节点的出栈和入栈先后顺序来实现对树的不同方式的遍历。

    非递归先根遍历二叉树

    • 当栈不为空或者当前节点为不为空,执行操作:
    • 从根节点开始,依次访问树中最左端的节点并入栈,当节点为空停止入栈。
    • 取栈顶元素为当前节点并出栈,如果当前节点有右子树,则遍历其右子树。
    void PreorderPrint(SearchBTree T)       // 先序根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                cout << pT->data << " ";    // 打印当前结点
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {       // pT为空,则
                pT = getTop(S);
                Pop(S);                  // 若pT为空表示左子树的左孩子全部遍历完,依次出栈
                pT = pT->right;             // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }

    非递归中根遍历二叉树

    • 当栈不为空或者当前节点为不为空,执行操作:
    • 同样地,先依次将根节点及其左子树最左端的节点入栈,但不进行访问。当节点为空,则停止入栈。
    • 访问栈顶元素作为当前节点并出栈,如果当前节点有右子树,则遍历访问其右子树。
    void InorderPrint(SearchBTree T)        // 中根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {       // pT为空,则
                pT = getTop(S);
                Pop(S); cout << pT->data << " ";    // 若pT为空表示左子树的左孩子全部遍历完,依次出栈并打印
                pT = pT->right;             // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }

    非递归后根遍历二叉树

    • 非递归后根遍历相比前两个有点麻烦,需要引入一个中间变量标记已经访问节点。
    • 当栈不为空或者当前节点为不为空,执行操作:
    • 依次将根节点及其左子树的左端节点入栈,但不进行访问,当节点为空,停止入栈。
    • 取栈顶元素作为当前节点,如果当前节点的右孩子(右子树)不为空且其右孩子不是上一次访问的节点。则当前节点变为其右子树,遍历其右子树。如果当前节点的右孩子为空或者其右孩子已经被访问,则访问当前节点,标记当前节点为已访问节点,出栈。将当前节点置为空(此时右孩子访问过了),继续取栈顶元素(为了访问根节点)。
    void PostorderPrint(SearchBTree T)      // 先根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
        TreeNode* qT = nullptr;
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {
                pT = getTop(S);         // 取栈顶元素作为当前结点
                if (pT->right && pT->right != qT)   // 若当前节点有右孩子且不是上一次已经被访问的结点
                {
                    pT = pT->right;     // 指向其右孩子
                }
                else
                {                       // 若当前结点没有右孩子或者未被访问,则
                    Pop(S);             // 出栈
                    cout << pT->data << " ";    // 访问当前结点的数据
                    qT = pT;                    // 令pT记录当前结点,用于稍后判断是否已经被访问过
                    pT = nullptr;               // 将当前结点赋值为空
                }
                    // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }

    附总的代码实现

    #include<iostream>
    using namespace std;
    typedef int ElemType;
    
    typedef struct _TreeNode {  // 定义二叉查找树的结构
        ElemType data;          // 数据
        struct _TreeNode* left;         // 指向左孩子指针
        struct _TreeNode* right;        // 指向其右孩子指针 
    }TreeNode, *SearchBTree;
    
    typedef SearchBTree StackElemType;
    typedef struct StackNode {          // 定义栈的结构(基于链表)
        SearchBTree data;
        StackNode *next;
    }*Stack;
    
    void initStack(Stack St)        // 初始化栈,把头节点看作是栈顶
    {
        St->next = nullptr;
    }
    
    int isEmpty(Stack St)
    {
        return St->next == nullptr;
    }
    
    void Push(Stack St, SearchBTree x)      // 每次从将元素插入到头节点的位置,头节点上移
    {
        StackNode* q = new StackNode;
        q->data = x;
        q->next = St->next;     // q的next域指向St(头节点)的后继结点
        St->next = q;           // St(头节点/栈顶)next域指向q,实现栈往上移
    }
    
    void Pop(Stack St)      // 出栈
    {
        StackNode* p = St->next;        // 临时结点指向头结点(栈顶)的后继结点
        St->next = p->next;     // 栈顶下移
        delete p;           // 释放空间
    }
    
    SearchBTree getTop(Stack St)
    {
        return St->next->data;
    }
    
    SearchBTree EmptyTree(SearchBTree T)    // 初始化、构造一颗空树/销毁一颗树
    {
        if (!T)
        {
            EmptyTree(T->left);     // 递归地释放空间
            EmptyTree(T->right);
            delete T;
        }
        return nullptr;
    }
    
    void Insert(SearchBTree &T, ElemType x)
    {
        if (!T)
        {
            TreeNode* pT = new TreeNode;        // 申请节点空间
            pT->data = x;                       // 为节点赋值
            pT->left = pT->right = nullptr;
            T = pT;                             // 将pT赋给T
        }
        else
        {
            if (x < T->data)                // 如果x小于某个结点的数据
                Insert(T->left, x);         // 递归地在其左子树上寻找空结点插入
            else if (x > T->data)           // 如果x大于某个结点的数据
                Insert(T->right, x);        // 递归地在其左子树上寻找空结点插入
        }
    }
    
    void PreorderPrint(SearchBTree T)       // 先序根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                cout << pT->data << " ";    // 打印当前结点
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {       // pT为空,则
                pT = getTop(S);
                Pop(S);                  // 若pT为空表示左子树的左孩子全部遍历完,依次出栈
                pT = pT->right;             // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }
    
    void InorderPrint(SearchBTree T)        // 中根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {       // pT为空,则
                pT = getTop(S);
                Pop(S); cout << pT->data << " ";    // 若pT为空表示左子树的左孩子全部遍历完,依次出栈并打印
                pT = pT->right;             // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }
    
    void PostorderPrint(SearchBTree T)      // 先根(序)遍历二叉树并打印出结点值
    {
        if (T == nullptr)
        {
            cout << "Empty tree!";
            exit(1);
        }
        Stack S = new StackNode;        // 借助栈来实现
        initStack(S);
    
        TreeNode* pT = T;       // 创建临时结点指向根节点
        TreeNode* qT = nullptr;
    
        while (pT || !isEmpty(S))           // 当结点不为空或者栈不为空执行循环
        {
            if (pT)                         // 当pT不为空
            {
                Push(S, pT);                // pT入栈
                pT = pT->left;              // pT移动指向其左孩子
            }
            else
            {
                pT = getTop(S);         // 取栈顶元素作为当前结点
                if (pT->right && pT->right != qT)   // 若当前节点有右孩子且不是上一次已经被访问的结点
                {
                    pT = pT->right;     // 指向其右孩子
                }
                else
                {                       // 若当前结点没有右孩子或者未被访问,则
                    Pop(S);             // 出栈
                    cout << pT->data << " ";    // 访问当前结点的数据
                    qT = pT;                    // 令pT记录当前结点,用于稍后判断是否已经被访问过
                    pT = nullptr;               // 将当前结点赋值为空
                }
                    // 当左孩子及根结点遍历完之后,开始遍历其右子树
            }
        }
        cout << endl;
        delete S;
    }
    
    int main()
    {
        const ElemType rawdata[] = { 19, 7, 9, 15, 23, 39, 4, 2, 75, 100, 43, 58 };
        SearchBTree myTree = new TreeNode;
        myTree = EmptyTree(myTree);     // 初始化树
        for (int i = 0;i < sizeof(rawdata) / sizeof(ElemType);i++)
        {
            Insert(myTree, rawdata[i]);     // 向树中插入给定数据
        }
    
        cout << "The inorder print of the tree is: \n";
        InorderPrint(myTree);
        cout << "The preorder print of the tree is: \n";
        PreorderPrint(myTree);
        cout << "The postorder print of the tree is: \n";
        PostorderPrint(myTree);
    
        delete myTree;
        system("pause");
        return 0;
    }
    • 操作运行结果
    The preorder print of the tree is:
    19 7 4 2 9 15 23 39 75 43 58 100
    The inorder print of the tree is:
    2 4 7 9 15 19 23 39 43 58 75 100
    The postorder print of the tree is:
    2 4 15 9 7 58 43 100 75 39 23 19
    更多相关内容
  • 森林(树)的括号表示法←→森林(树)←→二叉树←→遍历序列 ↓ 遍历序列
  • 二叉树的根,中根,后根遍历

    千次阅读 2021-11-16 17:10:01
    在java中,可以把数的一个节点看成一个对象,每个节点都有data最多两个字节点 class TreeNode { int data; TreeNode left; TreeNode right; } 首先先生成一颗二叉树 public void add(TreeNode node) { if ...

    二叉树(Binary tree)是树形结构的一个重要类型

    在java中,可以把数的一个节点看成一个对象,每个节点都有data和最多两个字节点

        class TreeNode {
            int data;
            TreeNode left;
            TreeNode right;
        }
    

    首先先生成一颗二叉树

    public void add(TreeNode node) {
            if (node.data < this.data) {
                if (left == null) left = node;
                else left.add(node);
            }
            if (node.data > this.data) {
                if (right == null) right = node;
                else right.add(node);
            }
        }
    
    public static void main(String[] args) {
            Tree tree = new Tree();
            tree.add(8);
            tree.add(4);
            tree.add(2);
            tree.add(3);
            tree.add(1);
            tree.add(6);
            tree.add(6);
            tree.add(7);
            tree.add(12);
            tree.add(10);
            tree.add(9);
            tree.add(11);
            tree.add(14);
            tree.add(13);
            tree.add(15);
        }
    

    创建的二叉树如下图所示
    在这里插入图片描述

    先根遍历:先根遍历就是先遍历根节点,然后遍历左子树,再然后右子树
    即输出8->4->2->1->3->6->7->12->10->9->11->14->13->15

        public void firstRoot() {
            System.out.print(data + " ");
            if (left != null) left.firstRoot();
            if (right != null) right.firstRoot();
        }
    

    中根遍历,先遍历左子树,然后遍历根,再然后遍历右子树
    即输出1->2->3->4->6->7->8->9->10->11->12->13->14->15

    public void midRoot() {
            if (left != null) left.midRoot();
            System.out.print(data + " ");
            if (right != null) right.midRoot();
        }
    

    后根遍历:先遍历左子树,然后再遍历右子树,最后再遍历根;
    即输出:1->3->2->7->6->4->9->11->10->13->15->14->12->8

    public void afterRoot() {
            if (left != null) left.afterRoot();
            if (right != null) right.afterRoot();
            System.out.print(data + " ");
        }
    

    完整代码

    public class TreeNode {
        public int data;
        public TreeNode left;
        public TreeNode right;
    
        public TreeNode(int data) {
            this.data = data;
        }
    
        //中序存
        public void add(TreeNode node) {
            if (node.data < this.data) {
                if (left == null) left = node;
                else left.add(node);
            }
            if (node.data > this.data) {
                if (right == null) right = node;
                else right.add(node);
            }
        }
    
        public void firstRoot() {
            System.out.print(data + " ");
            if (left != null) left.firstRoot();
            if (right != null) right.firstRoot();
        }
    
        public void midRoot() {
            if (left != null) left.midRoot();
            System.out.print(data + "->");
            if (right != null) right.midRoot();
        }
    
        public void afterRoot() {
            if (left != null) left.afterRoot();
            if (right != null) right.afterRoot();
            System.out.print(data + "->");
        }
    }
    
    public class Tree {
        TreeNode root;
        public void add(int n) {
            TreeNode node = new TreeNode(n);
            if (root == null) {
                root = node;
            } else {
                root.add(node);
            }
        }
    
        public void first() {
            root.firstRoot();
            System.out.println();
        }
    
        public void mid() {
            root.midRoot();
            System.out.println();
        }
    
        public void after() {
            root.afterRoot();
            System.out.println();
        }
    }
    
    展开全文
  • 二叉树先根次序遍历、中次序遍历后根次序遍历
  • 图解二叉树根、中根、后根遍历

    千次阅读 2020-09-02 09:23:17
    根、中根、后根遍历 三种遍历都是递归遍历 先根遍历 结果:ABCDEFGH 原理:先遍历根节点,再遍历左子树,最后遍历右子树; 中根遍历 结果:CBEDFAGH 原理:遍历左子树,再遍历根节点,最后遍历右子树; 后根...

    二叉树

    在这里插入图片描述

    先根、中根、后根遍历

    三种遍历都是递归遍历

    1. 先根遍历
      结果:ABCDEFGH
      原理:先遍历节点,再遍历子树,最后遍历子树;
    2. 中根遍历
      结果:CBEDFAGH
      原理:先遍历子树,再遍历节点,最后遍历子树;
    3. 后根遍历
      结果:CEFDBHGA
      原理:遍历子树,再遍历子树,最后遍历节点;
    展开全文
  • 根遍历和先根遍历/后根遍历构建二叉树

    万次阅读 多人点赞 2017-04-12 22:34:34
    1问题 给定二叉树的2个遍历序列(如先根+中先根+后根,中...因为先根/后根可以确定二叉树根节点是哪个,而中可以将二叉树分为节点其左子树其右子树,进而可以将先根/后根分成"+左子树先根+右子树先根

    1问题

    给定二叉树的2个遍历序列(如先根+中根,先根+后根,中根+后根等),是否能够根据这2个遍历序列唯一确定二叉树?

    2结论

    这三种组合并不是都能唯一确定二叉树的,其中先根+后根就不能唯一确定一棵二叉树,中根+先根/后跟可以唯一确定一棵二叉树。因为先根/后根可以确定二叉树根节点是哪个,而中根可以将二叉树分为根节点和其左子树和其右子树,进而可以将先根/后根分成"根+左子树先根+右子树先根“ 或 “左子树后根+右子树后根+根”。然后就可以利用递归解决问题啦。

    3理论分析

    下面是关于该问题的证明与结论。

    给定二叉树结点的前序序列和中序序列,可以唯一确定该二叉树
    证明:因为先序序列的第一个元素是根结点,该元素将二叉树中序序列分成两部分,左边(假设有L个元素)表示左子树,若左边无元素,则说明左子树为空;右边(假设有R个元素)是右子树,若为空,则右子树为空。根据前序遍历中"根-左子树-右子树"
    的顺序,则由从先序序列的第二元素开始的L个结点序列和中序序列根左边的L个结点序列构造左子树,由先序序列最后R个元素序列与中序序列根右边的R个元素序列构造右子树。

    ②由中序序列和先序序列能唯一确定一棵二叉树,但是由先序序列和后序序列不能唯一确定一棵二叉树,因无法确定左右子树两部分。
    反例:任何结点只有左子树的二叉树和任何结点只有右子树的二叉树,其前序序列相同,后序序列相同,但却是两棵不同的二叉树。
    如: 2           2
        /            \
       1              1 
      /                \
     3                  3
    这两棵二叉树的先序遍历序列都为2-1-3,后序遍历序列都为3-1-2。但是显然它们是不同的二叉树,所以根据先序序列和后序序列并不能唯一确定二叉树。

    ③已经说明由二叉树的先序序列和中序序列可以确定一棵二叉树,现在来证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。

    证明:
    当n=
    1时,只有一个根结点,由中序序列和后序序列可以确定这棵二叉树。
    设当n=m-1时结论成立,即结点数目为m-1时,中序序列和后序序列可以唯一确定二叉树。现证明当n=
    m时结论成立。
    设中序序列为S1,S2,…,Sm,后序序列是P1,P2,…,Pm。因后序序列最后一个元素Pm是根,则在中序序列中可找到与Pm相等的结点(设二叉树中各结点互不相同)Si(1≤i≤m),因中序序列是由中序遍历而得,所以Si是根结点,S1,S2,…,Si-1是左子树的中序序列,而Si+1,Si+2
    ,…,Sm是右子树的中序序列。
    若i=1,则S1是根,这时二叉树的左子树为空,右子树的结点数是m-1,则{S2,S3,…,Sm}和{P1,P2,…,Pm-1
    }可以唯一确定右子树,从而也确定了二叉树。
    若i=m,则Sm是根,这时二叉树的右子树为空,左子树的结点数是m-1,则{S1,S2,…,Sm-1}和{P1,P2,…,Pm-1
    }唯一确定左子树,从而也确定了二叉树。
    最后,当1<i<m时,Si把中序序列分成{S1,S2,…,Si-1}和{Si+1,Si+2,…,Sm}。由于后序遍历是"左子树-右子树-根结点",所以{P1,P2,…,Pi-1}和{Pi,Pi+1,…Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1,S2,…,Si-1}和{P1,P2,…,Pi-1}可唯一确定二叉树的左子树,由{Si+1,Si+2,…,Sm}和{Pi,Pi+1,…,Pm-1}可唯一确定二叉树的右子树。

    4代码实现
    前序遍历的第一个元素为根节点,在中序遍历中找到这个根节点,从而可以将中序遍历分为左右两个部分,左边部分为左子树的中序遍历,右边部分为右子树的中序遍历,进而也可以将前序遍历除第一个元素以外的剩余部分分为两个部分,第一个部分为左子树的前序遍历,第二个部分为右子树的前序遍历。 

    由上述分析结果,可以递归调用构建函数,根据左子树、右子树的前序、中序遍历的结果输出后序遍历的结果。 

    1. //根据前序遍历和中序遍历重建二叉树的Java实现   
    2.   
    3. class Node {    
    4.     Node left = null;    
    5.     Node right = null;    
    6.     char value;    
    7. }    
    8. public class BinaryTreeBuilder {    
    9.     /**  
    10.      * 根据前序遍历和中序遍历重建二叉树子树  
    11.      * @param preOrder 前序遍历数组  
    12.      * @param start 子树起始位置  
    13.      * @param inOrder 中序遍历数组  
    14.      * @param end 中序遍历结束位置  
    15.      * @param length 节点数  
    16.      * @return 树的根节点  
    17.      */    
    18.  public static Node buildTree(char[] preOrder,int start, char[] inOrder,int end,int length){    
    19.         //参数验证     
    20.         if (preOrder == null || preOrder.length == 0 || inOrder == null    
    21.                 || inOrder.length == 0 || length <= 0) {    
    22.             return null;    
    23.         }    
    24.             
    25.         //根据前序遍历的第一个元素建立树根节点     
    26.         char value = preOrder[start];    
    27.         Node root = new Node();    
    28.         root.value = value;    
    29.             
    30.         //递归终止条件:子树只有一个节点     
    31.         if (length == 1)    
    32.             return root;    
    33.             
    34.         //根据前序遍历的第一个元素在中序遍历中的位置分拆树的左子树和右子树     
    35.         int i = 0;    
    36.         while (i < length) {    
    37.             if (value == inOrder[end - i]) {    
    38.                 break;    
    39.             }    
    40.             i++;    
    41.         }    
    42.             
    43.         //建立子树的左子树     
    44.     root.left = buildTree(preOrder, start + 1, inOrder, end - i - 1, length - 1 - i);    
    45.         //建立子树的右子树     
    46.     root.right = buildTree(preOrder, start + length - i, inOrder, end, i );    
    47.             
    48.         return root;    
    49.     }    
    50.   
    51.    // 后序遍历二叉树  
    52.     private static void postOrder(Node root) {  
    53.         if (root == null) {  
    54.             return;  
    55.         }  
    56.         postOrder(root.left);  
    57.         postOrder(root.right);  
    58.         System.out.print(root.value+"  ");  
    59.     }  
    60.   
    61.   
    62.     public static void main(String[] args) {   
    63.         //char[] preOrder = new char[] {'1', '2', '4', '5', '3', '6'};    
    64.         char[] preOrder = new char[] {'A''B''D''E''G''H','J','C','F','I'};    
    65.         //char[] inOrder = new char[] {'4', '2', '5', '1', '6', '3'};    
    66.         char[] inOrder = new char[] {'D''B''G''E''H''J','A','C','I','F'};    
    67.         Node root = buildTree(preOrder, 0, inOrder, inOrder.length - 1, inOrder.length);    
    68.         postOrder(root);  
    69.     }    
    70. }    


    运行结果: 
    D  G  J  H  E  B  I  F  C  A 



    展开全文
  • 根,中根,后根遍历

    万次阅读 多人点赞 2018-06-08 16:17:00
    先序遍历(根)是访问当前节点,然后再...一棵二叉树的先根遍历为ABCDEFG,中根遍历为CBDEAGF,则其后根遍历为多少? 方法:(层层解剖,集合从大到小,递归分析) (无论如何必须分析根,确定父节点,再...
  • 数据结构中最爱考的题型已知后根、中先根或已知先根、中后根
  • 答: 能确定,树的先根遍历和后根遍历对应二叉树的先序遍历中序遍历。由二叉树的先序遍历中序遍历可唯一确定一颗二叉树,二叉树可唯一变换为树
  • 经典的二叉树的根、中根和后根遍历序列题

    千次阅读 热门讨论 2022-04-06 17:16:37
    根、中根后序根遍历序列
  • 二叉树根、中根、后根遍历

    万次阅读 多人点赞 2017-10-14 17:39:19
    二叉树根、中根、后根遍历 先根遍历: ABCDEFGH 中根遍历:CBEDFAGH 后根遍历 : CEFDBHGA
  • 先序遍历和先根遍历的区别

    千次阅读 2021-02-01 12:24:36
    没区别 如此,中序后序
  • 那可以推断出,要满足题意的话“二叉树的先序序列与后序序列正好相反”,说明整个二叉树左子树或者右子树有一个没有(遍历就成了,:M-L ;:L-M 或者 :M-R ;:R-M )也就是必然是一条链。 所以只有A对了...
  • //访问根节点 } } //建立二叉树 //由先根遍历序列根遍历序列建立一棵二叉树 public BiTree(String preOrder,String inOrder,int preIndex,int inIndex,int count) { if(count>0) { char r=preOrder....
  • // 由中根遍历的数组和后根遍历的数组建立一棵二叉树 // 其中参数inOrder是整棵树的中根遍历,postOrder是整棵树的后根遍历,inIndex是 // 中根遍历从inOrder字符串中的开始位置,postIndex是后根遍历从字符串...
  • 1、 构建二叉排序树,并进行中和后根遍历 【问题描述】 构建二叉排序树,并进行中和后根遍历。1,结点的权值为int型 【输入形式】 输入n个结点,其为整数 【输出形式】 二叉排序树的中和后根遍历...
  • 二叉树的先根遍历

    千次阅读 2017-03-03 11:00:28
    二叉树的先根遍历面试时,经常问道类似与,获取某一文件夹下所有文件文件夹;二叉树遍历等问题。 这是一类问题,以二叉树的先根遍历举例:递归实现public class Test { /** * 二叉树节点类 */ public static ...
  • 森林的遍历

    千次阅读 2020-02-20 09:56:24
    根遍历:访问树的根结点,然后再依次先根遍历根的每棵子树。 根遍历:依次遍历每棵子树,然后再访问根结点。 根遍历结果:ABEFCGDHIJ 根遍历结果:EFBGCHIJDA 2.森林的遍历 森林的遍历也分为前序遍历...
  • 数据结构——树森林的遍历方法

    千次阅读 多人点赞 2017-10-15 12:22:51
    树的遍历主要有先根遍历和后根遍历。 2、(1)先根遍历:若树非空,则访问根结点,再按照从左到右的顺序遍历根结点的每一棵子树。这个访问顺序与这棵树对应的二叉树的先序遍历顺序相同。 (2)后根遍历:若树非空...
  • 二叉树先根遍历、中根遍历后根遍历非递归算法的C++代码
  • 下面小编就为大家带来一篇通过先序遍历和中序遍历后的序列还原二叉树(实现方法)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • 既然是树,还是用根来描述更为贴切,根遍历出来,再遍历左右子树,就是先根遍历后根遍历就是把左右...那么问题来了,只看结果的话,如何根据和后根,求出中根遍历根:5 3 2 4 6 8 7 9 根:2 4 3 7
  • 函数填空:层次遍历多元树(在文件tree.cpp中3个空)、先根遍历后根遍历的递归函数(在文件tree.h中2个空);
  • 创建一棵二叉树,以二叉链表作存储结构,实现先根遍历算法
  • //二叉树结点的定义。   ...//一个循环遍历相应节点的右子树 ...//中根遍历的非递归算法 ...3: 如果除去访问节点的语句,先根遍历和根遍历是完全相同的,后根遍历也只是出栈函数的参数不同而已。
  • 二叉树的遍历 所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。...如果N代表根节点,L代表根节点的左子树,R代表根节点的右子树,则根据遍历根节点的先后次序有以下遍历方式
  • 树的先根遍历

    千次阅读 2015-03-28 22:44:14
    /*先根遍历兄弟树*/ } } /* void RootFirst(CSTree root) { CSNode *p; if (root!=NULL) { printf("%c ",root->data); / * 访问根结点 * / p= root->FirstChild; while (p!=NULL) { RootFirst(p)...
  • 后根遍历的顺序是左子树>右子树>根,根是最后的,但我们整体遍历...逆后根遍历先根遍历几乎完全一样,原理一样,只是一个往左一个往右! 后根遍历的非递归算法——巧解(代码): public void postOrde...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 404,275
精华内容 161,710
关键字:

先根遍历和后根遍历