二叉树存储及遍历

雨点打透心脏的1/2处 2022-07-12 06:46 180阅读 0赞

[点击打开链接][Link 1]←原文链接

[二叉树存储及遍历][Link 1]

**1、树的存储：**

![932826-20160619152506757-347429771.png][]

注意：树的深度是从根节点开始（其深度为1）自顶向下逐层累加的，而高度是从叶节点开始（其高度为1）自底向上逐层累加的。虽然树的深度和高度一样，但是具体到树的某个节点，其深度和高度是不一样的。我的理解是：非根非叶结点的深度是从根节点数到它的，高度是从叶节点数到它的。

![932826-20160619153439257-176641707.png][]

二叉树的存储：1、数组存储（此方法适合完全二叉树的存储）

2、链表存储（可分为二叉链表，三叉链表）结构如下：

![932826-20160619155619194-1546500274.png][]

**2、 使用二叉链表实现二叉树**

测试用例:

int a\[10\] = \{ 1, 2, '\#', '\#', 3, 4, '\#', '\#', 5, 6 \};//其中用'表示空'

按前序遍历的算法重建出二叉树为：(先创建根节点，再创建左子树，后创建右子树)

![932826-20160619161206851-1097126076.png][]

代码实现：

![复制代码][copycode.gif]

BinaryTree<T>* _CreateBinaryTree(const T *a，size_t size, size_t&index)
        {
            assert(a);
            BinaryTreeNode<T> *node = new BinaryTreeNode<T> (a[index]);
            if (index < size&&a[index++] != '#')
            {
                node->_left = _CreateBinaryTree(a, size, ++index);
               node->_right = _CreateBinaryTree(a, size, ++index);
    
            }
            else
            {
               return NULL；
           }
    return node;
    
        }

![复制代码][copycode.gif]

3、二叉树的遍历

以上图的二叉树为例：

1-a、先序遍历（由于二叉树的结构具有递归的特性可以采用递归的方式遍历）

![复制代码][copycode.gif]

void _PrevOrder(BinaryTreeNode<T>* root)
        {
            if (root)
            {
                cout<<root->_data<<" ";
                _PrevOrder(root->_left);
                _PrevOrder(root->_right);
            }
            else
                 return;
            
        }

![复制代码][copycode.gif]

1-b、二叉树的非递归先序遍历  
思想：1、可以采用栈先进先出的原则：先使根节点入栈，栈不为空打印栈顶元素，弹出栈顶元素，

2、在使栈顶元素的不为空右子树入栈，再使栈顶元素的不为空左子树入栈

3、 再按1、2进行判断直至栈为空退出

![复制代码][copycode.gif]

void PrevOrder_NonR(BinaryTreeNode<T> *_root)
        {
            if (_root==NULL)
            {
                return;
            }
            stack<BinaryTreeNode<T>*> s1;
            s1.push(_root);
            while (!s1.empty())
            {
                BinaryTreeNode<T> *top=s1.top();
                cout<<top->_data<<" ";
                s1.pop();
                if (top->_right)
                {
                    s1.push(top->_right);
                }
                if (top->_left)
                {
                    s1.push(top->_left);
                }
            }
            cout<<endl;
        }

![复制代码][copycode.gif]

2-a、二叉树的中序遍历（递归）

![复制代码][copycode.gif]

void _InOrder(BinaryTreeNode<T>* root)
        {
            if (root)
            {
                _InOrder(root->_left);
                cout<<root->_data<<" ";
                _InOrder(root->_right);
            }
            else
            {
                return;
            }
        }

![复制代码][copycode.gif]

2-b、二叉树的中序遍历非递归

思想：中序遍历是先遍历左子树，再遍历根节点，后遍历右子树

1、使cur指向根节点，使cur->\_left入栈直至cur为空（定义cur是为了指向当前遍历的节点）

2、若栈不为空，打印栈顶元素，使cur指向栈顶元素的右子树（当前的栈顶元素也就是某一个树的根节点，但其右子树还未遍历所以使cur指向其右子树）

3-a、若栈不为空，前一步栈顶元素的右子树为空，直接打印当前栈顶元素也就是前一步栈顶元素的根节点

3-b、若栈不为空，前一步栈顶元素的右子树不为空，使cur指向的右子树入栈

4、在按照2,3的步骤循环，直至cur和栈为空时结束

![复制代码][copycode.gif]

//非递归中序
        void InOrder_NonR(BinaryTreeNode<T> *root)
        {
            stack<BinaryTreeNode<T>*> s1;
            BinaryTreeNode<T>* cur=_root;
            while (cur||!s1.empty())
            {
                while (cur)
                {
                    s1.push(cur);
                    cur=cur->_left;
                }
                if (!s1.empty())
                {
                    BinaryTreeNode<T>* top=s1.top();
                    cout<<top->_data<<" ";
                    s1.pop();
                    cur=top->_right;
                }
    
            }
            cout<<endl;
        }

![复制代码][copycode.gif]

3-a二叉树的后续遍历（递归）

![复制代码][copycode.gif]

void _PostOrder(BinaryTreeNode<T>* root)
        {
            if (root)
            {
                _PostOrder(root->_left);
                _PostOrder(root->_right);
                cout<<root->_data<<" ";
            }
            else
            {
                return;
            }
        }

![复制代码][copycode.gif]

[Link 1]: http://www.cnblogs.com/Blog-day/p/My_Blog_Days-13.html
[932826-20160619152506757-347429771.png]: /images/20220711/865efe22953049a6959453b60d8fdaee.png
[932826-20160619153439257-176641707.png]: /images/20220711/264cbce850ab4066a1e1c671787ff02e.png
[932826-20160619155619194-1546500274.png]: /images/20220711/e5d51e0c1d5249679b8d5b8ba68c602a.png
[932826-20160619161206851-1097126076.png]: /images/20220711/32d131f72a5048f182d96bf62c799b43.png
[copycode.gif]: /images/20220711/b707f96be8be42ad974a8111cf484e65.png